거창한 시작

www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 알고리즘 종류 - 투포인터 사고 과정 - 정렬된 상태로 입력된 용액의 양쪽 끝에 포인터를 두고 비교한다. 1. 양쪽 끝의 합이 0보다 작으면, 왼쪽 포인터를 +1해준다. 2. 양쪽 끝의 합이 0보다 크면, 오른쪽 포인터를 -1해준다. 3. 두 용액의 합의 절대값을 이전에 저장한 answer이라는 변수보다 작으면 answer을 갱신한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 1..

www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 빗물이 고인다는 것은 양쪽에 벽이 있다는 것을 의미한다. 따라서, 벽이 나타나면, 같은 행에서 다른 벽이 있는지 확인하고 차이 만큼 빗물이 고인다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4..

www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 알고리즘 종류 - 플로이드 와샬 사고 과정 1. 2차원 배열에 INF로 초기화한다. 2. 플로이드 와샬로 값을 비교하면서 갱신한다. 3. [v][v] 값들 중에서 최소 값을 출력한다. 경로가 없으면 -1을 출력한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 알고리즘 종류 - 다익스트라 - BFS 사고 과정 - 보통의 다익스트라 문제는 노드 간의 간선 정보가 주어지고, 1차원 배열에 비용을 저장해서 문제를 해결한다. 이 문제는 이전과 다르게 2차원 배열에 문제를 해결해야 한다. 1. priority_queue를 이용해서 이동할 다음 위치(y, x)에 최소 비용을 저장한다. 2. 다음 위치는 4방향으로 구한다. 3. 다음 위치에서 이전에 저장된 비용..

www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 알고리즘 종류 - 트리 사고 과정 - 떠오르는 아이디어가 몇 가지 있었지만, 활용할 수 없음을 알고 검색을 했다. 이 블로그와 이 블로그의 도움으로 해결할 수 있었다. 최종적으로 이 블로그를 보고 깨달았다. 그림으로 설명을 잘 해주셨다. - 방법을 노트에 적어서 설명하는 것이 편해서 이미지를 첨부했다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 알고리즘 종류 - 트리 - DFS 사고 과정 - 가장 긴 한 쪽 노드에서 다른 쪽 가장 긴 노드로 이동해야 한다. 그러기 위해서는 양방향으로 움직일 수 있어야 한다. - DFS로 root에서 가장 긴 한 쪽 노드를 찾으면, 그곳을 start 노드로 잡고 그곳에서 다시 DFS를 하여, 가장 긴 다른 한 쪽 노드를 찾는다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 좌표와 방향 수정 1. 본인은 왼쪽 상단을 (1,1)으로 사용하려고 한다. 그러면 좌표를 수정하고 4방향도 수정한다. 위쪽이 S이고 아래는 N이 된다. EW는 그대로이다. - 동작 1. for문으로 저장된 명령을 하나씩 수행한다. 2. 로봇의 ID를 가져와서 명령을 수행하고 조건 1.벽에 부딪혔는지, 조건 2. 로봇에 부딪혔는지 확인한다. 구현(C++..

www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 소용돌이 만들기 1. 소용돌이는 중심에서 시작해서 2번씩 같은 거리를 이동한다. 2. 소용돌이는 원하는 배열이 다 차면 멈춘다. - 출력 1. 배열 내에서 최대 길이 숫자에 맞춰서 출력해야 한다. 2. 최대 길이 숫자를 찾고, 길이에 맞춰서 출력한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 알고리즘 종류 - 투 포인터 사고 과정 - 두 개의 포인터를 배열의 양끝에 놓고 비교하면서 포인터를 움직이면 된다. 1. left와 right에 해당하는 값을 더해서 sum을 구한다. 2. sum의 절대값이 이전의 값보다 작으면, left와 right가 가리키는 값을 저장한다. 3. left와 right가 교차할 때까지 반복한다. 구현(C++) 1 2 3 4 5 6 7 8 9 ..

www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 알고리즘 종류 - 플로이드 와샬(floyd warshall) 사고 과정 - 플로이드 와샬 적용하기 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include using na..