지금까지 배운 도구들 중 무엇을 쓰면 될지 문제 분류(=라벨링)을 하고 (ex. 그리디 / 스택 / 우선순위 큐 / 브루트포스 / DFS / 백트래킹 / 이분탐색 / 구현 등) 그 도구를 이용한 간략한 풀이 작성

1. (g4) 1744 수 묶기

문제

두 수를 묶어 곱하는 경우는 다음과 같다.

1. 양수x양수
   두 수의 크기가 클 수록 그 곱이 커진다.
2. 양수x음수
   두 수의 곱이 음수가 되므로 총 합의 크기가 오히려 작아진다.
   따라서 양수x음수의 두 수는 묶지 않고 양수x양수, 음수x음수 끼리만 묶는다.
3. 음수x음수
   두 수의 크기가 작을수록 그 곱이 커진다.

따라서 양수와 양수는 큰 수들을 먼저 묶어주고
음수와 음수는 작은 수들을 먼저 묶어줘야 그 곱이 가장 커질 수 있다.

즉, 그리디 알고리즘을 활용하는 문제이다.

https://jaekwan.tistory.com/13

2. (g4) 2458 키 순서

문제

두 학생끼리 키를 비교한 결과를 토대로 단방향 그래프를 만들어주고
(편의상 키가 가장 작은 학생부터 자신이 몇 번째인지 알고 싶은 학생의 번호를 target이라고 하겠다.)
target 부터 이동 가능한 모든 정점의 갯수(target보다 큰 학생의 수)와
특정 정점에서 target까지 도달할 수 있는 정점의 갯수(target보다 작은 학생의 수)를 더한 값이 전체 정점의 수와 같다면 target 학생은 본인이 자신의 키가 몇 번째인지 알 수 있다.
따라서 BFS or DFS 중에 편한 것으로 그래프를 완전탐색 해주면 된다.

https://onlytrying.tistory.com/218

3. (s1) 10597 순열장난

문제

순열의 수들을 처음부터 차례대로 한자리 or 두자리로 나누어야 한다.
한자리로 나눌껀지 두자리로 나눌껀지 두가지 경우가 존재하기 때문에 재귀를 사용한다.
완탐 재귀니까..DFS가 떠오른다.
대신 1~50의 수는 하나씩만 나올 수 있으므로 나왔는지 안나왔는지 체크해주는 배열이 필요하고 나온 수를 저장해줄 배열도 필요하다.
재귀를 돌고 난뒤에는 다시 돌아와 다른 경우 (한자리 수로 나누었다면 두자리 수로, 두자리 수로 나누었다면 이번엔 한자리 수로) 도 돌아야 하므로 두 배열도 다시 원래대로 돌려놔야 한다.

https://ip99202.github.io/posts/%EB%B0%B1%EC%A4%80-10597-%EC%88%9C%EC%97%B4%EC%9E%A5%EB%82%9C/

4. (s4) 2840 행운의 바퀴

문제

행운의 바퀴는 시계방향으로 돌기 때문에 배열을 S만큼 왼쪽으로 돌면서 글자를 하나씩 넣어주면 된다.
대신 조건이 있는데
1. 같은 자리에 중복되어 글자를 넣을 수 없다.
2. 다른 자리에 같은 글자를 중복되어 넣을 수 없다.
두 조건을 만족하지 않는 다면 "!"를 출력하고 배열의 빈칸은 "?"을 출력한다.
단순 구현문제

5. (g1) 3954 Brainf**k 인터프리터

문제

연산자마다 수행해야 할게 다르므로 구현문제이다.
점프하는 연산자 "[" 와 "]"가 있으므로 괄호의 위치를 기록해둘 필요가 있을 것 같다.

6. (g1) 3015 오아시스 재결합

문제

읽자마자 2493 탑 문제가 생각났다.
stack을 사용하는데, stack에 첫번째 수를 넣고

1. stack.top > now
   now는 stack.top을 볼 수 있으므로 answer(서로 볼 수 있는 쌍의 수) ++
   now는 stack.top 앞의 수들을 볼 수 없다.
   now를 push 해준다.
