hyeonzzz's Tech Blog

최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘 다익스트라 최단 경로 알고리즘 : 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선 : 0보다 작은 값을 가지는 간선 현실 세계의 간선은 음의 간선으로 표현되지 않으므로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다 그리디 알고리즘으로 분류된다. ('가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문) 알고리즘의 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블..

다이나믹 프로그래밍 (동적 계획법) : 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 피보나치 수열 재귀 함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) 문제점 : f(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어난다 시간 복잡도 : O(2^N) 동일한 함수가 반복적으로 호출된다. f(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다. 다이나믹 프로그래밍 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법(캐싱)으로 구현 (탑다운 방식) # 한 번 계산된 결..

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 정렬되지 않은 리스트에서 주로 사용한다 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다 순차 탐색 코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기) return -1 # 원소를 찾지 못한 경우 -1 반환 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") inpu..

# N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력 받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문 def dfs(x, y): # 주어진 범위를 벗어나는 경우에는 즉시 종료 if x = n or y = m: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드 방문 처리 graph[x][y] = 1 # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출 dfs(x - 1, y) dfs(x, y - 1) dfs(x..

BFS BFS : 가까운 노드부터 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 부른다. BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 큐 자료구조에 기초해 구현한다. O(N)의 시간이 소요된다. 일반적인 경우 수행 시간이 DFS보다 좋은 편이다. BFS 코드 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visite..

DFS DFS : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색이라고도 부른다. 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색한다 그래프 노드(정점)와 간선으로 표현된다 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 두 노드가 인접한다 = 두 노드가 간선으로 연결되어 있다 그래프를 표현하는 2가지 방식 인접 행렬 : 2차원 배열에 각 노드가 연결된 형태를 기록 INF = 99999999 # 무한의 비용 선언 #2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) [[0, 7, 5], [7, 0, 9..

자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입 : 데이터를 삽입 삭제 : 데이터를 삭제 오버플로 : 자료구조가 수용할 수 있는 데이터의 크기를 벗어나 넘쳐흐를 때 발생 언더플로 : 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생 스택 박스 쌓기와 비슷하다 선입후출, 후입선출 구조 스택 코드 stack = [] # 삽입 삭제 수행 stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출..

그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 ※ 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다! ※ 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다 거스름돈 문제 예시 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라 (N은 항상 10의 배수이다) 해결방법 가장 큰 화폐 단위부터 돈을 거슬러 준다 예를 들어 N이 1,260이라면 500원 2개 100원 2개 50원 1개 10원 1개 파이썬 코드 n = 1260 count = 0 #큰 단위의 화폐부터 차례대로 확인 coin_types = [500, 100, 50, 10] for coin in coin_typ..

정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다 N=10인 경우 1. 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다 2. 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꾼다 3. 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다 4. 이러한 과정을 반복하면 정렬이 완료된다 선택 정렬 python 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if a..