본문 바로가기

알고리즘204

[백준] 9251번 - LCS (파이썬) 문제) 백준 - 동적 계획법 (Dynamic Programming) - LCS -> www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp를 해당 문자 이전까지 만들 수 있는 LCS라 하자. dp를 업데이트 해가며 만약 문자열이 같을 경우(string1[i] == strring2[j]), 이전 LCS의 길이(dp[i - 1][j - 1])에 1을 더해준다. 문자가 같지 않을 경우, 이전에 만든 LCS중 최대값을 그대.. 2021. 3. 29.
[Code Jam] 2021 Code Jam 도전! Code Jam을 모르는 분들이 있다면 -> codingcompetitions.withgoogle.com/codejam Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 알고리즘 동아리 (AL林)에서 대회 공지가 올라와서 참가하게 되었다. Google 대회에 내가 참가하다니! 참가하는 것만으로도 영광스럽지 않을까 싶어서 호다닥 참가 신청했다. 한.. 2021. 3. 27.
[백준] 15917번 - 노솔브 방지문제야!! (C++) 문제 및 풀이 문제) 백준 - 수학(Mathematics) - 노솔브 방지문제야!! www.acmicpc.net/problem/15917 15917번: 노솔브 방지문제야!! 어떤 수 a가 2의 거듭제곱꼴로 나타내어진다고 해 봅시다. 그렇다면, a = 2n (단 n ≥ 0인 정수) 를 만족할 겁니다. 보통, 각 비트별로 검사를 하면서, 켜져 있는 비트의 개수를 알아내는 것도 좋은 www.acmicpc.net 완전 탐색을 이용한 풀이) #include #include using namespace std; int q; bool isTwo(int n) { for (int i = 0; i < 31; ++i) { if (pow(2, i) == n) return true; } return false; } int main() { i.. 2021. 3. 25.
[백준] 2798번 - 블랙잭 (C++/파이썬) 문제 및 풀이 문제) 백준 - 브루트 포스(Brute Force) - 블랙잭 -> www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 카드를 세 장 뽑으므로, 삼중 반복문을 이용하여 카드 세 장을 선택하며 그 카드들의 합을 계산하여 확인한다. c++ 소스코드) #include #include #include using namespace std; int n, m, sum = 0; vector card; int main() { //빠른 입출력 io.. 2021. 3. 18.
[백준] 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.
[Algorithm] 위상 정렬 - Topology Sort (파이썬, C++) 위상 정렬 - Topology Sort 위상 정렬은 순서가 정해져 있는 노드들을 차례대로 정렬할 때 사용할 수 있는 알고리즘이다. 더 개념적으로 정의하자면, 위상 정렬이란 "방향 그래프의 모든 노드를 방향성에 따라 정렬"하는 것이다. 위상 정렬에서 그래프는 방향 그래프이므로 각 방향에 대한 간선이 존재한다. 이때 어떤 노드가 다른 노드를 가리킬 때, 들어오는 간선의 개수를 "진입 차수"라 한다. 위상 정렬 알고리즘 ① 진입 차수가 0인 노드를 큐에 넣는다. ② 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. ③ 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다. ④ 큐가 빌 때까지 ②,③ 과정을 반복한다. 파이썬 소스 코드) C++ 소스 코드) 위상 정렬의 시간 복잡도 위상 정렬을 .. 2021. 3. 10.
[백준] 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.
반응형

티스토리툴바