Development Artist

도입 백준 알고리즘 분류-그리디 알고리즘 다섯 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 예시 : 거스름돈 최소 동전 수 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 ..

도입 백준 알고리즘 분류-그리디 알고리즘 첫 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 예시 : 거스름돈 최소 동전 수 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검..

도입 백준 단계별 풀기 DFS와 BFS 열한 번째, 마지막 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간..

도입 백준 단계별 풀기 그리디 알고리즘 첫 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검사 문제가 아니면 1번으로 돌아가서 반복 풀이 1...

도입 백준 단계별 풀기 최단경로 세 번째 문제이다. 풀이 1. s(var_start)에서 시작하여 g(point_one), h(point_two)를 무조건 지나서 도착지 후보 x1(list_dest[0], x2(list_dest[1], ...를 가는데, 최단거리를 구하는 문제. 2. 그렇다면 [s->g->h->x1] or [s->h->g->x1] 의 최단거리를 구해서 두개 중 출발지점->도착지점의 최단거리라면 results에 저장해준다. 코드 from sys import stdin from heapq import heappush, heappop INF = 1e7 def dijkstra(start): heap = [] heappush(heap, [0, start]) # 시작 노드 최단 경로 0 shorte..

도입 백준 단계별 풀기 최단경로 두 번째 문제이다. 풀이 1. 다익스트라 알고리즘을 사용한다. def dijkstra 함수를 정의하고, 매개변수로 start 할 꼭짓점을 받는다. 2. 그래프 정보를 가지는 변수(mat_table)를 선언한다. 단방향이 아닌, 양방향이기 때문에, 두 줄에 걸쳐서 넣어준다(윗 그림). 다음은 예제1의 입력이 주어졌을 때, 실제 만들어지는 mat_table 이다(아랫 그림). 3. 출발 꼭짓점으로 부터 해당 꼭짓점 까지의 weight값을 저장할 변수(list_shortest_dist)를 dijkstra함수 내부에 선언을 하고, 해당 변수를 return 하게 한다. 4. 1, v1, v2 지점을 dijkstra 함수의 매개변수로 주고, 그것에 맞는 list_shortest_di..

도입 백준 단계별 풀기 최단경로 첫 번째 문제이다. 다익스트라 알고리즘 [출처 : 위키 백과] 풀이 1. 다익스트라 알고리즘 사용할 것이다. dijkstra 라는 함수를 정의하고, 매개변수로 시작점(var_start)을 받는다. 2. heapq 라이브러리를 사용한다. heap에는 방문할 vertex의 정보들이 들어있다. [최단거리, vertex]로 구성이 되어 있다. 3. mat_table은 vertex간 어떻게 연결되어 있는지 인덱스값을 그 값에 해당하는 vertex(var_u)라고 두고, 해당 vertex에 연결된 다른 vertex(var_v)와 가중치(var_w) 정보를 넣어둔다. 4. list_shortest_dist는 시작점 index를 제외한 다른 index 들의 값을 INF(무한:infini..

도입 백준 단계별 풀기 DFS와 BFS 열 번째 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) 이..

도입 백준 단계별 풀기 DFS와 BFS 아홉 번째 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) ..

도입 백준 단계별 풀기 DFS와 BFS 여덟 번째 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) ..