WEEK03 알고리즘 3주차 후기

결국은 상문제가 5개임에도 불구하고 혼자 풀어보겠다고 하다가 다 못풀어버렸다... 알고리즘의 핵심인 bfs dfs 주여서 활용 문제가 많았다.

1. 이진 검색 트리
   • 숫자 하나씩 받을 때마다 이전것보다 작으면 왼쪽 크면 이전꺼랑 비교하고 그 부모랑 비교하고 어쩌구 해서 어렵게 생각했었는데 결국 안풀려서 답을 봤다. 이진 트리의 특성인 "자식도 이진트리"라는것으로 재귀를 예상했어야 했다. 루트보다 작은건 왼쪽 이진트리로 재귀 부르고 큰건 오른쪽으로 재귀 부르는 방식을 써야 한다.
   • 재귀를 반복문으로 바꿀 때는 해야하는걸 스택에 넣어놓고 while문 시작으로 돌아올 때 마다 하나씩 꺼내면 된다. 이 때 재귀 호출했던 순서랑 반대로 넣어야 똑같이 나온다. (재귀 때는 먼저 호출했던게 스택에 넣으면 후입선출로 나중에 나오기 때문에)
2. 최소 스패닝 트리
   • 유니온 할 때 parent[parent[node1]] = get_parent(node2)가 아니라 parent[get_parent(node1)] = get_parent(node2) 해야 함. 전자는 재귀로 타고 올라가지 않기 때문에 조상의 부모는 바뀌지 않을 수 있음. get_parent 함수로 타고 올라가면서 부모의 부모의 부모의 .... 최상위 부모를 바꿔야 함.
3. 미로 찾기
   • bfs는 큐로 구현해야 한다. 앞에서부터 꺼내야 너비가 우선이 된다.
   • 최단 거리같이 매번 움직일 때마다 따로 뭔가 저장해야 하면(전역 변수로 cost에 저장하면 최단거리가 아니라 움직인 모든 횟수가 저장된다) 큐에 넣을 때 튜플이나 리스트로 묶어서 같이 넣자.
   • 잘못 가서 돌아온다고 해도 visited에서 pop할 필요는 없다. 어쨌든 이미 가보고 틀린 길인걸 아는 것이기 때문에.
   • 스택이나 큐 구현할때는 deque를 쓰는데 일반 리스트보다 O(1)로 압도적으로 빠르다. 자세한 사용법은 여기

   	from collections import deque
   	deq = deque()

   • 줄글로 받은 연속 숫자를 한 글자씩 떼어 배열에 저장할때는 [int(x) for x in stdin.readline().rstrip()]
   • visited를 방문한 것대로 집어넣고 if (x,y) in visited 하면 O(n)의 시간이 걸리기 때문에 시간초과가 난다. 2차원 배열에 True/False로 저장해서 해당 배열값을 조회하면 바로 알 수 있게 해야 한다.
   • 배열 초기화할 때 visited = [[False]*m]*n로 만들면 visited[x][y] = True 했을 때 한 열이 통채로 다 True로 바뀌어버린다. n개의 열이 [[False]*m]이라는 동일한 리스트 객체를 가리키도록 생성되기 때문이다. 올바르게 생성하려면 visited = [[False]*m for _ in range(n)]라고 해야 한다.
   • BFS가 최적으로 작동하려면 같은 점이 2번 이상 큐에 들어가지 않도록 해주어야 시간을 아낄 수 있다. 출발점부터 어떤 점까지 가는 길을 하나 찾았다면 그 점까지 가는 다른 길이 더 있더라도 이미 처음에 찾은 길보다 더 길거나 같을 테니 필요가 없어진다. 따라서 어떤 노드까지 가는 길을 하나 찾는 "즉시" 그 노드에 방문 표시를 해줘야 하고 "어떤 노드까지 길을 찾았다"의 다른 표현은 "그 노드의 앞 노드에서 그 노드에 대해 if문을 검사해서 True가 나왔다"는 말이다. 즉 방문 표시는 큐에서 꺼냈을 때가 아니라 큐에 넣을 때 해야 한다. - 백준의 질문 게시판을 참고했는데 100퍼센트 완전하게 이해가 간건 아니지만 앞으로 이렇게 해야겠다.
