Developer/Algorithm29 [Algorithm] (이코테) DFS/BFS - BFS (Python/파이썬) ▶ 문제 설명 BFS(Breadth First Search) 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대다. 그렇다면 BFS는 실제로 어떤 방식으로 구현할 수 있을까? BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 그림과 함께 자세한 동작 방식을 살펴보자. 알고리즘의 정확한 동작 방식은 다음과 같다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 .. Developer/Algorithm 2023. 9. 2. [Algorithm] (이코테) DFS/BFS - DFS (Python/파이썬) ▶ 문제 설명 한 그래프에서 노드 1과 노드 7이 연결되어 있는 상황을 생각해보자. 인접 행렬 방식에서는 graph[1][7] 만 확인하면 된다. 반면에 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다. 그러므로 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다. DFS는 탐색을 위해서 사용되는 탐색 알고리즘이라고 했는데 구체적으로 어떻게 동작할까? DFS는 깊이 우선 탐색 알고리즘이라고 했다. 이 알고리즘은 특정한 경로로 탐색하다가 특정환 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처.. Developer/Algorithm 2023. 8. 30. [Algorithm] (이코테) DFS/BFS - 인접 리스트 예제 (Python/파이썬) ▶ 문제 설명 인접 리스트 예제 ▶ Code # 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연결된 노드 정보 저장 (노드, 거리) graph[0].append((1, 7)) graph[0].append((2, 5)) # 노드 1에 연결된 노드 정보 저장 (노드, 거리) graph[1].append((0, 7)) # 노드 2에 연결된 노드 정보 저장 (노드, 거리) graph[2].append((0, 5)) print(graph) ▶ Point 인접 리스트 정의 확인 Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 인접 행렬 예제 (Python/파이썬) ▶ 문제 설명 인접 행렬 예제 ▶ Code INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) ▶ Point 인접 행렬의 정의 확인 Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 2가지 방식으로 구현한 팩토리얼 예제 (Python/파이썬) ▶ 문제 설명 2가지 방식으로 구현한 팩토리얼 예제 ▶ Code # 반복적으로 구현한 n! def factorial_iterative(n): result = 1 # 1부터 n까지의 수를 차례대로 곱하기 for i in range(1, n + 1): result *= i return result # 재귀적으로 구현한 n! def factorial_recursive(n): if n Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 재귀함수의 종료 조건 예제 (Python/파이썬) ▶ 문제 설명 재귀함수의 종료 조건 예제 ▶ Code def recursive_function(i): # 100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.') recursive_function(i + 1) print(i, '번째 재귀함수를 종료합니다.') recursive_function(1) ▶ Point 재귀함수의 종료 조건 확인 Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 무한히 반복되는 재귀함수 예제 (Python/파이썬) ▶ 문제 설명 무한히 반복되는 재귀함수 예제 ▶ Code def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() ▶ Point 재귀함수의 정의 확인 Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 큐 구현 예제 (Python/파이썬) ▶ 문제 설명 큐 구현 예제 ▶ Code from collections import deque # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() # 다음 출력을 위해 역순으로 바꾸기 print(queue) # 나중에 들어온 원소부터 출력 ▶ Point .. Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) DFS/BFS - 스택 구현 예제 (Python/파이썬) ▶ 문제 설명 스택 구현 예제 ▶ Code stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 ▶ Point stack의 정의 확인 Developer/Algorithm 2023. 6. 2. [Algorithm] (이코테) Implementation - 문자열 재정렬 (Python/파이썬) ▶ 문제 설명 알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출련한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다. ▶ 입력 조건 첫째 줄에 하나의 문자열 S가 주어집니다. (1 Developer/Algorithm 2023. 3. 11. [Algorithm] (이코테) Implementation - 왕실의 나이트 (Python/파이썬) ▶문제 설명 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a 부터 h로 표현한다 c2에 있.. Developer/Algorithm 2023. 3. 11. [Algorithm] (이코테) Implementation - 시각 (Python/파이썬) ▶ 문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다 00시 02분 55초 01시 27분 45초 ▶ 입력 조건 첫째 줄에 정수 N이 입력된다.(0 Developer/Algorithm 2023. 3. 10. 이전 1 2 3 다음