BOJ (34) 썸네일형 리스트형 BOJ 1655 가운데를 말해요 BOJ 백준 1655 C++ 가운데를 말해요 https://www.acmicpc.net/problem/1655 0) 처음에는 이중 for문 이용해서 N^2시간에 구하려고 했는데 직관적으로 시간초과가 예상되었다(N이 최대 10만) 1) priority queue를 이용한 두개의 heap을 통해 중간값을 구할 수 있다. 2) [조건 1] pqLeft의 크기는 pqRight와 같거나, 1 크다 [조건 2] pqLeft.top() 의 값은 -pqRight.top() 보다 항상 작다. -> 크기가 같을 때, left에 push하므로 push 후 top을 확인하여, 재정렬 필요 ***** 문제에 주어진 실행 시 pqLeft, pqRight에 실제 들어있는 값 pqLeft : 기본 우선순위 큐 사용, 내림차순 정렬 .. BOJ 2151 거울 설치 백준 BOJ 2151 C++ 거울 설치 https://www.acmicpc.net/problem/2151 1) BFS 문제 -- BFS는 이제 빠른 시간 내에 풀 줄 안다고 생각했는데 .. 오래 걸렸다! 더 열심히! 2) 코드를 깔끔하게 짠다고(중복 줄이기, 불필요한 연산 줄이기) 생각을 오래 했는데.. 부족한 것 같다. 3) 거울이 없을 때는 공통 부분이므로 따로 조건문 안에 넣지 않았고, 다음 칸이 '!'일 때 방향 전환해서 큐에 넣었다. /** * 200610 * 2151 거울 설치 * BFS * */ #include #include #define INF 987654321 using namespace std; int N; char map[52][52]; int check[52][52][4]; int.. BOJ 1600 말이 되고픈 원숭이 백준 BOJ 1600 C++ 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1) BFS 문제 2) #14442 벽 부수고 이동하기2 (https://www.acmicpc.net/problem/14442) 와 비슷한 문제라고 생각했다. #14442와 마찬가지로 주어진 K만큼 특별한 이동(말의 이동처럼)을 할 수 있다.(hx, hy) cnt가 K보다 작을 때는 hx, hy를 이용하여 이동하는 경우를 큐에 push, 그리고 K와 관계없이 dx,dy를 이용하여 인접한 이동에 대해 큐에 push했다. 3) 원숭이의 도착 지점이 (H,W)이므로, 도착 지점 도달 시 가능한 ans의 최솟값을 비교하여 update한다. 4) 내가 실수했던 지점은, 47line에서 check[nx.. BOJ 1986 체스 백준 BOJ 체스 C++ https://www.acmicpc.net/problem/1986 1) 풀면서 정.말.로 다 해보는 거 맞아? 하는 의문이 정말 많이 들었는데 정말 '브루트 포스'가 맞았다.. 2) 시키는 대로 조건 설정 해주면 된다. 나는 Queen, Knight의 좌표를 벡터에 넣어서 차례대로 말을 움직였다. 3) [Queen:1 / Knight:2 / Pawn:3 / Queen 이동 가능:4 / Knight 이동 가능:5] 설정하여 마지막에 map의 값이 0인 것만 카운트해서 출력한다. #include #include using namespace std; int N, M; int map[1005][1005]; struct info{ int x, y; }; vector q; vector k;.. BOJ 2565 전깃줄 백준 BOJ 전깃줄 C++ https://www.acmicpc.net/problem/2565 1) DP를 이용한 LIS (최장 증가 부분 수열, Longest increasing subsequence) 2) LIS를 복습 할 수 있었던 문제. 최근까지 헷갈렸는데 이번에 확실히 정리! 3) 이 문제의 output은 LIS에 포함되지 않는 것을 출력해야 함. /** * 200522 * BOJ 2565 전깃줄 * LIS 최장 증가 부분 수열 * */ #include #include using namespace std; int N; pair arr[105]; int mxLen[105]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin .. BOJ 1461 도서관 백준 BOJ 1461 도서관 C++ https://www.acmicpc.net/problem/1461 1) 단순 시뮬레이션 문제 2) 조건 "책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. " 를 이용해서 왼쪽/오른쪽 통틀어서 가장 큰 절댓값을 가진 위치를 마지막에 이동하는 것으로 생각하여 ans에 더한다. 3) 그 외 값들은 책을 두고, 다시 원점 0으로 돌아와야 하기 때문에 leftLoc[]에서 인덱스가 가장 큰 것의 배열값X2(왕복)을 ans에 더한 후, M만큼 인덱스를 감소했다. 마찬가지로 오른쪽(rightLoc[])도 인덱스가 큰 값에서부터 확인하여 ans에 더한 후, M만큼씩 인덱스를 이동했다. 4) 위치가 담긴 배열의 인덱스를 적절히 조작해서 계산하는 재미있는 문제였다. /.. BOJ 1517 버블 소트 백준 BOJ 1517 버블 소트 C++ https://www.acmicpc.net/problem/1517 1) 문제의 N제한이 50만이기 때문에, O(N^2)은 TLE이다. → 문제 이름은 '버블 소트'이지만 "합병 정렬"을 이용하여 풀어야 한다. 2) 합병 정렬 수행시, 원소의 위치가 변경 될 때 그 거리를 count 한다. 3) 합병 정렬을 다시 구현해보고 복습할 수 있는 문제였다. // no bubbleSort, yes mergeSort #include #include using namespace std; int N; int a[500005]; int b[500005]; long long ans=0; void merge(int start, int mid, int end){ int i = start;.. BOJ 14442 벽 부수고 이동하기 2 백준 BOJ 14442 벽 부수고 이동하기 2 (C++) https://www.acmicpc.net/problem/14442 1) BFS 문제이다. 2) 에서 벽을 부술 수 있는 갯수인 cnt의 조건만 변경하면 쉽게 풀 수 있다. /** * 200519 * BOJ 14442 벽 부수고 이동하기 2 * BFS */ #include #include using namespace std; int N, M, K; int map[1005][1005]; int check[1005][1005][11]; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int cnt=0; int bfs(int x, int y){ queue q; q.push(make_pair( make_pair(x,y), 0.. 이전 1 2 3 4 5 다음 목록 더보기