백준 - 현수막백준의 섬 개수 세기 문제와 동일하다.

백준 - 우수 마을거의 다 풀었는데 점화식에서 사소한 실수를 했다.특정 노드가 꺼져 있을 때 최대 값은 그 자손들이 각각 켜져있을때 혹은 꺼져있을 때의 최대값을 더해주면 된다.

백준 - 트리와 쿼리기초적인 트리 dp문제다. 그래프를 만들고 dp 배열을 만드는데 dpi는 i를 루트로 하는 서브트리에서 루트를 포함한 정점의 개수라고 정의했다. 그러면 리프노드에서 1을 반환하면 된다.

백준 - 욕심쟁이 판다그냥 DFS를 다 돌리면 시간 초과가 난다.이번에도 역시 점화식이 중요했는데, dpi를 (i,j)에서 출발해서 갈 수 있는 루트 중 가장 긴 루트의 길이라고 하자. 그러면 이미 dpi는 최적해라는 것이 보장되었기 때문에, 다른 지점에서 길을 찾다가

백준 - 사다리 조작

백준 - 효율적인 해킹주어진 입력의 방향을 바꿔서 그래프를 만들었다. 그래서 1이 몇개의 컴퓨터를 지나냐 이런식으로 했고, 그 정답은 HashMap에 저장했다.크게 바뀐건 없다. 방향을 원래 입력대로하고, 지나갈때마다 arrnode++해줬다. 하지만 이 코드도 통과했지

백준 - 바이러스백준 - 연결 요소의 개수와 동일한 문제다.

백준 - 연결 요소의 개수본질적으로 백준 - 섬의 개수 문제와 동일하다.그래프를 코드로 나타내는데 두 가지 방법이 있는데 하나는 이차원 배열을 사용하는 것이고 하나는 리스트를 담는 배열을 이용하는 것이다. 리스트를 담는 배열을 만드는 것에도 익숙해지자.

백준 - 연구소효율성이 좋지 않았다. 이유는 combination 부분이었다.combination 부분을 이진법하는듯 방법으로 바꾸었다. (탈출조건에 처음에는 그냥 curPos >= emptySpaces.size() 라고 했다가 틀렸다. curPos가 마지막에 넘었더라

백준 - 유기농 배추백준 - 섬의 개수 문제와 거의 동일하다.

백준 - 섬의 개수dfs를 한번 돌면 한 섬을 다 표시하므로 전체에 대해 dfs를 돌려주면된다. 다만 방향이 4방향이 아니라 8방향이다.

백준 - 내리막길예전에도 다른 사람의 풀이를 보고 풀었더니 풀지 못했다. 이번에 확실히 정리하자.상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우, 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합한다.한 번 방문해서 경로의 수를 갖고 있다면 그대로 반환하고,

프로그래머스 - 여행경로파이썬 알고리즘 인터뷰와 리트코드의 일정 재구성과 동일한 문제이다. 하지만 풀이가 정확히 기억나지 않아 다소 비효율적으로 풀었다.애초에 딕셔너리에 넣을 때 sort 해서 넣으면 나중에 하나씩 정렬해줄 필요가 없다. 경로가 끊기는 경우가 없기 때문

프로그래머스 - 네트워크 def dfs(i, visited, computers): visitedi = True for k in range(len(computersi)): if computersi == 1 and not visitedk:

이진 탐색 트리(BST) 노드 간 최소 거리이진 탐색 트리이므로 차이가 가장 적게 나는 것은 부모노드와, 왼쪽 서브트리 중 가장 오른쪽 그리고 오른쪽 서브트리중 가장 왼쪽의 것이다.스택을 이용한 DFS 풀이이다.

코스 스케줄각 코스 별로 순환하는 사이클이 없는지 검사하는 것이다. 하지만 이렇게 풀면, 만약 순환이 아니더라도 복잡하게 서로 호출하는 구조로 그래프가 구성되어 있다면, 불필요하게 동일한 그래프를 여러 번 탐색하게 될 수도 있다. 따라서 한 번 방문했던 그래프느느 두

일정 재구성여러 일정이 있을 경우 사전 어휘순으로 방문해야하므로, 그래프를 만들고 나서 정렬을 해준다. 하지만 무조건 사전 어휘순으로 방문하려고하면, 방법이 나오지 않을 수도 있다. 따라서 A에서 갈 수 있는 곳이 여러 곳 있을 때, 사전 어휘순으로 하나씩 시도해보아야

부분 집합

조합a,b,c,d가 있으면 a를 넣고나서, b부터 또 보는 방시깅다. 여기서 중요한 점은 result.append(elements)라고 하면, dfs가 종료되고 elements.pop()이 있기 때문에 result에 있는 elements도 영향을 받을 수 있다는 점이다

트리의 부모 찾기DFS예전에 풀었던 문제인데도 기억이 잘나지 않아서 트리를 구현해야하나 싶었다.우선 2차원 리스트로 연결되어 있는 것들은 다 이어준다.그리고 DFS를 돌리는데 시작점이 분명하므로, 그 시작점에 연결된 것들은 만약 parents에 부모가 저장되어 있지 않