2. stack.top < now
   now는 stack.top을 볼 수 있으므로 answer ++
   now 다음 수는 now 때문에 now 이전의 수를 볼 수 없다.
   stack.top을 pop 해주고
   now를 push 해준다.
3. stack.top == now
   음..

참고한 블로그에서는
stack<pair<int,int>>로 구현했는데
first에는 키를, second에는 현재 스택에 같은 키를 가진 사람의 수를 저장했다.

잘 이해가 안된다..(미해결)

https://velog.io/@morphine/BOJ.-3015-%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4-%EC%9E%AC%EA%B2%B0%ED%95%A9

7. (g4) 7573 고기잡이

문제

모든 위치에서 가능한 그물을 던져 그 안에 있는 물고기들을 세기에는 일단 크기가 NxN (N은 최대 10000)을 한칸씩 다 돌아야 하고 가능한 그물도 주어진 그물의 길이에 따라 굉장히 여러가지가 있으므로 시간초과가 날 것 같다.

따라서 한칸씩 다 따져보지 말고 물고기가 있는 곳을 그물의 꼭지점으로, 즉 물고기가 있는 곳까지만 그물을 쳐서 그 안에 몇마리가 있는지 확인해보면 될 것 같다.

브루트포스
https://westmino.tistory.com/51

8. (g1) 13460 구슬 탈출 2

문제

구슬이 움질일 수 있는 방향은 상하좌우 4가지 이다.
빨간 구슬과 파란 구슬은 동시에 같은 방향으로 중력을 이용해서 굴린다.
무조건 두 구슬이 움직여야 하는건 아니고 굴리는 방향으로 막히지 않은 구슬만 이동한다.
즉, 한번 움직일 때마다 두 구슬의 이동을 각각 체크해야 한다.

굴릴 수 있는 횟수는 10번으로 제한되어 있기 때문에 굴린 횟수를 저장해가며 진행해야 한다.

최단경로를 구하는 문제이므로 BFS

https://sanghyu.tistory.com/74

9. (s5) 1059 좋은 구간

문제

A<B를 만족하는 수와 A,B도 정수 집합에 속하지 않아야 한다.
즉, n을 포함하는 정수 집합의 구간을 먼저 구해야 한다.
따라서 정수 집합을 먼저 정렬해준다.

예제1로 보면

4
1 7 14 10 -> 정렬 -> 1 7 10 14
2

n(2)을 포함하는 정수 집합의 구간은 1과 7이다. 이제 1과 7 사이에 속해있는 n을 포함하는 구간의 수를 구하면 된다.

답 : [2,3], [2,4], [2,5], [2, 6]

브루트포스 문제이다.

10. (p5) 1131 숫자

문제

N, SK(N), SK(SK(N)), … 수열을 언제까지 하는지에 대한 조건이 없다.
예제를 보면서 규칙을 찾아보면

1: 1, 1, 1...
2: 2, 4, 16, 37, 58, 89, 145, 42, 20, 4...
3: 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37...
4: 4, 16, 37, 58, 89, 145, 42, 20, 4...
5: 5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89...

일의 자리 수와 십의 자리 수(백의 자리까지 있다면 백의 자리 + 십의 자리를 합쳐 십의 자리로 보면됨)의 대소 관계에 따라 다음수가 커지거나 작아지므로 브루트포스로 풀면되지 않을까 싶었지만 안된다..
범위가 1 ≤ A ≤ B ≤ 1,000,000 이므로 2초를 분명히 넘을 것 같다.

음..(미해결)

https://blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222447946383&categoryNo=11&parentCategoryNo=52&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView

11. (g5) 1107 리모컨

문제

예제가 이해가 안간다...
(미해결)

12. (s4) 1205 등수 구하기

문제

새로운 점수를 현재 랭킹 리스트에 넣고 내림차순으로 정렬한 뒤,
가장 큰 수부터 랭킹을 세어주면 된다.

새로운 점수를 랭킹 리스트에 넣은 뒤 정렬하고 그 크기가 P보다 크면 가장 작은 수를 제거한다. 여기서 가장 작은 수가 새로운 점수였다면 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다는 것이므로 -1을 출력한다.

