꺼진불도다시보자

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 접근방법 최고점과 최저점을 저장한 후. 최고점에서 한 칸 제거하는 시간과 최저점에서 한 칸 추가하는 시간을 비교한다. 더 짧은 시간이 걸리는 쪽을 선택하고, 만약 최저점에서 추가할 블록이 없는 경우에는 무조건 최고점에서 한 칸 제거를 택한다. 코드 #include #include #include #include #include #include #include #include #include..

문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 접근방법 삼성 sw역량평가에 출제됐던 문제라고한다. 푸는 방법은 대충 bfs 이용해서 하는 거 같은데, 코드가 복잡해지니까 나중에는 디버깅이 잘 안되서 많이 헤멨다. 그래서 유투브를 참고했다. 링크 : https://www.youtube.com/watch?v=SarTy3ZwmVo&t=1114s&ab_channel=na982 내가 생각했던 풀이..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근방법 bfs를 이용해 푸는 문제였다. 처음 dfs로 접근했는데, dfs로 풀기엔 쉽지 않을 거 같다. sum과 cnt를 계산해야하는데 dfs를 사용하면 복잡해진다. 어쨋든 dfs든 bfs든 포인트는 돌면서 마주친 나라들을 배열에 담아두어서 나중에 한번에 sum과 cnt를 계산해 table의 값을 변경해 주는 것이다. 이를 위해서 table을 전역변수로 설정하는 것이 유리하다..

문제 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 접근방법 k의 개수만큼 배열의 크기를 유지하는 게 포인트라고 생각했다. 각 알파벳마다 인덱스를 저장할 배열이 필요했고, 그 배열의 크기는 k로 일정했으면 좋겠다는 생각이 들어서 queue를 선택했다. 각 알파벳마다 queue를 만들었다면, queue에 k개의 원소가 채워질 때마다 첫번째 인덱스와의 거리를 계산한후 push, pop해주면 된다. 그러면 queue의 크기를 항상 k로 유지할 ..

문제 https://www.acmicpc.net/problem/22233 접근방법 포인트는 2가지이다. parsing과 unordered_set 사용. 인풋값이 아래와 같이 크기때문에 최대한 시간을 줄이는 방법을 택해야한다. 1 ≤ N ≤ 2×10^5 1 ≤ M ≤ 2×10^5 map에서 접근 시간은 O(1)로 알고있었는데, map을 사용하니 시간초과가 났다. 알고보니 O(1)이 아니었다. map과 set은 둘 다 red-black-tree를 사용하고, unordered_set은 hash-table을 사용한다고 한다. 다음을 참고하자. - **std::map** - **Find:** O(log n) (finding a value by key) - **Inserting:** O(log n) - **Dele..

문제 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 접근방법 이분탐색이다. 이분탐색을 할 때 중요한 포인트는 오른쪽으로 이동할 때, mid+1을 해주고 같은 값(정답이 될 수 있는 값)일 때는 왼쪽으로 이동해주는 것이라고 생각한다. mid = (left + right) / 2이므로 left와 right이 이어지는 숫자인 경우, 항상 mid는 left에 위치하기 때문에, 여기서 만약 정답이 left에 ..

문제 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 접근방법 사이즈가 같은 경우와 한 사이즈 작은 경우, 한 사이즈 큰 경우를 나눠서 계산했다. map을 복사해와서, word에 있는 알파벳이 cand에 몇개 존재하냐를 세는 것이 포인트다. 만약 word에 D가 2개 있을 경우, cand에 D가 3개 있다면, 3개를 다 세면 안되고 2개만 세야하기 때문에 세면서 하나씩 빼준다. cand에 D가 1개 있다면, 1개만 셀 것이기 때문에 match..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 접근방법 크루스칼 알고리즘을 사용했다. Edge와 DisjointSet의 클래스를 각각 선언해 사용했다. Kruskal 또는 prim 알고리즘을 구현할 때, 포인트는 Edge 클래스 내에 operator를 선언하는 것이다. 부등호의 방향이 >임을 잊지말자. DisjointSet 생성자에서 parent와 rank의 크기를 V+1으로 초기화해야하는데..

문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 접근방법 BFS를 활용해 최단거리를 구하는 문제다. queue를 정의하고, pair.first에 위치 저장하고, pair.second에 이동시간 저장했다. 포인트는 방문여부 체크로 중복을 줄여주는 데 있었다. 방문여부 체크를 안하면 메모리 초과로 실패했다. 1 2가 입력되면, 0이 정답이 되어야 하는데, 1이 나왔다. 알고보니 함수 리턴하는 과정에서 순서..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 접근방법 트리의 지름 구하는 방법은 임의의 노드 x로부터 가장 먼 노드를 하나 선택하고 그 노드로부터 가장 먼 노드와의 거리를 측정하는 것이다. 문제의 그림을 보면 직관적으로 이해할 수 있다. 가장 먼 노드를 찾는 것과 가장 먼 노드와의 길이를 측정하기 위해서 DFS알고리즘을 이용했다. 코드 #include #include #include #include #include ..