차가운오미자님의 유리병

https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제 이해 주어지는 입력 중에, 각 요소가 어느 위치의 길이인지를 파악하는 것이 관건이다. 주어질 수 있는 경우는 ㄱ,┏, ┗, ┛ 네 개이다. ㄱ 모양의 경우에 한 번 씩 나오는 방향의 길이가 큰 사각형이 너비(North), 높이(West)이고, 두 번씩 나오는 방향(South, East)의 길이들 중에, 껴있는 것이 작은 사각혐의 너비, 높이이다. 다시 말해서 East방향의 길이들 중에서도 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 이해 모든 경우를 탐색해서, 연결되어 있는 것들의 수를 세서 저장하면 된다. (map[i][j] == 0일때 BFS 혹은 DFS를 돌리기) 모든 경우를 탐색하기 때문에 DFS를 이용해도 되고, BFS를 이용해도 된다. 문제를 잘 읽어야하는게, 집의 개수를 저장한 배열을 정렬해서 출력해야 한다. (안했다가 계속 허탕침) 작성 코드(C) 1. BFS 이용 #include #include int N..

이진 탐색은 범위를 반으로 나눠가며 찾는 것이다. 선형 탐색보다 훨씬 빠르게 타겟을 찾을 수 있다. 시간 복잡도는 NlogN이다 주의할 점은, 이진 탐색에서 m의 왼쪽에 m보다 작은 요소가, 오른쪽에 m보다 큰 요소가 있는 걸 보장하기 위해, 이진 탐색 전에 배열은 반드시 정렬되어 있어야 한다. 예를 들어서, 9개의 요소를 가진 배열 arr가 있다고 가정하자. 1 2 3 4 5 6 7 8 9 이렇게 있을 때, 3을 찾는다고 하자. 일단 전체 arr[0] ~arr[8] 중 중간 요소가 3인지 확인한다. 타겟은 3보다 5가 크므로 5보다 아래에 있다는 소리이다. 그럼 다시 arr[0] ~ arr[3] 을 찾아본다. 중간((0+3)/2)은 arr[1] == 2 이다. 타겟 보다 작으므로 오른쪽에 있다는 소리다..

https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 문제 이해 일단 기본적으로 주어지는 입력 들의 수가 굉장히 크다. 사대가 최대 100,000개이고, 동물의 수가 최대 100,000 이기 때문에, 각 사대 별 동물 탐색, 혹은 동물별 사대 탐색을 하면 100,000 * 100,000 = 10,000,000,000번의 루프이므로 절대 시간 내에 문제를 풀 수 없다. 탐색의 시간을 줄이기 위해..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=942&sca=50&sfl=wr_hit&stx=1669&sop=and JUNGOL www.jungol.co.kr 문제 이해 계속 DFS, BFS만 생각하다가 이 문제를 봐서 처음에 DFS를 해야하나? 생각했다. 근데 소시지가 5000개이다. 절대 불가능 Greedy를 사용해야 하는 문제이다. 공장을 한 번 정비할 때 최대한의 소시지를 만들고 다시 정비하고 최대한 만들고 정비하고... 를 반복해야 한다. 한 번 정비 후마다 남아있는 소시지 중에 가장 작은 소시지부터 만들면 된다. 루프를 돈다. (남은 소시지 개수 > 0 까지) 소시지 배열을 정렬한다. (길이를 기준으로 정렬한다. ) 루프를 돈다. 여기서는 자..

https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 문제 이해 해밍거리가 1이란 주어진 두 개의 코드 중에 하나의 비트만 다른 관계를 뜻한다. 코드 A 부터 B 까지 가장 짧은 경로를 찾는다. 따라서 BFS를 이용한다. 움직이는 것은 해밍 거리가 1인 관계에서만 가능하다. 해밍 거리를 판단하는 것은 별도의 함수 (isHamming)로 구현해주었다. 단 BFS 를 이용할 때, 그 경로를 저장하는 것이 어렵다. 이를 위해 별도의 배열을 선언하여, ..

VScode에서 디버깅을 하면서 변수를 확인하고 싶은데, vscode 에서 C++을 디버깅할 땐 터미널 input를 못받는다. 따라서 freopen을 사용해야 하는데, main함수 맨 위에 freopen("input.txt", "r", stdin); 을 추가해주면 된다. 근데 디버깅을 해주니까, input.txt에 있는 데이터가 들어오지 않는다는 것을 발견했다. 찾아보니, launch.json에 있는 cwd 경로를 input.txt가 있는 디렉터리로 설정하면 된다는 것을 알아냈다. https://stackoverflow.com/questions/65550374/vs-code-on-windows-debugger-does-not-work-with-freopen VS Code on Windows debugge..

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 나는 처음에 BFS를 이용해서 풀었다. 근데 알고보니 BFS까지 필요없는 문제였다. 1. BFS 문제 이해 맵을 X+1 * Y+1 로 바꿔서, 동근이 위치로부터 특정 위치까지의 경로를 BFS로 visited 배열에 찍어두고, 각 상점 좌표에 있는 값을 답으로 찍어주었다. 주어진 맵이 이렇게 생겼다면, 나는 맵을 다시 이렇게 구성해서 D를 시작점으로 해서 BFS를 돌렸다. 대신 저 하얀 부분은 못가도록 ..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 이해 1. 공기(0) 옆에 있는 치즈(1)를 녹인다 (= 공기로 바꾼다) 2. 단, 치즈로 둘러쌓인 공간은 공기지만 치즈를 녹이지 않는다. 3. 문제의 핵심은 벽면은 모두 공기라는 것이다. 즉 (0, 0)에서 출발하면 치즈 내 구멍을 뺀 바깥 공기 모두를 탐색할 수 있다. 해결: 치즈가 모두 녹을 때까지 BFS를 실행한다. 작성 코드 (C) #include int Y, X; int map[100 + 5][100..

https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 이해 역시 문제를 이해하는 것이 중요하다 문제에서 제시한 표가 2차원 배열로 주어져서 그런데, 그냥 수의 나열로 보는게 훨씬 낫다. 분자와 분모의 합이 2인 것은 1개 분자와 분모의 합이 3인 것은 2개 분자와 분모의 합이 4인 것은 3개 이런 식으로 이어진다. 이걸 일반화하면 분자와 분모의 합이 i+1 인 것이 i개씩 나열되어 있는 것이다. 각 덩어리를 살펴보면 i가 홀수인 경우에는 분자가 큰 경우부터 나열되고 i가 짝수인 경우에는 분자가 작은 경우부터 나열된다. 다시 일반화 하면 i가 홀수인 경우 분모가 1부터 i-1까..