가장 큰 수부터 랭킹을 세어줄 때는 같은 수라면 등수가 같고, 그 다음 다른 수는 크기가 같았던 이전 수들의 개수만큼 더한 것이 등수가 된다.

일반적인 구현 문제

13. (b2) 2902 KMP는 왜 KMP일까?

문제

대문자들을 한문자열로 합치는 간단한 구현 문제

14. (s4) 1026 보물

문제

A를 오름차순으로 정렬하고 B를 내림차순으로 정렬하여

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

함수 S를 구하면 되는 간단한 구현 문제

15. (s4) 2607 비슷한 단어

문제

비슷한 단어의 경우
1. 같은 종류의 문자를 사용하면서 순서는 다른 단어
2. 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 1번을 만족하는 경우

순서는 고려하지 않아도 되므로 단어들의 문자별 사용 횟수를 아스키 코드 순으로 배열에 저장하여 1,2 번을 만족할 수 있는지 판별하는 간단한 구현 문제

16. (p5) 1184 귀농

문제

두 땅은 꼭짓점 하나에서 만난다.
따라서 만날 꼭짓점을 하나 정하고 그 꼭짓점을 기준으로
1. 위쪽의 오른쪽과 아래쪽의 왼쪽
2. 위쪽의 왼쪽과 아래쪽의 오른쪽
두가지 경우로 땅의 크기를 각각 정하여 수익이 같은 경우를 카운트 해준다.

(실제 구현을 어떻게 해야할지 감이 잘 안옴)

(미해결)

https://heechan3006.github.io/problemsolving/2020/03/01/BOJ_1184.html

17. (b1) 2167 2차원 배열의 합

문제

배열을 탐색하면서 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하면 되는 간단한 구현 문제

18. (b2) 2920 음계

문제

오름차순인지, 내림차순인지, 둘 다 아닌지 배열을 탐색하며 판별하는 간단한 구현 문제

19. (s3) 14501 퇴사

문제

특정요일에 상담을 하는지 안하는지에 따라 최대 수익이 달라진다.
각요일에 상담을 할지 안할지 경우마다 이전 요일의 경우도 중복 연산되는 것을 방지하기 위해 dp의 메모이제이션을 사용한다.

1일부터 N일까지 각요일에 상담을 할지 안할지 경우를 모두 따져봐야 하므로 각각 재귀함수에 넣고 상담을 하지 않은 경우(기존 최대이익)와 재귀함수에 넣은 경우 중에 큰 값을 현재 최대이익으로 최신화 하면서 진행한다.

재귀함수 안에서도 i 일 부터 N일까지 상담을 할지 안할지 경우도 판단해야 하므로 위와 동일하게 상담을 하지 않은 경우(기존 최대이익)와 재귀함수에 넣은 경우 중에 큰 값을 현재 최대이익으로 최신화 하면서 진행한다.

https://yjyoon-dev.github.io/boj/2020/10/29/boj-14501/

20. (g5) 14502 연구소

문제

일단 바이러스가 이동하며 퍼지기 때문에 BFS로 경로를 따져 최종 안전 영역을 구할 수 있다.
그리고 벽을 세워야 하는데 N과 M의 범위가 (3 ≤ N, M ≤ 8) 작기 때문에 3*8C3 으로 벽을 세울 수 있는 모든 경우를 제한시간안에 판별해 볼 수 있을 것 같다.
벽을 세울 수 있는 모든 경우마다 BFS로 최종 안전 영역을 구해 안전 영역의 최댓값을 구한다.
브루트포스와 BFS 둘 다 사용하는 문제

https://jaekwan.tistory.com/21

21. (b3) 2163 초콜릿 자르기

문제

NxM 초콜릿의 세로 N먼저 쪼개면 N-1번을 쪼개야 모든 세로 길이가 1이 된다.
이제 가로 M을 쪼개야 하는데 N개의 가로 조각을 M-1번 쪼개야 모든 가로 길이가 1이 된다.
즉 점화식은 $(N-1)+N(M-1)$

-> 구현 문제이다.

22. (g2) 1655 가운데를 말해요

문제

