ACMICPC (7) 썸네일형 리스트형 [백준] 랜선 자르기 백준, 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net TL;DR 이진 탐색(Binary Search) Parametic search 문제 요약 1. 랜선의 길이가 주어지고 해당 랜선을 잘라 만들어야 하는 랜선의 개수가 주어진다. 2. 만들어야 하는 랜선의 개수를 만족할 수 있는 경우 중 가장 긴 랜선의 길이를 반환하는 프로그램을 작성해야 한다. 3. 주어진 랜선의 개수를 초과해서 만들 수 있다. - 주어진 랜선의 길이를 잘라 만든 랜선의 개수가 주어진 랜선의 개수 이.. [백준] 그대, 그머가 되어(python) 백준, 그대, 그머가 되어 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 바꿀 수 있는 문자 간의 관계가 표현되어 있는 그래프에서 주어진 문자를 바꿀 수 있는 최소 횟수를 반환하라. 2. 문자를 바꿀 수 없는 경우에는 -1을 출력한다. - 문자를 다른 문자로 바꿀 수 있는 관계가 주어진다. - 이 관계들에서 바꾸기를 원하는 문자를 바꿀 문자로 바꾸는데 걸리는 과정의 최소 횟수를 반환하는 프로그램을 작성하면 된다. - 각 문자들을 노드로, 바꿀 수 있는 노드들 사이의 관계를 간선의 형태로 그래프로 표현할 수 있다. 이 때, 그래프는 방향성이 없는 무향 그래프이다. - 노드 사이의 관계를 표현할 때 꺽쇠''가 아닌 괄호'()'를 사용하여 표현한 것.. [백준] 특정 거리의 도시 찾기(python) 백준 온라인 저지, 특정 거리의 도시 찾기 TL;DR 다익스트라 알고리즘(Dijkstra Algorithm) 너비 우선 탐색(BFS) 문제 요약 1. 1번부터 N번까지 N개의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 2. 특정 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하라. 3. 최단 거리가 K인 도시를 오름차순으로 출력한다. 존재하지 않는다면 -1을 출력한다. - 1 : N개의 노드와 M개의 간선, 간선의 가중치는 1인 그래프로 생각할 수 있다. - 다익스트라 알고리즘을 사용하여 X 노드로부터 다른 노드들까지의 최단 경로를 확인한 뒤, 경로가 K인 노드들을 반환하면 될 것 같다. 입출력 형태.. [백준] 막대기(python) 백준, 막대기 TL;DR 스택(Stack) 문제 요약 1. 높이가 서로 다른(같을 수 있음) 막대기를 일렬로 세운 후 오른쪽에서 봤을 때 보이는 막대기의 개수를 알아내는 프로그램을 작성하라. - 일렬로 세운 막대기를 가장 오른쪽에서 봤을 때 보이는 막대기의 수를 반환하면 된다. - 가장 오른쪽에 있는 막대기보다 크기가 작은 막대기들은 보이지 않을 것이고, 큰 막대기들이 보일 것이다. 입출력 형태 - 주어진 예시에서 1번 막대기는 2번 막대기에 가려지고 4, 5번 막대기는 6번 막대기에 의해 가려져서 보이지 않는다. 따라서 보이는 막대기는 2, 3, 6번 막대기가 되어 총 3개가 된다. 풀이 막대기의 길이를 스택에 입력받는다. 가장 마지막에 들어오는 원소가 스택의 최상단에 위치할 것이다. 스택에서 하나씩 .. [백준] 고무오리 디버깅(python) 백준, 고무오리 디버깅 TL;DR 스택(Stack) 구현(Implementation) 문제 요약 1. 문제를 받은 상태에서 고무오리를 받으면 문제를 해결한다. 2. 문제가 없는 상태에서 고무오리를 받으면 두 문제를 추가한다. 3. 주어진 입력에 대해서 문제를 모두 해결하였으면 '고무오리야 사랑해'를 아니라면 '힝구'를 출력한다. - 문제와 고무오리가 입력으로 주어질 때 문제가 스택에 있고 고무오리를 입력으로 받는다면 스택을 비우는 방식으로 문제를 해결할 수 있을 것이다. - 스택이 비어있을 때 고무오리가 입력으로 들어온다면 두 문제를 스택에 추가해야 한다. 입출력 형태 문제를 모두 해결한 경우와 그렇지 않은 경우의 예시를 가져왔다. - 예제 입력 1에서는 (문제 - 고무오리), (문제, 문제 - 고무오리.. [백준] 수들의 합2(python) 백준, 수들의 합 2 TL;DR 투 포인터(two pointer) 문제 분석 1. N개의 자연수 배열에 대해서 i부터 j까지 연속된 수들의 합이 M이 되는 경우의 수를 구하는 프로그램을 작성하라. 2. 1 [백준] DFS와 BFS(python) 백준, DFS와 BFS TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 분석 1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 2. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 3. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 4. 정점 번호는 1번부터 N번까지이다. - 입력으로 주어진 그래프를 DFS와 BFS로 각각 순회한 결과를 출력하는 프로그램을 작성하는 문제이다. - 2번의 조건에 유의하여 문제를 풀어야 한다. 입출력 형태 - 가장 첫 번째 줄에 정점(vertex, node)의 개수와 간선(edge)의 개수, 그리고 시작 정점의 번호가 주어진다. - 두 번째 줄부터는 각 정점 간의 연결관계를 나.. 이전 1 다음
