Park Wooseong

Just Learn it

앞 내용(1~20)은 “알고리즘 PS 오답노트/팁”에서 찾아볼 수 있다.

21.

구현에서 어떤 조건의 만족 여부, 개수를 찾는 문제라면 문제를 만족하는 경우의 수를 제대로 파악해야 한다.

BOJ 2615

오목의 달성 여부를 판단하는 문제인데 좌상단에서 우하단으로 찾는아서 경우의 수를 줄인다는 것에 매몰되어 가로(→), 세로(↓), 우하 대각선(↘) 만 파악해서 문제를 풀지 못했다. 실제로는 우상 대각선(↗)도 존재한다.

22.

격자를 다루는 문제에서 실제로 보드를 전부 나타내야하는 상황이 아니라면 1 base 인덱스를 0 베이스 인덱스로 옮긴다던지, →↑ xy좌표를 ↓→ xy 좌표로 바꿀 필요가 없다.

BOJ 15685 문제는 직접 보드를 모두 나타낼 필요가 없고 x축의 방향을 변환시킬필요가 없다. 하지만 그게 더 편하지 않을까 싶어서 바꿨다가 더 헷갈려서 문제를 헤멨다. 처음부터 끝까지 동일한 축 방향을 유지해도 문제 풀이에 지장이 없다면 문제에 주어진 축 대로 풀자

23.

격자에서 높이가 $R$ 이고 너비가 $C$ 일 때 둘레의 길이는 $2(R-1)+2(C-1)$ 이다 곱하기가 아니다! 곱하기는 넓이다.

BOJ 16926 문제에서 둘레에 대해 계산해야 하는데 계속 곱하기로 해서 틀렸다.

24.

BFS를 여러개 할 때의 문제이다.

다음과 같은 예를 보자

1
2
3

1...
1..2
#...

각 번호는 2칸씩 움직일 수 있고 움직인 자리에 자신의 흔적을 남긴다고 하자. 번호는 낮은 숫자에서 높은 숫자의 순서로 진행한다. #는 벽이기에 그냥 2칸 이하의 공간에 모두 번호를 표시할 수는 없다. 그러므로 직접 땅을 밟아봐야 한다.

이럴 경우에는 큐를 활용하게 될 텐데 이때 반복의 순서는 다음과 같이 해야 한다.

  1. 1번의 좌표를 0스텝과 함께 한 큐에 넣는다. 이때 방문표시도 한다.
  2. 큐를 돌리며 스텝의 카운트를 늘리면서 BFS를 실행한다.
  3. 1번 좌표의 큐에 요소가 더이상 없으면 2번 좌표에 대해 1.과 같이 실행한다.

이것을 반복한다.

이 글을 왜 쓰냐면 BOJ 16920 문제에서 BFS를 하기 위해 한 큐에 좌표를 넣는데 낮은 숫자부터 큰 숫자의 순서로 진행되니까 한 큐에 모든 좌표를 숫자대로 넣고 각 좌표마다 정해진 거리만큼 BFS를 했다. 예를 들어

1
2
3

1...
1..2
#...

정답 풀이는 (0, 0), (1, 0)을 넣고 1번호에 대해 2칸만큼 BFS를 실행하는데 나는 (0, 0)에서 1번호에 대해 2칸만큼 BFS를 하고 (1, 0)에서 1번호에 대해 2칸만큼 BFS를 했다. 이러면 문제가 무엇이냐면 (0, 0)에 대해 BFS를 한 후에 다음과 같이 된다.

1
2
3

111.
11.2
#...

그럼 이제 (1, 0) 좌표에 대해 BFS를 해야 하는데 주변이 막혀있거나 이미 방문한 곳이라 방문을 하지 않게 된다. 이것을 해결하기 위해 다른 수단을 썼으나(방문했을 당시 step에 따라 방문 여부 결정) 시간초과가 났다.

25.

어떤 변수에 따라 문제풀이가 바뀐다면 그에 종속되는 변수의 값도 바로바로 바뀌어야 한다.

예를들어 r, c 값이 있다고 하자, 그 값들을 이용한 rr, cc가 있다고 하자.

그렇다면 r, c가 바뀌면 그때그때 rr, cc 값을 바꿔주거나 그때 그때 동적으로 구해야 한다.

BOJ 16935 문제를 풀다가 5, 6번 일때 움직여야 하는 delta값을 미리 정해놨는데, 행렬이 회전할 때마다 그 값도 바뀌어야 하는데 바꾸지 않아서 에러가 발생하였다.

26.

변수 재활용은 자제하자

BOJ 14442 문제를 풀다가 k를 조건으로 받고 k를 변경햇다. 하지만 마지막에 k에 대한 조건이 있었는데 변경된 k를 기준으로 하여 풀이에 실패하였다.

27.

문자를 숫자로 바꿀 때는 0에 조심하자.

보드에 str 로 되어있는 숫자를 조합하는 문제였다. 그런데 예를 들어 009를 뒤집으면 900이 되어야 하는데 10을 곱하고 해당 숫자를 더하는 방식으로 처리하여 9로 처리되는 일이 발생하여 문제를 틀렸다.

문제 조건에 따라

1
2
3

number = ''
number += board[r][c]

식으로 처리할지

1
2
3

number = 0
number = number * 10 + board[r][c]

식으로 처리할지 잘 판단하자. 일단 0이 있으면 첫 번째 방법이 안전하다.

BOJ 1025 문제를 풀다가 발생한 실수이다.

28.

뒤집으면 연산조건이 좁혀질 경우 (연산량이 줄어들 경우) 뒤집어서 연산하자.

  • BOJ 12931
    • 배열에 있는 값 하나를 1 증가시킨다.
    • 배열에 있는 모든 값을 두 배 시킨다.
  • BOJ 12919
    • 문자열의 뒤에 A를 추가한다.
    • 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

두 문제 모두 X를 위와같은 연산을 사용하여 Y를 만들 수 있냐는 식의 문제이다.

첫 번째 문제의 경우 1을 증가시키고 두 배 시키는 것은 모든 배열에 대해서 가능하다. 근데 뒤집어서 생각하면 정수를 1 증가시키고 두배 시킨다는 것은 모든 값을 2로 나누면 모든 값이 정수여야 한다는 뜻이다. 그러면 거꾸로 연산할 때 배열의 모든 값이 짝수거나 0이어야 한다는 조건이 생긴다. X -> Y로 갈 경우 모든 배열에 대해 연산이 가능해지는데 Y -> X로 할 경우 두 번째 연산을 할 때 모든 배열의 수가 짝수여야 한다는 조건이 생긴다.

두 번째 문제의 경우도 똑같다. X -> Y로 할 경우 모든 문자열에 대해서 연산이 가능한데 Y -> X로 할 경우 문자열의 맨 뒤에 A가 있어야 뺄 수 있고 문자열의 맨 앞에 B가 있어야 빼고 뒤집을 수 있다. 이렇게 연산의 조건을 만들어 연산을 줄일 수 있다. (문제의 핵심이기도 하다)

29.

True, False 가 재귀적으로 반복될 경우 비트연산을 고려하자

BOJ 1194 문제에서 6개의 조건이 True, False 냐에 따라서 판단하는 것이 있는데 6중 dict문을 쓴 후에 R X C 보드를 작성하였다. 예를 들어 다음과 같다.

visited[0][1][0][0][1][1][r][c]

하지만 이것은 visited[bit][r][c] 와 같이 작성될 수 있다. 이것이 훨씬 깔끔하다.

참고