백준이가 수를 넣을 때마다 순서대로 정렬(오름차순, 내림차순 둘 다 상관 없지만 오름차순으로 넣자)되어야 동생이 중간 값을 구하기 편해진다. 따라서 우선순위 큐를 사용하여 수를 넣고 수를 넣을 때마다 들어가 있는 수의 개수가 홀수 일때는 중간값을, 짝수일때는 중간값 중 작은 수이므로 오름차순 상으로는 중간값 중 먼저 나오는 값이다.

23. (b2) 2804 크로스워드 만들기

문제

단어 B에 단어 A에도 있는 글자를 먼저 찾는다.
찾은 글자의 단어 B에서의 인덱스가 겹친 위치의 y축 좌표가 되고
찾은 글자의 단어 A에서의 인덱스가 겹친 위치의 x축 좌표가 된다.

-> 구현 문제이다.

24. (g3) 1256 사전

문제

모든 조합의 수보다 더 큰 순서를 물어볼 경우 -1를 출력해야 하므로 가능한 조합의 수를 구해야 한다.

모든 경우를 만들어서 선형 탐색한다면 $1 ≤ N, M ≤ 100$ 이므로 만들 수 있는 모든 경우의 수는 $200!/100!100!$ 음.. 굉장히 큰 수가 나올 것 같다. (브루트포스는 탈락)

바로 이전 조합((n-1,m) or (n,m-1))에서
(n,m)개를 사용한 조합은 아래 2가지 경우가 있을 것이다.

1. (n-1,m)개를 사용한 조합 끝에 a를 한개 더 붙이는 경우
2. (n,m-1)개를 사용한 조합 끝에 z를 한개 더 붙이는 경우

점화식으로 표현하면

$dp[n][m]$ : (n,m)개를 사용한 조합의 경우의 수
$dp[n][m] = dp[n-1][m] + dp[n][m-1]$

• n이나 m중에 0인 경우에는 한가지 알파펫만 k만큼 이어준다.
• 이외의 경우에는 앞부터 a를 붙이는 경우, z를 붙이는 경우로 나누어 재귀를 통해 문자열을 구한다.

https://mapocodingpark.blogspot.com/2020/02/BOJ-1256.html

25. (g5) 16234 인구 이동

문제

그래프(맵) 상을 이동하면서 인구 이동이 며칠 동안 있었는지 구해야 하므로
BFS로 이동 가능한 나라들을 이동하면서 인구이동을 해준다.
주의해야 할 점은 하루에 연합이 여러가지가 있을 수 있으므로 모든 좌표에서 BFS를 수행하며 인구이동을 해주고 모든 좌표에서 BFS이 끝난 뒤에 인구이동 날짜를 +1 해준다.

https://ongveloper.tistory.com/158?category=854013

26. (g5) 14503 로봇 청소기

문제

처음에 문제를 보고 청소기가 이동하면서 청소하는 칸의 개수를 구하는 문제이므로 DFS / BFS를 떠올렸다. 둘 다 적용 가능할 것 같다.
다만 청소기의 위치뿐만 아니라 방향도 고려해줘야 하기 때문에 DFS인자로 x,y,direction 3가지가 들어가야 한다.

• 4가지 방향에 따라 모두 진행해줘야 하므로 DFS 안에서 for문으로 4가지 모두 재귀를 돌려야 한다.
• 뒤쪽이 벽일 경우 작동을 멈추므로 재귀함수를 종료(리턴)해준다.
• 북,동,서쪽이 막혀 있고 남쪽이 막혀있지 않다면 방향을 유지한 채로 뒤로 한칸 이동한다.

https://sanghyu.tistory.com/55

27. (s3) 1057 토너먼트

문제

• 한 라운드가 진행될 때마다 지민이와 한수의 순번도 바뀌기 때문에 최신화 해야 한다.
• 최신화 할 때마다 서로 인접해 있는지 확인한다.
• 만약 인접해 있다면 해당 라운드가 구하는 값이다.

브루트포스

28. (g3) 16236 아기상어

아기상어는 상하좌우로 인접한 칸으로 이동 가능하고 자기보다 크기가 큰 경우에는 이동 불가능하며, 자기와 크기가 같은 경우에는 먹을 수는 없지만 이동은 가능하다.
이동 가능한 우선순위를 따져보면

