백준 2206 벽 부수고 이동하기

일단 나는 벽을 부수지 않은 경우, 부순 경우를 각각 배열로 선언하고, 큐에도 (행, 열, 부순 여부) 를 넣어서 bfs를 돌렸다.

하지만 AC를 받은 후 내 코드 보다 훨씬 빠른 namnamseo님의 코드를 봤는데, 훨씬 간단하고 기발한 방법인 것 같아 여기 기록해둔다.

bfs를 두 번 돌리는데, 한 번은 시작점(1, 1)에서부터, 또 한 번은 끝점(n, m)에서부터 돌린다.
그렇게 돌려서 d1배열에는 시작점으로부터 각 점까지의 최단 거리, d2배열에는 끝점부터 각 점까지의 최단 거리를 구한는데, 이 때 벽을 만나게 되면 더 이상의 bfs는 하지 않기 때문에 벽을 만난 경우 벽 1개까지의 최단 거리를 구하게 된다.

그리고 나서 각 점까지의 최단 거리를 합쳐서 그 중 최소를 구하게 되면 최대 벽 1개를 부술 수 있을 때의 최단 거리가 구해진다!!

만약 벽이 여러개 있어서 경로가 없는 경우에는 처음 d1, d2배열을 큰 수로 초기화 해주는데, 적어도 d1, d2중 하나에는 큰 수가 갱신되지 않고 그대로 있게된다. 그래서 최종적으로 구한 값이 n * m보다 크면 -1을 출력해준다.

백준 9466 텀프로젝트, 재귀 주의 사항

dfs 재귀를 돌릴 때, visited값이 0이면 dfs함수를 재귀 호출하고, visited값이 1이면 flag값이 같은 경우만 dfs함수를 재귀 호출했는데...

if visited == 0

    ...

    dfs

    ....

if visited == 1

    ...

    dfs

    ...

이런 식으로 했다가 틀려서... 원인 찾는데 매우 힘들었다...

다행히 질문 검색에서

1

5

5 3 4 5 1

라는 반례를 올려주신 분이 계셨는데, 

저 반례를 가지고도 원인 파악하는데 시간이 엄청 결렸다.

내가 착각하고 있던 것이... 당연히 if문 하나로만 들어갈 것으로 착각했는데, 알고보니, dfs함수를 타고 들어가면서 visited값이 업데이트(0 -> 1) 되어 그 다음 if문의 dfs로 또 들어가게 되는 것이었다...

그래서 두번째 if문을 else if로 고쳐서 AC를 받았다...

아주 기본적인 것인데도, 원인을 찾지 못하고, 반례를 알고도 직접 출력을 해보며 디버깅해보고 나서야 겨우 원인을 파악했다... 반성하자...

firstDuplicate 문제

CodeFights라는 사이트의 이름이 Code Signal로 바뀐 것 같다.
여기에서 본 문제 중 firstDuplicate라는 문제가 있는데,
지금은 문제가 좀 바뀐 것 같지만, 내가 처음 봤을 당시 문제는 다음과 같다.

양의 정수 수열이 입력으로 들어오면, 그 수열에서 처음으로 중복되는 수를 찾아서 리턴하는 문제인데, 여기서 처음으로 중복되는 수는 두 번째로 나온 수 기준으로 가장 앞에 있는 수를 뜻한다.
2, 1, 3, 5, 3, 2 가 있으면 처음으로 중복되는 숫자는 2가 아니라 3이된다.
그리고 중복되는 숫자가 없으면 -1을 리턴해야 한다.

얼핏보면 쉬워 보이지만, 조건이 하나 더 있다. 바로 메모리를 추가적으로 사용하지 않고 풀어야 한다는 것이다... (지금 들어가보면 그 조건이 사라져 있지만 이 조건이 있어야 어렵고 생각해볼만한 문제가 된다.)

boolean 배열이라도 하나 더 있어야 어떤 수가 이미 이 전에 나왔는지 체크를 할텐데... 어떻게 추가적인 메모리를 사용하지 않고 풀라는 걸까?
생각하다가 도저히 모르겠어서 다른 사람들의 모범 solution을 봤다.

추가적인 메모리는 사용할 수 없어도 주어진 수열은 활용할 수 있는데, 이것을 어떻게 활용하냐면,
입력으로 들어오는 수열의 수가 양의 정수라는 점, 입력으로 들어오는 수의 크기는 1이상 수열의 길이 이하라는 점을 이용해서, 해당 수를 주어진 수열의 index(해당하는 수 - 1)로 하여 index에 해당하는 값을 음수로 만든다. 그래서 그 index에 있는 수가 음수이면 그 수는 이미 한 번 나왔던 수라는 것을 알 수 있다.
참고로 음수로 바꿔서 체크하므로, 어떤 수 x를 볼 때는 x의 절대값으로 봐야한다.

예전에 한 번 본 문제 같기도 한데... 아무튼 전혀 생각을 못했다. 비록 수열이 양의 정수로 구성되어 있을 때만 가능하긴 하지만 정말 멋진 풀이같다.

백준 3665 최종 순위

위상 정렬을 활용한다. graph와 indegree배열, queue를 사용한다.

문제의 예제와 같이 1등부터 시작해서 5등까지 팀이 5 - 4 - 3 - 2 - 1 인 경우,

그래프를 5 -> 4 -> 3 -> 2 -> 1 형태로 그리는 것이 아니라

5 -> 4 /  5, 4 -> 3 / 5, 4, 3 -> 2 / 5, 4, 3, 2 -> 1 처럼 각 정점에 도달하기 위해 거쳐야 하는 정점들을 모두 연결하게 그려서 각 정점이 서로 연결되어 있게(indegree도 그에 맞게 ++해주어야 한다) 한 후, 위상정렬을 진행한다.

