WoohyunKing의 개발 성장일지

BFS는 Breadth-First Search, 너비 우선 탐색이라고 부르며 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 Queue 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 알고리즘의 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 너비 우선 탐색 알고리즘인 BFS는 Queue 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현 함에 ..

DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프의 기본 구조: 노드(Node) or 정점(Vertex) 간선(Edge) 그래프의 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접(Adjacent)하다고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩테스트에서는 이 2가지 방식 모두 필요하니 두 개념에 대해 확실하게 알고 있도록 하자. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계..

n = int(input()) change = 1000 - n money_unit = [500,100,50,10,5,1] count = 0 for i in money_unit: if change//i > 0: count += (change//i) change %= i print(count) 이번 문제는 그리디 알고리즘의 대표적인 기본 문제로, 그리디 알고리즘을 처음 공부할 때 내용을 이해하기 좋은 문제이다. 이 문제의 핵심은 잔돈을 최대한 적은 개수의 잔돈으로 거슬러주는 것인데, 위 문제와 같은 경우에는 모든 돈의 단위가 서로 배수 관계를 가지고 있기 때문에 단순히 금액이 큰 순서대로 거슬러 주어도 문제없이 풀 수 있다. 만약에 잔돈이 800원이고 가진 돈의 단위가 [500, 400, 100] 이라면 단..

expression = input() # '-'를 기준으로 분할 # ex) ['00009','00009+00008'] split_exp = expression.split('-') for i in range(len(split_exp)): # 분할된 문자열들을 순서대로 '+'를 기준으로 분할 후 합을 구하기(내부는 +로만 이루어져 있기 때문) # 그리고 동시에 앞에 0으로 채워진 문자열들을 정수화 시킨다 # ex) [9, 17] split_plus = list(map(int,split_exp[i].split('+'))) split_exp[i] = sum(split_plus) # 첫 번째 원소를 제외한 나머지 원소들은 '-'를 기준으로 파싱되었기 때문에 모두 빼주면 된다. # ex) 9 - 17 print(s..

n = int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) a.sort() a_resort = [0] * n b_index = [] for i in range(n): b_index.append((i,b[i])) b_index.sort(key=lambda x:-x[1]) for i in range(n): a_resort[b_index[i][0]] = a[i] sum = 0 for i in range(n): sum += (a_resort[i] * b[i]) print(sum) 이번 문제는 전형적인 Greedy 알고리즘 문제로 난이도는 크게 어렵지 않았다. 이 문제의 핵심은 배열 A의 원소와 B의 원소간의 곱이 최..

# 회의실 배정 n = int(input()) list = [] count = 0 last_time = 0 for i in range(n): start, end = map(int,input().split()) list.append((start,end)) # 시작시간 기준으로 오름차순 정렬 list.sort(key=lambda x:x[0]) # 종료시간 기준으로 오름차순 정렬 list.sort(key=lambda x:x[1]) # 회의 시간이 겹치지 않도록 회의 선정 for i in list: if i[0] >= last_time: count += 1 last_time = i[1] print(count) 이번 문제는 본인이 문제를 잘못 읽게 되어 많이 헤맸던 문제였다. 여태까지 그리디 문제를 풀 때 주어진..

n, k = map(int,input().split()) value = [] count = 0 for i in range(n): value.append(int(input())) value.sort(reverse=True) while k!=0: for i in value: if k//i > 0: count += k//i k %= i print(count) 이번 문제는 대표적인 Greedy 알고리즘 문제로, 주어진 동전 단위들을 가지고 최소한의 동전을 사용하여 금액(k)를 만드는 것이 핵심이다. 여기서 가장 중요한 조건은 바로 A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수이다. 왜 저 조건이 중요한지 생각해보면, 이 문제를 간단하게 탐욕적으로 접근해서 풀 수 있는 이유는 가지고 있는 동전 중에서 ..