차가운오미자님의 유리병

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..

cin, cout 은 시간이 많이 걸린다. printf나 scanf를 사용하면 시간을 단축할 수 있지만, ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 이걸 main함수 맨 앞에 쓰는 게 가장 빠르다.

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까..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 문제 이해 아래 층부터 채워나가면 된다. 각 칸의 패턴을 파악하면 금방 식을 세워서 해결할 수 있다. 1호 2호 3호 1층 0+1 = 1 1+2 = 3 1+2+3 = (1+2) + 3 = 6 0층 1 2 3 보면 각 k층 n호는 k-1층의 1부터 n호까지의 합인데, k-1층의 1부터 n-1호까지의 값이 k층 n-1호에 있으므로, k-1층 n호 + k층 n-1호의 값을 더하면 된다. 주어지는 테스트 케이스가 여러 개여서, 그냥 14층 14..

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 이해 수열이 1, 6, 12 로 늘어나는 것을 확인하면 된다. 1: 1번 2~7: 2번 8~19 : 3번 .... 이런식으로 늘어간다. 작성 코드 (C++) #include using namespace std; int N; int main(void){ cin >> N; if(N==1) { printf("1"); return 0; } int i; int no = 1; for(i = 1; ;i++){ n..

모든 요소를 탐색하면서 요구사항에 맞게 동작하면 된다. DFS를 이용하거나 BFS를 사용하는데 1. DFS를 사용할 경우 코드가 간단하지만, map이 크면 메모리 부족이 일어날 수 있고, 디버깅이 어렵다 2. BFS는 맵이 너무 클 경우에 사용한다. https://chagaun-omija.tistory.com/71 [백준] 2667: 단지번호붙이기 https://www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번 chagaun-omija.tistory.com 여기 있는 이 문제가 Flood Fill의 예시 문제이다. 문제 해설처럼 맵에서 ..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954 JUNGOL www.jungol.co.kr 문제 이해 가능한 경로들 중에 최적의 경로를 찾는 것이기 때문에 (최소 비용 구하기) DFS를 돌리면 되는 문제이다. Depth 는 총 배달해야 하는 장소의 개수 (12)이다. 사실 12개의 초이스들을 12번 선택해야 하기 때문에 상당히 수가 크지만, (12!) 이미 방문한 곳은 다시 방문하지 않기 때문에 충분히 작아질 수 있다. 또한, 마지막 가지치기를 하면 생각보다 가지가 많이 뻗지 않을 수있다. 기본적으로 DFS를 돌릴 때는 depth가 12가 넘어가지 않는 정도면 해낼 수 있다고 생각하면 된다. 회사(1)에서 출발해서, 가능한 경로들을 하나하나..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 이해 FIFO 방식이라고 했으므로 큐를 이용하는 문제이다. 문서를 앞부터 하나하나 체크하면서, 뒤에 우선순위가 자기보다 높은 애가 있으면 프린트하지 않고 다시 큐의 뒤에 넣어준다. 관건은 우선순위가 자기보다 높은 애가 있는지를 판단하는 것이다. 우선순위가 1부터 9로 범위가 작으므로 각 우선순위 별로 문서가 몇 개가 있는지를 확인하면 편하다. 이를 위해서 우선순위 별 문서 수를 저장한 배열을 이..