indegree가 0인 것을 queue에 넣고, graph에 따라서 탐색하면서 다음 것의 indegree를 -1해주고 indegree가 0이면 queue에 넣어주는 식으로 진행한다.

만약 indegree가 0인 것이 없다면 모순이 있어 순위를 정할 수 없는 경우이고,

indegree가 0인 것이 동시에 여러개가 생긴다면 확실한 순위를 찾을 수 없는 경우로 볼 수 있다.

-----------------------

직접 구현해보니, 상대적 순위가 바뀌었다는 정보에 대해서 그래프를 수정해주는 것이 문제이다. 둘 중 누가 앞서 있는지도 알아야 하고, 그래프에 연결된 점을 일일이 다 보면서 찾아야 하는데 m이 25000이라... 그래프에 연결된 점이 최대 500개정도 된다고 하면 12,500,000번을 봐야 하는데,  테스트 케이스가 최대 100개라 시간초과가 날 위험이 있다.

그래서 vector를 사용하는 인접리스트 대신에 인접행렬을 써볼까한다. 일단 500 * 500이라 메모리는 문제없고, 인접행렬을 사용하면 일일이 다 볼 필요가 없고, 둘 중 누가 앞서 있는지도 쉽게 파악 가능하다.

아 참고로 인접리스트를 쓴다면, 소팅하여 이분탐색을 이용하는 방법도 있을 것이다.

---------------------------

계속 틀려서... 고민하다가 겨우 원인을 알아냈다.

바로 순위를 정할 수 없는 경우를 알아내는 부분에서 문제가 있었다. 나는 indegree가 0인 것이 없는지를 맨 처음에만 판단했다. indegree가 0인 것이 없으면 사이클이 생기는데, 사이클이 처음부터 생기지 않을 수도 있다. 일단 처음에는 indegree가 0인 것이 존재해서 queue에 들어가고, 계속 진행하다가 indegree가 0인 것이 없는 상황이 올 수가 있는 것이다... 

반례)

input

1

4

1 2 3 4

2

3 4

2 3

output으로 "IMPOSSIBLE"이 나아야 하는데, 나의 틀린 코드로 돌리면 "?"가 나왔다.

그래서 그 경우를 처리했더니 AC를 받았다... 

** 참고) 그리고 문제 관련 질문을 보던 중 확실한 순위를 찾을 수 없는 경우는 나올 수 없다는 답변이 있었는데, 실제로 그 답변을 잘 이해하진 못했고, 나도 정확히 증명은 못하겠지만 실제 예제나 반례를 만들어 보면서 확실한 순위를 찾을 수 없는, indegree가 0인 것이 동시에 여러개 생기는 경우를 만들지 못했었다.

백준 1915 가장 큰 정사각형

백준 Slack에서 고수분들이 말씀해주신 풀이를 적어보려 한다.

이 문제는 dp로 풀 수 있다.
주어진 배열에서 1로 된 가장 큰 정사각형의 크기를 구해야 하는데,
(r, c)를 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형과, (r+1, c)와 (r, c+1) 각각을 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형을 생각해보면,
d[r][c] = (r, c)를 가장 위의 가장 왼쪽으로 하는 가장 큰 정사각형의 한 변의 길이
라고 할 때,
d[r][c] = min(d[r+1][c], d[r][c+1]) + 1 이라고 볼 수 있을 것 같다.
하지만 d[r+1][c]와 d[r][c+1]이 같은 경우, 가장 오른쪽 아래 부분도 추가로 확인해봐야 한다. 가장 오른쪽 아래 부분이 0이면 d[r][c] = min(d[r+1][c], d[r][c+1]) 이 되는 것이고, 1이면 min(d[r+1][c], d[r][c+1]) + 1이 될 것이다.

시간복잡도는 O(N^2)정도가 나올 것 같다.

백준 8394 악수

처음에는 규칙을 찾아보려 했지만... dp로 풀 수 있다.
d[n] 을 사람의 수가 n명일 때, 악수를 하는 방법의 수
라고 하면
d[n]은 맨 끝의 사람이 악수를 하는 경우와 안 하는 경우로 나눌 수 있다.
악수를 하는 경우는 d[n - 2]가지 경우의 수가 있을 것이고,
악수를 하지 않는 경우는 d[n - 1]가지의 경우의 수가 있을 것이다.
d[n] = d[n - 1] + d[n - 2]가 된다.

C, switch, case 문에서 || 연산자

백준 11723 집합 문제를 풀다가
swtich case문을 사용하면서 ||(or)연산자를 사용했는데

아래와 같이...
case 'a' || 'b':
내가 의도한 바는 'a' 또는 'b'인 경우에 그 케이스 문 안의 코드를 실행하는 것이었는데, 'a'가 오든 'b'가 오든 해당 case문 안으로 들어가지 않길래 찾아봤더니...

https://stackoverflow.com/questions/13226124/switch-case-with-logical-operator-in-c

저 경우에는 'a' || 'b'가 계산이 되어 True(1) 값으로 설정되기 때문에, 즉 case 1: 이 되기 때문에 'a', 'b'값 모두 통과를 할 수 없게 되는 것 같다.

----
아 그리고, switch문 안에서 case를 벗어난 부분에 코드를 입력하면 내려가면서 실행될 줄 알았는데 그렇지 않다... case문 밖에 있는 코드는 실행되지 않는다.
swtich(x) {
  case 1:
    ......
    break;

  (x가 1이 아닌 경우에도 이 부분에 입력된 코드는 실행되지 않음)

  case 2:
    .......
    break;
}