1. 아기상어와 거리가 가장 가까운 순
2. 가장 위에 있는 물고기
3. 가장 왼쪽에 있는 물고기

따라서 BFS를 통해 자신보다 작은 상어가 없을 때까지 우선순위대로 이동하면서 이동한 시간을 측정한다.

https://luv-n-interest.tistory.com/973

29. (g4) 15685 드래곤 커브

문제

처음에는 드래곤 커브의 세대마다 이동 경로를 따져 BFS로 좌표를 찍어야 했는데 드래곤 커브를 좌표로 생각하기엔 너무 복잡했다.
따라서 좌표 말고 직선이 새로 생기는 진행방향으로 생각해보자.

• 0세대 : 0
• 1세대 : 0 1
• 2세대 : 0 1 2 1
• 3세대 : 0 1 2 1 2 3 2 1

1~2세대를 보면 1세대를 뒤집고 -> (1 0) -> 1을 더하여 -> (2 1) 뒤에 붙여줬다.
2~3세대를 보면 2세대를 뒤집고 -> (1 2 1 0) -> 1을 더하여 -> (2 3 2 1) 뒤에 붙여줬다.
4세대 부터는 다시 0세대와 동일하게 진행한다.

따라서 진행 방향을 저장하면서 드래곤 경로를 그려주고 다 그린 뒤에 네 꼭짓점이 모두 드래곤 코브의 일부인 사각형을 완전탐색으로 찾아준다.

구현

https://donggoolosori.github.io/2020/11/20/boj-15685/

30. (g2) 3101 토끼의 이동

문제

토끼가 이동할 수 있는 방향의 종류는

• U : 위
• D : 아래
• L : 왼쪽
• R : 오른쪽

점프한 횟수 K의 최댓값은 30,0000 이므로 한칸씩 이동하면서 수를 모두 더해도 시간초과는 안날꺼 같다.

근데 문제는 N의 최댓값은 100,000 이여서 배열을 선언하면 백만이다..정수가 4Byte 니까 400만 Byte 인데 메모리 제한이 128MB = 128,000B 으로 메모리 초과가 될 것 같다. 따라서 배열을 미리 선언하면 안되고 토끼가 이동하면서 그 칸이 무엇일지 찾으면서 더해줘야 한다.

배열을 유심히 보면 짝수 행은 대각선 왼쪽 아래로 수가 1씩 커지고 홀수 행은 대각선 왼쪽 아래로 수가 1씩 작아진다.

토끼가 이동한 칸의 행, 열에 따라 규칙에 맞게 칸에 있는 수를 구해 더해준다.

구현

https://littlesam95.tistory.com/22

31. (g3) 2146 다리 만들기

문제

먼저 섬들을 구별해야 한다. 왜나하면 육지에서 출발해서 바로 옆칸인 같은 섬인 육지를 잇는 다리가 생길 수 있기 때문이다. 다리는 다른 섬끼리 연결한다.

따라서 BFS나 DFS로 섬안의 육지를 돌면서 섬의 고유 번호를 육지마다 부여하고 BFS로 바다로만 이동하면서 다른 육지까지 도달할 때의 최단 경로를 구하면 된다.

32. (g3) 1937 욕심쟁이 판다

문제

판다는 본인이 위치한 칸 보다 더 많은 대나무가 있는 인접한 칸으로 이동한다.
일반적인 DFS와 BFS를 생각해봤는데 500x500에 출발 위치가 정해져 있지 않으므로 총 O(500x500x500)으로 시간초과가 우려된다.

따라서 DFS + DP 조합으로 풀어야 한다.
판다의 해당 위치까지 오면서 먹을 수 있는 대나무의 최대 양은 정해져 있다.
따라서 해당 위치를 중복되어 위치하게 되었다며 이전에 계산했던 값을 불러오고 (메모이제이션) 처음오는 위치라면 DFS를 다시 수행한다.

https://rile1036.tistory.com/70 (문제가 조금 바뀐거 같으나 기본 매커니즘은 비슷한거 같다.)

33. (s3) 2784 가로 세로 퍼즐

문제

6단어 중에 3가지를 뽑아 3x3 배열에 넣고 만든 배열로 6가지 단어를 만들 수 있는지 확인하면 된다. 만들 수 있다면 그 배열이 정답.

