Basic 2/2 (60X, Graph, BFS, Tree)

https://code.plus/course/42

2023.01.06 - Basic 2/2 600: Graph, BFS Start.
2024.06.26 - 601 그래프 1 (연습) DONE.
2024.06.27 - 600 그래프 1 & 610 BFS DONE. - 다익스트라 (dijkstra) 알고리즘 (다이나믹 프로그래밍) 공부

2024.06.27 - Baekjoon 1707 이분그래프

BFS로 탐색.
(1-2-3) (4-5) 와 같은 두개의 그래프의 합집합 구성도 이분 그래프임에 유의.

2024.06.27 - Baekjoon 1261 알고스팟

{33188 KB, 72ms} 우선순위 큐 heapq를 활용한 다익스트라 알고리즘으로 해결
다익스트라 알고리즘 참고https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

2024.06.26 - Baekjoon 16947 서울 지하철 2호선

PyPy3 {212076KB, 3204ms}
Edge Node와 Cycle Node를 찾은 후에 접근하는 방식으로 해결
Cycle을 찾는 알고리즘을 비효율적으로 짠것같은데, 확인해보니 DFS와 stack을 활용하면 빠르게 찾을 수 있는 듯함.

2024.06.26 - Baekjoon 16947 서울 지하철 2호선

DFS 재귀를 호출하는 사람들은 재귀 호출 횟수 제한을 풀고, 해결하는 모습.

2024.06.24 - Baekjoon 1707 이분그래프 (시간초과)

BFS로 구성했는데, 6% 시간초과

2024.06.21 - Baekjoon 1967 트리의 지름 (시간초과 해결)

1) 임의의 노드에서 제일 먼 노드 찾기 (그 점이 지름의 끝 점 중 하나)
2) 그 노드에서 제일 먼 노드 = 지름
n=1 일 때 고려.
Python3 {37068 KB, 124 ms} 로 해결

2024.06.21 - Baekjoon 1167 트리의 지름

Baekjoon 1967 과 동일한 문제
입력 구조만 변형.

2024.06.21 - Baekjoon 11725 트리의 부모 찾기 (시간초과 해결)

루트 (모든 노드들의 부모)가 1이라는 가정을 활용하여 전체 트리를

부모 > 자식 방향으로 탐색하여 부모-자식 경로를 저장한 후 마지막에 출력. set() 활용

{66140 KB, 380ms} 통과!
내 4달 전 제출 코드를 확인해보니, dfs로 똑같은 구성을 했는데 recursion error 때문에 실패했었음. dfs> bfs로 바꾸어 해결된 예로도 볼 수 있겠음.

2024.06.21 - Baekjoon 1967 트리의 지름 (시간초과)

모든 노드를 각각을 중심하는 원의 지름을 찾는 BFS 알고리즘
시간 초과
모든 노드를 각각을 원의 중심으로 둘 필요가 있는가? No

2024.06.21 - Baekjoon 11725 트리의 부모 찾기 (시간초과)

BFS로 접근, PyPy3/ Python3 모두 시간초과

2024.06.21 - Baekjoon 11725 트리의 부모 찾기 (시간초과)

BFS 찾은 경로를 저장해두고, 중복 제거
시간초과

2024.02.23 - Baekjoon 2003: 수들의 합 2 - 두개의 포인터를 사용하는 문제. 두 개의 for 문을 사용한 경우에는 0.5초에 대하여 시간초과. - 애벌레가 기어가는 것 같은 모습으로 리스트의 합을 확인하는 알고리즘.

2024.01.23 - Baekjoon 14226, 이모티콘 - 시간초과

2024.01.23 - Baekjoon 14226, 이모티콘 - visited[display][clip] 이차원 방문 배열을 통해서 시간초과 확인.

2024.01.22 - Baekjoon 11725 트리의 부모 찾기 > dfs로 진행시 RecursionError (너무 깊은 탐색)

2024.01.21 - Baekjoon 13549 숨바꼭질 3,

PyPy3 = {115748 KB, 168ms}
Python3 = {35756 KB, 144ms} 로 통과.
순간이동이 0초여서 가장 먼저 조건을 확인하고 방문표시하는 것이 아이디어.

2024.01.21 - Baekjoon 13549 숨바꼭질 3 예시.

5>10(0)>9(1)>18(1)>17(2) : 2초

2024.01.16 - Baekjoon 1697 숨바꼭질, 쉬운 BFS. 35664KB, 140ms

2024.01.17 - Baekjoon 13913 숨바꼭질, 쉬운 BFS. 현재 노드가 어디서 왔는지 저장하기 위해서 dictionary 자료형을 사용. 처음에 parent=[0]*(100001) 로 list 자료형을 사용해서 접근했는데, 수가 많아지면 시간초과. Hash를 사용하는 dictionary 자료형을 통해서 보다 빠르게 해결. 49968KB, 212ms. vs 동일한 BFS 문제 Baekjoon 1697, 140ms. 꽤 효율적으로 경로를 저장하여 연결, 출력함.