4. 특정 거리의 도시 찾기
   • 이렇게 방향이 있어서 s에서 시작할 때 e들을 모두 찾으려고 순회를 돌아야 한다면 딕셔너리에 저장해서 도착지만 순회를 도는게 훨신 빠르다.
   • 모든 노드가 visited로 되면 break 걸리게 했었는데 이렇게하면 틀린다. break가 아니라 continue를 걸어야 한다. 또한 덱에 넣을 때 방문 처리를 하기 때문에 방문처리에는 모두 방문했다고 됐어도 덱에는 아직 안 뺀게 남아있을 수 있다. (반례 4 4 2 1/1 2/1 3/2 4/3 4)
5. 줄 세우기
   • 위상정렬 할 때는 맨 처음에 차수가 0인 모든 값을 큐에 넣어주지 않으면 틀린다. 하나만 넣고 시작했다가 틀렸음.
   • 간선이 방금 끊어진 노드만 진입차수가 새롭게 0이 됐을 가능성이 있으므로 모든 노드를 다 순회하면서 찾을 필요는 없다. 현재 노드로부터 도착할 수 있는 노드들만 보면 된다.
   • 비슷하게 모든 관계가 담긴 배열을 순회하면서 시작점이 지금 노드인 원소를 찾을 필요 없이 해당 노드를 인덱스로 가지는 원소에 배열 형태로 도착할 수 있는 모든 노드를 모아서 넣어두자.
6. 최소 비용
   • 이 bfs는 최소 거리랑 다르게 꺼낼 때 방문처리 해줘야 한다. 그렇게 하지 않으면 출발점에서 바로 옆에 3이 있어서 이미 스택에 들어가 있기 때문에 출발점 바로 옆의 [1에서 3]은 못 가게 된다. 원래의 "최소 거리"는 더 가까운 3이 있으면 그걸 선택하는 거였기 때문에 넣을 때 해주는게 중복 방지에 도움되는데, 이건 요금이라서 다르게 풀어야 한다.
7. 임계경로
   • 나는 노드 n까지 가는데 걸린 시간을 노드랑 같이 묶어서 큐에 넣어놓고 뺄 때마다 더하려고 했는데 그러면 진입차수가 0이 되기 전의 시간들은 모두 사라지게 된다. (진입차수가 0이 아니면 큐에서 빼서 걸린 시간을 더한 새로운 시간을 다시 큐에 넣지 않기 때문에) 그래서 최대시간 배열을 따로 만들어놓고 [현재까지의 시간+next에 가는데 걸리는 시간]이 지금까지의 그 노드의 최대 시간보다 크면 갱신해주기로 했다.
8. 토마토
   • 풀이 자체는 어렵지 않은데 3차원 배열로 인덱스에러를 무진장 주는 문제... 3차원 배열을 만들어서 arr[a][b][c]를 하면 abc는 xyz가 아니라 zxy이다!
9. 숨바꼭질
   • while문 돌 때마다 x-1, x+1, x*2일 때 스택에 넣고 방문처리하는 같은 일을 반복하면 따로 if문 세번 쓸 필요 없이 for el in (x+1, x-1, 2*x)로 처리할 수 있다. 고급 스킬.
10. 경쟁적 전염
    • 시험 시간 내에 해결 못하고 3분 지나서 맞음.. s가 0일 수도 있는걸 체크하지 못했더니 0일때 while문이 무한루프를 돈다. 마찬가지로 타겟자리에 뭐든 들어가면 브레이크 걸리게 해놨지만 시간이 지나면 내가 생각했던 값은 아니어도 어쨌든 그 자리에 뭐든 들어가긴 할거니까 잘못된 값이 출력되는 거였다.
    • 힙큐에 이차원 배열을 넣으면 배열 첫번째 기준으로 정렬한 뒤 첫번째 값이 같으면 두번째 기준 정렬, 그것도 같으면 세번째....로 넘어간다는 사실! 난 모르고 일일이 정렬해줬는데..
11. 트리
    • 동기의 풀이에서 (ridx-i_s)가 뭔지 한참 궁금했는데 inorder 그래프에서의 루프인덱스에서 inorder 그래프의 시작점을 빼면 inorder 그래프에서 왼쪽 자식의 수가 나오는 거였다! 천재.... 그러면 p_s에 이걸 더하면 postorder 그래프에서 왼쪽자식으로 넘길 배열의 끝 인덱스가 된다.