구현

https://blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222193836752&parentCategoryNo=&categoryNo=11&viewDate=&isShowPopularPosts=false&from=postView

34. (s4) 1015 수열 정렬

문제

문제 자체가 이해가 잘 안된다.. 블로그를 참고 했다.

• 주어진 배열 A에 대해서 배열 B와 수열 P는 다음과 같은 관계를 갖는다.
  $A[i]=B[P[i]]$

• 이때 배열 B가 비내림차순이 되도록 하는 수열 P를 찾아야 한다.
  B가 비내림차순의 배열
  찾아야 하는 것은 P

• 예시1을 보면
  $A[0]=2=B[P[0]]$
  $A[1]=3=B[P[1]]$
  $A[2]=1=B[P[2]]$

• 여기서, 배열 B는 비내림차순의 배열이기 때문에 배열 안의 값은 {1,2,3} 일 것이다.
  $B[P[2]]=1=B[0]$
  $B[P[0]]=2=B[1]$
  $B[P[1]]=3=B[2]$

• 위와 같이 된다면 배열 P와 B의 인덱스를 매칭 시킬 수 있다.
  $P[2]=0$
  $P[0]=1$
  $P[1]=2$

• 인덱스 순서대로 정렬하면
  $P[0]=1$
  $P[1]=2$
  $P[2]=0$

관계에 맞게 각 배열(A,B)을 만들고 마지막 수열 P을 구해 인덱스 순서대로 정렬하여 출력하면 된다.
$A[i]=B[P[i]]$

구현

https://suri78.tistory.com/271

35. (s3) 1748 수 이어 쓰기 1

문제

1부터 N까지 숫자를 하나의 문자열로 합쳐주고 자릿수를 구해주면 된다.
하지만 N의 크기가 최대 100,000,000이므로 하나로 합친뒤에 선형 탐색으로 자릿수를 구할 수 없다.
따라서 1부터 N까지 숫자들의 자릿수를 일의 자리, 십의 자리, 백의 자리인 수들의 수를 구해 더해주면 된다. (마지막에 0 오는 경우 주의)

구현

36. (s2) 5567 결혼식

문제

연결되어 있는 친구들로 이동하면서 친구의 수를 세어주면 된다.
BFS

37. (g5) 5582 공통 부분 문자열

문자

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR 인데
CA 는 CADA에 포함되는 문자열이다. 즉, 중복 연산되는 부분이 있으므로 dp를 사용한다.

$D[i][j]$ : A의 i번째 문자와 B의 j번째 문자를 끝으로 하는 부분문자열의 최대의 길이
$D[i][j] = D[i-1][j-1] + 1$

https://life-with-coding.tistory.com/203

38. (g5) 2589 보물섬

문제

문제 설명이 굉장히 이상하게 되어 있는 것 같다. 보물이 묻혀있는 위치를 알려주지않고 보물 2개가 묻혀있을 때의 최단거리를 구하라니.. 블로그를 참고해보니까 결론은 2개의 보물이 임이의 위치에 묻혀있을 때 최장거리를 구하라는 것 같다;;

뭐 아무튼

• 같은 대륙 안에서 보물 2개의 위치를 임의 지정하고 BFS로 최단거리를 탐색한다.
• 탐색한 결과 중에 가장 긴 값을 구한다.

가로 세로의 최대 크기가 50 이므로
최악의 경우 O(50C2x50x50)로 시간초과가 나지는 않을 것 같다.

부르트포스 + BFS

https://artjjong.tistory.com/35

39. (g2) 17837 새로운 게임 2

문제

각 말에 따라 이동하는 방향이 다르고 다음 칸이 무슨 칸인지, 다음 칸에 말이 있다면 어떤 말인지에 따라 상태가 달라지기 때문에 (복잡..) BFS로 풀기보단 구현하는 것이 나을 것 같다.
다만 턴 한번에 1번 말부터 K번 말까지 순서대로 이동하므로 queue에 push해준 순서대로 pop하여 이동하고 이동한 뒤에 위치와 방향을 다시 push 해주면 될 것 같다.