2024.01.15 - Baekjoon 1991 트리 순회: DFS로 접근. 중위순회에 대한 개념을 처음에 잘못 이해하여 구현 실패. 인터넷 검색을 통해서 이해한 후, 보다 간결한 dfs로 구현. postorder 와 preorder 의 개념은 제대로 구현했으나, 좀더 간결하게 inorder 함수에서 출력 순서만 변경한 형태로 구현할 수 있겠음.

2024.01.15 - Baekjoon 1991 트리 순회 입출력.

2024.01.15 - 중위순회 개념: https://codingstarter.tistory.com/7

2024.01.14 - Baekjoon 13023 ABCDE: dfs로 접근. 5개의 노드를 깊이 탐색한 순간 종료되므로 dfs가 어울림. "next not in friends_list" 보다 visited 의 값 변환으로 탐색하면 더욱 빠를 것.

2024.01.14 - Baekjoon 7576 토마토 - BFS que의 초기값으로 현재 토마토의 [x 좌표, y좌표, 날짜] 를 저장하는 방식으로 최종 날짜를 확인. que를 모두 확인했음에도 tomato에 안 익은 토마토 '0'이 남아있으면, 모두 익는 것이 불가능한 상황이므로 -1 출력.

2024.01.14 - Baekjoon 7576 토마토: 모두 익는 것이 불가능한 경우 예시.

2024.01.12 - Baekjoon 1065 한수, 쉬운 수학문제

2024.01.13 - Baekjoon 1712 손익분기점, 쉬운 수학문제.

2024.01.08 - Baekjoon 20920 영단어 암기는 괴로워, 파이썬의 dictionary 자료형과, lambda 정렬 조건을 잘 활용.

여러조건이 포함된 내림차순 정렬을 위해서 "lambda x: x[1], reverse =True" 대신 "lambda x: -x[1]" 을 사용하는 것이 포인트!

2024.01.11 - Baekjoon 1003 피보나치 함수, 쉬운 DP 문제.

2024.01.08 - Baekjoon 16929 Two Dots, 쉬운 BFS. 연결된 점을 모두 탐색해가면서, 만약에 현재 점의 주변(상하좌우)에 같은 색깔이 점이 이미 연결되어 있으면, 사이클이 형성되어 있다는 아이디어. 34112KB, 64ms.

인터넷의 흔한 풀이는 DFS로 구현. DFS의 경우 스텝수를 세어서 4이상이 되면 사이클이 확인되는 것을 조건으로 구현.
BFS/DFS 외에 중요한 부분은 언제 사이클이 형성되는 것 인가의 조건을 코딩으로 잘 표현하는 것.

2024.01.08 - Baekjoon 16929 Two Dots, 쉬운 BFS. 연결된 점을 모두 탐색해가면서, 만약에 현재 점의 주변(상하좌우)에 같은 색깔이 점이 이미 연결되어 있으면, 사이클이 형성되어 있다는 아이디어.

EX1. 사이클 한개가 형성되면 조기종료되는 것 확인.

EX2. 사이클 한개가 형성되면 조기종료되는 것 확인.

2024.01.07 - Baekjoon 2178 미로탐색, 방문하지 않은 장소에 도달할 수 있는 최소 숫자를 기록해나가는 BFS 방식.

2024.01.07 - Baekjoon 2178 미로탐색, 방문하지 않은 장소에 도달할 수 있는 최소 숫자를 기록해나가는 BFS 방식. - 과정 출력.

2024.01.07 - Baekjoon 2667 - 단지번호붙이기, 쉬운 BFS. 연결된 집을 찾는 것 = 연결된 노드를 찾는 것.

2024.01.06 - Baekjoon 11724 연결 요수의 개수, 간단한 BFS 문제 import sys해야 시간초과 통과

2024.01.06 - Baekjoon 7562 섬의 개수, 간단한 BFS 문제. graph에 해당 2D 좌표 노드에 도달 할 수 있는 최소 스텝을 기록하여도 적당함. 말을 옮기는 문제 자체가 BFS와 연관이 큰 것을 그림을 통해서 이해할 수 있음.

2024.01.06 - Baekjoon 4963 섬의 개수, Graph와 BFS 문제

2024.01.06 08:18 - 그래프 공부, 문어박사 IT편의점

https://www.youtube.com/watch?v=kkZFEwoZ3fA

2024.01.06 - BFS vs DFS

https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-1260%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

2024.01.06 08:42 - Baekjoon 1260; DFS와 BFS

BFS 구현에는 Que가 필요.

Page updated

Google Sites

Report abuse