본문 바로가기

백준/Silver(1~5)

 (33)
[백준]_11724번 : 연결 요소의 개수(파이썬) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 무방향 그래프에서 연결 요소의 개수를 세야 하는 문제이다. 조금 더 쉽게 말하자면 간선으로 이어진 묶음이 몇 개 발생하는지 알아내야 한다. 일단 예시 입력 1에 의하면 그래프의 생김새는 아래와 같을 것이다. 이 문제는 두 가지 방식으로 풀 수 있는데, 1. Union-Find 알고리즘 해당 알고리즘을 이용하면 모든 노드의 최상위 노드를 모두 찾을 수 있다. 무방향 그래프라 상위 노드 개념은 없지만 유..
[백준]_1991번 : 트리 순회(C언어) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 입력으로 노드들이 부모, 왼쪽 자식, 오른쪽 자식 순서로 주어지고 이렇게 완성된 트리에서 전위 순회, 중위 순회, 후위 순회를 해서 노드에 저장된 값들을 순회별로 출력하면 되는 문제이다. 전략 먼저 입력 방식을 정의해 보자. 부모 노드는 반드시 입력되고 존재하지 않는 자식 노드는 '.'으로 대체된다. 즉 일단 크기가 6인(최대 입력이 5개까지인데 크기가 6인 이유는 배열의 마지막에 널 문자('\0')를 저장해야 되기 때문) 배열로 문자열을 받은 다음에..
[백준]_16139번 : 인간-컴퓨터 상호작용(파이썬) 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 누적합과 사전을 적절히 사용하면 무난하게 풀렸던 문제이다. 문제에 나와 있듯이 문자열의 길이와 질문의 수는 최대 200,000까지 늘어날 수 있기 때문에 질문을 하나 받을 때마다 문자열 구간 [l, r]에서 목표 알파벳이 몇 개 나오는지 다시 샐 여유가 없다. 따라서 아래와 같은 접근을 사용하여 시간을 줄이는 전략을 선택했다. 접근 알파벳을 target, l을 start, r을 finish라고 하자. 또한 과거에 ..
[백준]_12852번 : 1로 만들기 2(파이썬) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1로 만들기 문제에서 업그레이드된 문제이다. 이 문제는 크게 두 가지 영역으로 나뉘고 서로 거의 독립적인 코드를 요구한다. 사실 1번 코드로부터 2번 코드에서 사용될 정보는 1번 코드의 결괏값 1개뿐이다. 이 문제에서 요구하는 그대로 1로 만들기 위해 필요한 연산 횟수를 구하는 코드. 입력 n에 대해 1까지의 경로를 탐색하는 코드. 1번 코드는 이미 만들었다고 가정하고(궁금하면 위의 링크를 타고 해결책(dp, bfs)을 보고 오시기를 바랍니다) 2번 코드만 작성해 보겠다. 접근 n에 대한 연산 횟수 정보를 이미 얻었다고 가정하고 이 값을 A라고 하자. 이제 n에서 출발..
[백준]_1463번 : 1로 만들기(파이썬) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법? 잘 알려져 있는 동적 계획법(Dynamic Programming) 문제이다. 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 의미한다고 생각하면 편하다. 각 하위 문제를 해결한 후 그 해결에서 얻은 답을 나중에 다시 사용하는 방법인 것이다. 이 꼬리의 꼬리를 무는 과정을 계속하다 보면 결국 우리가 원하는 큰 문제에 대한 답이 튀어나온다는 원리인 것이다. 가장 좋은 예시로는 피보나치 수열이다. 9 번째 피보나치 수열의 값을 얻기 위해서는 0+1=1 -> 1+1=2 -> 1+2=3....처럼 아래에서부터 차근차근 올라가는 과정을 진행에 있어 과거..
[백준]_1260번 : DFS와 BFS(파이썬 and C언어) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net INDEX 1. 그래프 탐색 2. 전략(파이썬) 3. 전략(C언어) 1. 그래프 탐색 어떤 정점들이 서로 간선으로 연결되어 있다. 이것을 그래프라고 한다. 그래프 탐색이 초반에 까다롭게 느껴지는 점은 바로 방문했던 정점을 다시 방문할 필요가 없다는 사실이다. 이제 이것을 코드로 어떻게 처리하냐는 나중의 문제이고, 그래프 탐색에는 크게 두 가지 방법이 있고 이번 문제에서는 그것들에 대해 묻고 있다. 첫 번째는 DFS(Depth..
[백준]_1931번 : 회의실 배정(파이썬 and C언어) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 가장 많은 회의 수를 배정하게끔 코드를 짜야한다. 그렇다면 어떤 접근을 해야 할까? 먼저 문제를 푸는 데에 있어서 중요한 값들은 무엇이 있을까. 일단 회의실 배정을 많이 해야 되기 때문에 회의의 시작 시간과 마침 시간이 최대한 적어야 한다. 또한 직전에 끝난 회의 시간과 그다음에 시작할 회의의 시간 차이가 적어야 한다. 하지만 어느 것이 가장 중요하다고 할 수 있는가? 그렇지 않다. 바로 동시에 동등히 중요하다는 것이다. 예제와 같은 답이((1,4), (5,7), (8,11), (12,14)) 어떻게 나오게 되었는지 생각해보자. (1,4)는 존재하는 모든 타임테이블 중에서 가장..
[백준]_2606번 : 바이러스(파이썬 and C언어) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 파이썬(dfs) 파이썬(bfs) C언어(dfs) bfs와 dfs 두 개의 방법으로 해결할 수 있는 문제이다. 파이썬(dfs) 문제 풀이의 기반이 되는 그래프를 먼저 그려야 한다. 여기서 말하는 그래프란 2차원 배열에 특정노드마다 어떤 노드들과 인접해 있는지 저장해 주는 그래프이다. 예를 들어 문제에서 예제로 제시된 을 보면 1 노드는 2 노드와 5 노드와 연결되어 있기 때문에 그래프에는 [ [ ], [ 2, 5 ] ...]와 같이 저장될 것이다. 저장하는 방법은 아래..

티스토리툴바