본문 바로가기

백준198

[백준] 1707번 - 이분 그래프 (파이썬) 문제 및 풀이 문제) 백준 - 그래프 이론 (Graphs) - 이분 그래프 -> acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프가 주어졌을 때, 집합을 둘로 나누어 한 집합에 속한 정점끼리는 인접하지 않게 분할하는 문제. 처음에 주어진 그래프가 당연히 연결 그래프일거라 생각해 약 2시간가량 맞왜틀(맞는데 왜 틀려)를 시전 했다. 연결 그래프가 아니어도 이분 그래프가 될 수 있음을 깨달았다. 그래프를 인접 리스트 형태로 선언하고, 각 노드가 어떤 집합에 포합 되.. 2021. 3. 12.
[백준] 11725번 - 트리의 부모 (파이썬) 문제) 백준 - 트리 (Tree) - 트리의 부모 -> www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리 상에서 연결된 두 정점을 인접 리스트 방식으로 나타낸다. 문제에서 트리의 루트가 1번으로 주어졌으므로 dfs를 이용해 1번부터 시작해 노드에 연결된 노드들을 순회한다. parent 리스트에 부모를 채킹(Checking)하면서, 0일 겨우 방문하지 않은 노드로 인식해 부모 노드로 저장한다. 소스 코드) import sys sys.setrecursionlimit(10 ** 8) n = int(input()) tree .. 2021. 3. 12.
[백준] 12865번 - 평범한 배낭 (파이썬, C++) 문제) 백준 - 동적 계획법 (Dynamic Programming) - 평범한 배낭 -> www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1 2 3 4 5 6 7 ( 6, 13 ) 0 0 0 0 0 13 13 ( 4, 8 ) 0 0 0 8 8 13 13 ( 3, 6 ) 0 0 6 8 8 13 14 ( 5, 12 ) 0 0 0 0 12 13 14 (물건 무게, 가치)가 (3, 4)인 경우를 주목.. 2021. 3. 11.
[백준] 2252번 - 줄 세우기 (파이썬) 문제 및 풀이 문제) 백준 - 위상 정렬 (Topology Sort) - 줄 세우기 -> www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상 정렬 문제. 각 학생들의 키 비교를 진입 차수로 생각하여 위상 정렬하면 된다. 소스 코드) from collections import deque v, e = map(int, input().split()) #진입 차수 indegree = [0] * (v + 1) graph = [[] for i.. 2021. 3. 10.
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 바이토닉 부분 수열 -> www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net (백준 - 11053번)가장 긴 증가하는 부분 수열 문제와 (백준 - 11722번) 가장 긴 감소하는 부분 수열 문제를 합치면 풀 수 있다. 가장 긴 증가하는 부분 수열의 아이디어를 채택해 우리는 1~n까지 탐색( i )하면서 그 이전까지 i번째 숫자보다 작으면서도 가장 긴 증가하는 부분 수열의 길이를 저장한다. 가장 긴 증가.. 2021. 3. 9.
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 가장 긴 감소하는 부분 수열 -> www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 참고) 2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) 문제) 백준 - 동적 계획법 .. 2021. 3. 9.
[백준] 1890번 - 점프 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프 -> www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다. 소스 코드) import sys sys.setrecursionlimit(1000000) input = sys.s.. 2021. 3. 9.
[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길 -> www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. Python 소스 코드) C++ 소스 코드) Python .. 2021. 3. 9.
[백준] 1904번 - 01타일 (C++/파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 1(Dynamic programming)- 01타일 -> www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net dp 가능한 숫자 dp[1] 1 dp[2] 11 00 dp[3] 111 001 100 dp[4] 1111 0011 1001 1100 0000 ... dp[n] dp[n - 1] ... dp[n - 2] n을 숫자의 길이, dp[n]에 해당하는 값을 가능한 숫자의 개수라 하자. '00' 타일과 '1' 타일을 붙이는데 별 다른 제약 조.. 2021. 3. 4.
반응형

티스토리툴바