1. 게리맨더링 2 (백준17779)
문제를 푸는 방법이 여러가지가 있을 수 있다고 생각합니다.
모든 방법이 일단 문제에서 중간 지역을 만드는 모든 경우를 모두 계산해주어야 합니다.
중간지역의 꼭지점 중 가장 위를 0번, 가장 위에서 왼쪽 밑을 1번, 가장 위에서 오른쪽 밑을 2번, 가장 밑을 3번 이라고 부르겠습니다.
여기서 핵심은 0번을 기준으로 1번과 2번만 찾으면 됩니다. ( 0번에서 1번 + 2번이 3번이기 때문입니다. 마름모 공식? )
그래서 0번을 기준으로 1번의 경우의 수와 2번의 경우의 수를 조합하면 모든 경우가 나오고 이때 전체 범위안에 들면 다음 계산(최대최소찾기)을 하면됩니다.
1번과 2번 꼭지점을 지정했다고 가정하고 계산을 하는데 총 5개 구역의 값을 찾아야합니다.
이때 이중 for문으로 1,2,3,4를 찾으면 5는 전체에서 1234를 빼주면 되기 때문에 1234만 찾습니다.
이때 핵심은, 이중 for문을 하드코딩으로 4가지 경우 모두 적어도 되지만 이중 for문에 범위만 체크해주면 모두 같기 때문에
각 구역의 범위를 배열에 넣기만 하면 됩니다.
각 구역의 범위는 1번 꼭지점을 기준으로 계산만 해주면 됩니다. 그리고 각 구역마다 계단 처럼 적어지거나 늘어나는 부분은 int 변수 한개를 ++해줘서
특정 범위를 기준으로 빼주거나 더해주면 됩니다.
[코드] : https://2heedu.tistory.com/174
2. 새로운 게임 2 (백준17837)
문제에서 주어진 조건을 순서대로 구현하면 됩니다.
제가 푼 방식은 덱을 이용하여 풀었습니다.
굳이 덱이 아니라도 스택이나 배열 등 여러가지 방법으로 풀 수 있습니다. 핵심은 자신과 그 위에 쌓인 것을 옮기는 것입니다.
말을 순서대로 움직입니다. 이때 다른 건 그냥 구현하면되는데 겹친 부분을 표현하는 것을 덱으로 했습니다.
덱 배열을 똑같이 하나 더 만들어서 그곳에 쌓인 말을 저장했습니다. 그러면 만약 옮기는 곳이 반대로 쌓아야하면 그 덱 배열에서 뒤에서 부터
옮겨주면 되고 아니면 자신부터 끝까지 옮겨주면 됩니다.
덱 배열을 사용해서 쌓여있는 말의 사이즈와 위치 push pop을 편하게 했습니다.
[코드] : https://2heedu.tistory.com/175
5. 연구소 3 (백준17142)
문제에서 주어진 조건을 잘 읽고 풀면 됩니다.
활성화 된 바이러스 옆에 비활성화 바이러스가 있다면 1초 후 그 비활성화 바이러스를 활성화 시킨다에 유의해야합니다.
문제는 먼저 모든 바이러스에 대해 활성화 시킬 바이러스를 골라야 합니다. 이를 재귀 또는 permutation으로 풀 수 있습니다.
저는 permutation으로 바이러스 조합을 만들어서 활성화 시켰습니다. 활성화 시키면 bfs를 통해 퍼트리면 됩니다.
퍼트릴 때마다 빈곳의 개수를 빼주면 0이 되는 순간 종료시키면 됩니다.
그리고 시간을 줄이는 한가지 방법이 min을 사용해서 현재까지 했던 시뮬레이션 중 가장 짧은 시간보다 시간이 넘어가면 바로 종료시키면
시간을 줄일 수 있습니다.
[코드] : https://2heedu.tistory.com/173
6. 이차원 배열과 연산 (백준17140)
문제를 푸는 다양한 방법이 있다고 생각합니다.
제가 푼 방법은 set과 multiset 그리고 priorty_queue를 사용했습니다.
한 줄 씩 읽어가면서 set과 multiset에 값을 넣게 되면 set에는 중복이 되지 않기때문에 어떤 숫자가 있는지 알 수 있고
multiset에는 중복된 모든 숫자가 들어가서 count를 통해 숫자의 개수를 알 수 있습니다.
따라서 set의 원소들을 돌며 숫자와 개수를 priority_queue에 넣어주게 되면 문제가 요구하는 정렬법에 따라 정렬이 됩니다.
이를 순서대로 넣어주면 쉽게 풀 수 있습니다. 이 방법말고 다양한 방법으로 할 수 있습니다.
[코드] : https://2heedu.tistory.com/172
7. 낚시왕 (백준17143)
문제에서 주어진대로 순서대로 구현을 하면 쉽게 풀 수 있습니다.
정확한 채점기준을 잘 모르겠지만 문제의 조건을 보면 문제를 만든 사람의 의도를 볼 수 있습니다.
주의깊게 보아야할 부분이 상어의 속도 s 의 최대크기입니다. s는 1000까지 입니다.
혹시, 상어의 이동(벽에 부딪혀 turn하는 경우와 그냥 이동)을 반복문으로 일일이 했다면 코드가 도는데 꽤 오랜시간이 걸릴 것 입니다.
출제자는 이것을 어떻게 수식으로 간단히 할 수 있을지 묻는 것 같았습니다.
제가 짠 코드는 상어의 이동을 수식하나로 한번에 이동시킵니다. 수식은 코드에서 go함수에 있으며 속도, 방향에 따른
상어의 이동 후 좌표, 방향을 바로 계산해 줍니다. 이를 통해 코드의 실행속도를 현저히 줄였습니다.
이외의 부분은 천천히 문제의 순서에 따라 쉽게 구현할 수 있습니다.
[코드] : https://2heedu.tistory.com/171?category=672811
8. 미세먼지 안녕! (백준17144)
문제에서 주어진대로 순서대로 구현을 하면 됩니다.
여기서 주의할 점은 2차 배열의 최대크기가 50X50이기 때문에 전체 탐색과 벡터에 담는 것 어떤 것이 빠른지 고려해야합니다.
만약 벡터에 미세먼지를 담게 된다면 공기청정기에 의한 이동때문에 상당히 번거로울 수 있습니다.
이 문제의 핵심도 이것이라고 생각합니다. 공기청정기에 의해 미세먼지가 이동합니다.
벡터에 담게되면 결국 다시 담아야하므로 이동된 미세먼지에 대해 다시 계산을 해야하는 문제가 생깁니다.
더 시간이 오래걸리고 이 문제의 핵심이라고 생각합니다.
물론, 코드의 실행속도를 더 줄이는 다양한 방법이 있지만 간결하게 문제에서 요구하는 것을 풀었을 때 아래와 같은 코드가 됩니다.
[코드] : https://2heedu.tistory.com/170?category=672811
9. 아기상어 (백준16236)
아기 상어가 움직일 수 있는 경로에 대해 가장 가까운 먹이를 찾기 위해 bfs를 이용합니다.
그러나 먹이를 먹는 순서에 주의해야 합니다. 같은 거리에 대해 가장 위, 가장 왼쪽 부터 먹기 때문에
일반적으로 bfs를 돌리면 반례가 나오게 됩니다. 따라서 이 문제의 핵심은 이 반례를 해결하는 거라고 생각합니다.
이를 위해 우선순위 큐와 가중치를 사용했습니다. 같은 거리에 있는 먹을 수 있는 먹이에 대해
i에 100을 곱하고 j를 더해서 우선순위 큐(오름차순 정렬)에 저장했습니다. 결국 우선순위 큐의 top에 있는 먹이가
아기 상어가 먹어야 하는 먹이가 되므로 쉽게 해결할 수 있습니다.
[코드] : https://2heedu.tistory.com/165
10. 나무재테크 (백준16235)
봄,여름,가을,겨울에 일어나는 일을 순서대로 코드화 하면 간단하게 해결할 수 있습니다.
1. 먼저 나무의 정보를 vector에 저장합니다. 그 후 K년의 시간을 돌립니다.
2. 봄에는 먼저 나이가 어린 나무를 찾기 위해 vector를 sort합니다. 그 후, 죽게되는 나무는 queue에 따로 넣어두고
죽지않는 나무는 나이 1증가 후 다시 넣습니다. 임의의 vector를 하나 더 만들어서 따로 담은 후 swap 했습니다.
3. 여름에는 queue에 담아 둔 죽은 나무 정보를 가져와서 처리합니다.
4. 가을에는 vector의 나무 정보를 가져와 번식시킵니다.
5. 겨울에는 전체 배열에 양분을 추가합니다. N의 크기가 작아 배열 전체를 한번 돌렸습니다.
[코드] : https://2heedu.tistory.com/167
11. 인구이동 (백준16234)
한번 체크했던 나라는 다시 안해도 되기 때문에 순서대로 체크하면서 bfs를 통해 국경을 열어 인구 이동을 시킵니다.
N의 크기가 작기 때문에 처음부터 시작해서 2차 배열의 끝까지 bool visit 체크하며 방문안했던 곳을 찾습니다.
안했던 곳은 queue와 vector에 넣습니다. 그 후 queue를 통해 bfs를 돌려 열려서 이동이 가능한 곳들을 찾아서 vector에 추가합니다.
결국 이동가능한, 연결된 나라들이 vector에 담기게 되고 인구를 이동하고 다음 방문하지 않았던 나라를 찾으면서 반복합니다.
[코드] : https://2heedu.tistory.com/166
12. 큐빙 (백준5373)
큐브를 돌리는 것에 대한 규칙을 찾으면 쉽게 풀 수 있습니다. 이 문제의 핵심은 6면에 대한 각 값, 총 54개의 값들을 어떻게 저장하냐가 중요하다고 생각합니다.
큐브를 회전했다는 것은 1. 중심면 (정사각형)이 90도 또는 -90도 회전 2. 중심면에 붙어있는 사이드 4개의 면들의 붙어있는 3개의 값들(총 12개) 가 회전 입니다.
어떠한 회전이든 모든 큐브의 값이 잘 저장만 되어 있으면 회전하는 코드는 각 값을 바꿔주기만 하면 끝나기 때문에 회전 코드는 매우 짧습니다.
이러한 규칙을 빠르게 적용하기 위해 익숙한 전개도를 활용하였습니다. 먼저, 전개도에 대해 54개의 값에 번호를 붙였습니다. 그 후 배열에 저장을 할 때 쉽게 회전
시키기 위해 총 9+12=21개의 값(회전하는 중심면+같이 회전되는 4개의 사이드 면의 3개 값들)을 저장하여 쉽게 회전시켰습니다.
코드를 짤 때 전개도를 그리면서 생각하다보니.... 엄청 길지는 않을 것 같아서...
처음 각 면 대한 배열 값 sur[6][21] 그리고 회전 할 때 바꾸는 위치의 값 ch[2][21]은 직접 값을 다 넣었습니다.
회전 할 때 다른 면보다 Bottom 부분을 회전할 때 햇갈릴 수 있습니다. 전개도를 해당 값을 매칭해보면 실수없이 정확히 이해할 수 있습니다.
[코드] : https://2heedu.tistory.com/163
13. 감시 (백준15683)
cctv의 방향을 구현하는 것이 중요합니다. 5개의 cctv의 처음 방향을 정하고 회전했을 때의 방향을 수식으로 표현합니다.
90도 회전은 (처음방향+i)%4 로 구현할 수 있습니다.
방향을 구현했으면 브루트포스 조합으로 모든 경우에 대해 연산을 합니다. 이때 memcpy를 통해 임시의 2차배열을 통해 되돌리는 것이 중요합니다.
모든 경우를 연산 후 가장 최소값을 출력하면 쉽게 풀 수 있습니다.
[코드] : https://2heedu.tistory.com/78
14. 사다리조작 (백준15684)
2차원 배열에서 브루트포스 조합으로 모든 경우를 연산합니다. 사다리가 놓일 수 있는 경우를 생각하고 0개부터 3개까지 모든 경우에 대해 연산을 해줍니다.
최소값을 찾아야 하기 때문에 i에서 i로 간다해도 모든 경우를 체크해주어야 합니다.
사다리를 놓을 때는 각 지점마다 오른쪽으로 놓였는지 왼쪽으로 놓였는지를 구분해줍니다. 저는 1과 -1로 하여 사디리 시뮬레이션 시에 가로 값이 움직이는 걸
한번에 표현했습니다.
그리고 N, M, H 값이 햇갈릴 수 있으니 주의해서 짜면 쉽게 풀 수 있습니다.
[코드] : https://2heedu.tistory.com/3
15. 드래곤커브 (백준15685)
규칙을 찾으면 쉽게 풀 수 있습니다. 반복되는 규칙이 잇습니다. 또한 방향에 관한 것이기에 +1 %4를 기억합니다.
그후 규칙을 찾으면 0방향을 기준으로 다른 방향은 시작 방향 값 만큼만 더해서 %4를 해주면 같으므로 하나만 계산하면 됩니다.
규칙을 다른 여러가지 방식으로 코드화 할 수 있는데 수식의 핵심은 %4입니다.
[코드] : https://2heedu.tistory.com/157
16. 치킨배달 (백준15686)
가능한 조합을 모두 연산합니다. 거리를 미리 저장하여 시간을 줄이고 재귀를 통해 연산합니다.
조합을 만들어 모든 조합에 대해 연산하는 브루트포스 문제입니다.
거리 계산을 할때 inline 함수를 쓰면 조금 시간이 줄지만 역량테스트 특성상 시간초과를 많이 고려하지 않아도 되기에 상관없다고 생각합니다.
[코드] : https://2heedu.tistory.com/158
모든 문제 관련 출처
- 백준 : https://www.acmicpc.net/workbook/view/1152
- SWEA : https://www.swexpertacademy.com/main/searchAll/searchMore.do?category=CODE&keyword=%EB%AA%A8%EC%9D%98+sw
작성자 : 히더
