Oneulog

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 문제 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오. 입력 첫째 줄에 지름길의 개수 N과 고속도로의..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이..

BFS(Breadth-First Search) 1. BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘 2. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다. 1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3) 더 이상 2)의 과정을 수행할 수 없을 때까지 반복한다. 3. BFS 동작 예시 [Step 0] 그래프를 준비한다.(방문 기준 : 번호가 낮은 인접 노드부터) -> 시작 노드 : 1 [Step 1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다. [Step 2] 큐에서 노드 '1'을 꺼내 방문하지..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다. 상근이의 집에서 페스티벌이 열리는..

그래프 탐색 알고리즘 : DFS/BFS 1. 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 2. 대표적인 그래프 탐색 알고리즘을는 DFS와 BFS가 있다. 3. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. DFS(Depth-First Search) 1. DFS는 깊이 우선 탐색이라고도 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 2. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드거 ..

1. 재귀 함수란 자기 자신을 다시 호출하는 함수 2. 단순한 형태의 재귀 함수 예제 - '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다. - 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다. def recursive_function() : print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 3. 재귀 함수의 종료 조건 (1) 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. (2) 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. (3) 종료 조건을 포함한 재귀 함수 예제 def recursive_function(i) : # 100번 째 호출을 했을 때 종료되도록 ..

스택 1. 스택 자료구조 (1) 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 (2) 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 2. 스택 구현 예제 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[::-1]) # 최상단 원소부터 출력 print(stack) # 최하단 원소부터 출력 3. 큐 자료구조 (1) 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료..