구현

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jhc9639&logNo=221827865930
여기 블로거는 queue 말고 일반 배열을 사용한듯

40. (s2) 4693 섬의 개수

문제

DFS나 BFS로 이동할 수 없을 때까지 이동하면서 섬마다 고유 번호를 부여하고 부여한 고유 번호까지를 구하면 된다.

41. (s2) 14889 스타트와 링크

문제

DFS를 통해 N/2 명을 뽑아 뽑힌 사람들 한팀, 뽑히지 않은 사람들 한팀으로 하여 시너지를 계산하고 두 팀의 차이가 가장 최소가 될 때의 값을 저장하면서 진행한다.

N/2 명만 뽑고 그 이상은 중복되므로 더 이상 뽑지 않아도 된다. (백트래킹)

https://cryptosalamander.tistory.com/61

42. (g3) 2931 가스관

문제

두 지점에서 각각 이동하면서 연결될 수 있는 경우를 따져보기에 코드가 너무 복잡해질 것 같다. 따라서 단순하게 BFS로 지워진 위치만 탐색하고 탐색된 위치를 1~7번 블록까지 모두 넣어 비교하면서 알맞은 블록을 찾는다.

https://chogyujin.github.io/2019/04/11/BOJ-2931%EB%B2%88-%EA%B0%80%EC%8A%A4%EA%B4%80/

43. (g4) 1339 단어 수학

문제

각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합한다.
주어진 단어를 더했을 때 자릿수에 따라 큰 자릿수부터 순서대로 큰 수를 넣어준다.
예를 들어 ABC가 주어지면, C는 1개, B는 10개, A는 100개 있는 것이다.
이에 따르면 ABC + BCD 인 경우는 A 100개, B 10+100개, C 1+10개, D 1개가 있는 것과 같다.
따라서 알파벳의 개수가 큰 차례대로 큰 수를 부여한다.
그리디

https://mapocodingpark.blogspot.com/2020/02/BOJ-1339.html

44. (g5) 1405 미친 로봇

문제

1. 한 방향으로 최대 14번 움직일 수 있기 때문에 (15, 15)에서 시작하고 판은 적어도 29*29여야 한다.
2. 한번 움직일 때마다 4방향 다 움직인다. (브루트포스)
3. 다른 방향으로 탐색하기 전에 전 방향에서 밟았던 칸을 다시 밟지 않은 칸으로 표시한다. (왜냐하면 다른 방향으로 이동할 경우도 수행해야 하기 때문)
4. N번 움직였을 경우 누적 확률을 더해준다.

DFS

https://jaimemin.tistory.com/724

45. (p5) 5373 큐빙

문제

큐브를 돌린 횟수 n과 돌린 방법이 주어지므로 각 횟수와 방법에 맞게 돌려 윗 면의 색상을 출력한다.
구현

46. (g4) 15684 사다리 조작

문제

가로선을 놓을 수 있는 모든 경우(브루트포스)마다 i번째가 i번째로 나오는지 판별해보는 수밖에 없다. 사다리를 놓을 수 있는 경우는 NxM = 10x((10-1)x30) = 2700개의 부분이 있고 이중에서 H 구간에 사다리를 놓고 각각 완전탐색을 하면 너무 많은 경우가 나온다.
따라서 완전탐색을 하면서 가지치기(백트래킹)를 해줘야 한다.
최대로 놓을 수 있는 사다리의 개수를 0부터 H까지 증가시키면서 최대 사다리 개수와 일치하는 값을 찾게 되면 나머지 경우의 수는 탐색할 필요가 없다.

https://velog.io/@statco19/boj-15684

47. (g1) 5214 환승

문제

최단경로이므로 BFS
하지만 찾아보니 BFS로 그냥 풀면 메모리 초과가 난다고 한다.
하이퍼튜브를 하나의 역으로 보고 풀면된다고 하는데 다음에 자세히 읽어보도록 하자.

https://yabmoons.tistory.com/260

48. (b3) 2490 윷놀이

문제

각 경우마다 0과 1의 개수를 구하여 도개걸윷모인지 판별한다.

구현

49. (g2) 17825 주사위 윷놀이

문제

(미해결)

50. (g4) 2573 빙산

문제

