DFS - 깊이 우선 탐색, BFS - 너비 우선 탐색 DFS: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘그래프는 노드와 간선으로 표현되며, 두 노드가 간선으로 연결되어 있을 시 인접하는 것 DFS는 주로 스택 자료구조를 이용한다. BFS: 가까운 노드부터 탐색하는 알고리즘, 주로 큐 자료구조 사용 1012 유기농 배추 import sys sys.setrecursionlimit(10000) t = int(input()) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): # 깊이우선탐색 for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx=m or ny=n: continue elif graph[ny][nx] ..

그리디 알고리즘 Greedy = 탐욕 말 그대로 각 단계에서 가장 욕심을 부려서 최선의 선택을 하는 것 근데 이게 결과적으로 최선의 선택으로 통하는 경우 / 통하지 않는 경우가 있다. 당연히 그리디 알고리즘은 이 탐욕법이 통하는 문제에 쓰는 것 1417 국회의원 선거 오랜만에 알고리즘 하니까 머리가 안돌아간다... A = 다솜, B, C 총 3명의 후보가 있다 치고, A: 5, B: 7, C: 7 A+B+C = 19, 19/3 = 6.xxx.... 대충 반올림하면 7 이고 -5 하면 2 이렇게 생각해봤다 (사실 더 생각하기 귀찮았다) 근데 후보 1명이면 어칼려고....... 당연히 틀렸다. 그래서 다시 생각을 해봤다. A 기준 B, C 를 정렬하면 5 < 7, 7 한명을 매수하면 6 | 6, 7 다시 정..

2589 보물섬 import sys from collections import deque input = sys.stdin.readline s, g = map(int, input().split()) maps = [] for _ in range(s): maps.append(list(input())) dxdy = [(0,1), (0,-1), (1,0), (-1,0)] def bfs(i,j): q = deque() q.append((i, j)) visited = [[False]* g for _ in range(s)] visited[i][j] = 1 length = 0 while q: x, y = q.popleft() for i in range(4): dx = dxdy[i][0] dy = dxdy[i][1] nx..

모든 순간의 다익 + dp로 생각하면 될듯 11403 경로 찾기 import sys input = sys.stdin.readline N = int(input()) graph = [] for _ in range(N): graph.append(list(map(int, input().split()))) for i in range(N): for j in range(N): for k in range(N): if graph[j][k] == 1 or (graph[j][i] == 1 and graph[i][k] == 1): graph[j][k] = 1 for x in graph: for y in x: print(y, end = " ") print("") 1389 케빈 베이컨의 6단계 법칙 import sys input..

최단 거리 알고리즘 18352 특정 거리의 도시 찾기 import sys import heapq input = sys.stdin.readline INF = int(1e9) N, M, K, X = map(int, input().split()) graph = [[] for _ in range(N+1)] distance = [INF] * (N+1) for _ in range(M): a, b = map(int, input().split()) graph[a].append((b, 1)) def dijk(start): # 시작 노드 넣으면 q = [] heapq.heappush(q, (0, start)) # 힙큐에 스타트 노드 넣고 distance[start] = 0 # 당연히 거리는 0 while q: # 큐가 안..

정렬 정렬 알고리즘 5문제 풀기 백준 1181 단어 정렬 n = int(input()) words = [] for _ in range(n): words.append(input()) words = list(set(words)) words.sort() words.sort(key = lambda x:len(x)) for x in words: print(x) 백준 3273 두 수의 합 import sys n = int(input()) nums = list(map(int, sys.stdin.readline().rstrip().split())) nums.sort() x = int(input()) cnt = 0 left = 0 right = len(nums) - 1 while left < right: tmp = nu..

DFS/BFS 깊이 우선 탐색 / 넓이 우선 탐색 설명은 이전 글에 있으니 생략하겠다. 백준 2644 촌수계산 from collections import deque n = int(input()) p1, p2 = map(int, input().split()) m = int(input()) relat = [] res = [] visited = [False] * (n+1) for _ in range(m): x, y = map(int, input().split()) relat.append([x, y]) relat.append([y, x]) graph = [[]] for i in range(1, n+1): temp = [] for x in relat: if x[0] == i: temp.append(x[1]) gr..

그리디 그리디는 현재 순간에서 최고의 선택을 하는 알고리즘 1789 수들의 합 s = int(input()) hap = 0 ans = 0 while s >= hap: ans += 1 hap += ans if s < hap: break print(ans - 1) 1449 수리공 항승 n, l = map(int, input().split()) leak = list(map(int, input().split())) leak.sort() start = leak[0] cnt = 1 for x in leak[1:]: if x in range(start, start + l): continue else: start = x cnt += 1 print(cnt) 11501 주식 t = int(input()) for _ in ..

이진 탐색 데이터 탐색 시 매우 빠른 속도를 자랑하는 알고리즘이다. 이진 탐색을 보기 이전에 순차 탐색부터 알아보자. 순차 탐색 순차 탐색은 말 그대로 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법이다. 시간만 충분하다면 상관없지만, 코딩 테스트 같은 경우 순차 탐색을 사용할 시 시간 초과가 발생하기 쉽다. def sequential_search(n, target, arr): for i in range(n): if arr[i] == target: return i + 1# 현재의 위치 순차 탐색 이진 탐색은 반으로 쪼개면서 탐색하는 방법이라 생각하면 된다. 이미 정렬되어 있는 데이터에 사용 가능하며, 매우 빠르게 탐색을 할 수 있다. 위치를 나타내는 변수(포인터)가 3개가 필요한데, 시작점, 끝..

정렬 데이터를 특정 기준에 따라 순서대로 나열하는 것 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있다. 선택 정렬 가장 기본적인 정렬 알고리즘으로 가장 작은 것을 왼쪽으로 계속 보내는 (오름차순의 경우) 정렬 방식 arr = [7, 3, 5, 9, 6, 2] for i in range(len(arr)): min_idx = i for j in range(i+1, len(arr)): if arr[min_idx] > array[j]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] 시간 복잡도가 $O(N^2)$ 이기 때문에 원소의 개수가 많으면 효율적이지 못한 알고리즘이다... 삽입 정렬 특정한 데이터를 적절한 위치에 삽입한다는 의미의 삽입 정렬이다..