일년마다 빙산이 녹기 때문에 그래프를 최신화 해주고
DFS로 구별되는 빙산의 수를 구한다.

https://artjjong.tistory.com/44

51. (g1) 1799 비숍

문제

• 비숍을 놓을 수 있는 곳을 기준으로 DFS
• 양 대각선을 확인하면서 다음 비숍을 놓을 수 없는 곳은 놓지 않는다. (백트래킹)

하지만 찾아보니 백트래킹을 써도 시간초과가 난다고 한다.
체크판을 각 흰색, 검은색 부분만으로 이루어진 두가지 체스판이라고 생각해야한다. 왜냐하면 비숍의 특성상 각 영역에 영향을 주지 않기 때문

https://mygumi.tistory.com/289

52. (g3) 17822 원판 돌리기

문제

(미해결)

53. (g5) 3980 선발 명단

문제

이미 한 선수가 한 포지션을 채웠을 경우 다음 선수는 해당 포지션을 뛸 수 없다. 능력치가 0인 경우도 뛸 수 없다. (능력치의 합이 최댓값이 될 수 없으므로)

DFS + 백트래킹

https://velog.io/@mopevxw/BOJ-3980.-%EC%84%A0%EB%B0%9C-%EB%AA%85%EB%8B%A8-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9DFS-c

54. (s3) 2606 바이러스

문제

1번 컴퓨터와 연결되어 있는 모든 컴퓨터를 탐색한다.
DFS, BFS 모두 가능

55. (s2) 10819 차이를 최대로

문제

N의 범위가 최대 8로, 굉장히 작으므로 무식한 방법(?)도 가능하다.

dfs로 하나씩 넣으면서 이미 넣은건지 안넣은건지 확인하면서 진행한다.

https://excited-hyun.tistory.com/147

56. (g2) 17143 낚시왕

문제

한칸 움직일 때마다 상어를 이동시켜 격자판을 최신화 시킨다.

구현

57. (g1) 2014 소수의 곱

문제

1. 숫자를 중복 삽입하는 것을 방지하기 위해 map을 사용
2. 소수의 곱을 우선순위 큐에 입력하는데 우선순위 큐의 크기가 N을 초과하고 우선순위 큐 내 최댓값보다 현재 숫자가 더 크면 삽입하지 않는다.
   -> 우선순위 큐 내 최댓값보다 현재 숫자가 작으면 현재 숫자가 더 먼저 등장하므로 우선순위 큐에 넣는다.
3. 반복문을 탈출한 뒤 우선순위 큐의 top을 출력한다.

N이 최대 100,000으로 메모리 초과를 방지하기 위해 우선순위 큐를 최대크기를 제한하여 사용하는 것이 중요

https://jaimemin.tistory.com/986

58. (g5) 4811 알약

문제

각 알약마다 반으로 쪼개는 경우와 쪼개지 않은 경우 2가지가 존재한다.
모든 경우는 앞에서 알약들을 쪼갰는지 안쪼갰는지에 따라 다르므로 dp를 사용

$DP[W][H]$ : 온전한 알약이 W개, 반쪽짜리 알약이 H개 있을 때 만들 수 있는 문자열의 개수

• 쪼개진 알약이 없는 경우(H == 0)
  $DP[W][H] = DP[W-1][1]$

• 온전/쪼개진 알약모두가 있는 경우
  $DP[W][H] = DP[W-1][H+1] + DP[W][H-1]$

https://cpp-dev.tistory.com/68

59. (p5) 3895 그리고 하나가 남았다

문제

(미해결)

60. (s1) 1189 컴백홈

문제

BFS나 DFS로 거리가 K인 가짓수를 모두 구하면 된다.
다만 한번 지나친 곳은 다시 방문하지 않는다고 했으므로 지난 곳을 체크해가며 진행한다. (백트래킹)

61. (g5) 14891 톱니바퀴

문제

톱니바퀴 A를 회전할 때 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이

• 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.
• 같다면, 회전하지 않는다.

회전시킨 톱니바퀴의 번호와 방향에 따라 다른 맞닿은 톱니와 극이 다른지 같은지 판단하고, 다르다면 회전, 같다면 회전시키지 않는다.

구현