Algorithm

[백준] 9252. LCS 2 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 참고 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence 풀이 0 - 1 Knapsack 문제와 비슷하게 2차원 배열을 이용한 DP로 풀이할 수 있는 LCS(Longest Common Subsequence, 최장 공통 부분수열) 문제. 최장..

[백준] 7579. 앱 - 파이썬

[Gold III] https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 일단 보자마자 생각난 것은 "Greedy로 풀면 참 편하겠다..." 인데, 간단하게 생각해 봐도 그리디로 해결될 문제가 아님. 모든 경우의 수를 파악해봐야 될 것 같은 문제이고, DP로 풀면 되겠다 싶었다. 0-1 Knapsack 문제와 동일한 방법으로 풀이했다. 1

[백준] 2623. 음악프로그램 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 보자마자 위상 정렬부터 생각이 났다. 근데 문제에서 사이클이 있을 수 있다는 것을 명시함. (위상 정렬은 사이클이 없을 때 적용 가능.) 처음에는 Union-Find를 이용해 미리 사이클이 있는 지를 검증하고 해야하나 생각했으나, 굳이 그러지 않아도 진행 과정에서 사이클이 존재한다면, N개를 모두 돌지 못하고 종료되므로 예외처리에 넣어줌. from co..

[백준] 2473. 세 용액 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 [백준] 2467. 용액 - 파이썬 의 업그레이드(?) 버전. 2467번 용액 문제는 N

[백준] 2467. 용액 - 파이썬

[Gold V] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 1과 풀이 2 모두 AC(통과)가 가능한 코드입니다. 풀이 1 일단, 모든 경우의 수를 다 따져본다면(Brute-Force), NC2 이기 때문에, (N * (N-1)) / 2 => O(N^2) 정도의 Time Complexity로 풀 수 있게 됨. 당연히 이 방법은 아닐 테고, 일단 문제를 보자마자 직감적으로 생각난 것은 Two Pointer였다. 그런데 일반적인 tw..

[백준] 2252. 줄 세우기 - 파이썬

[Gold III] https://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 풀이 [백준] 1005. ACM Craft - 파이썬 [백준] 2056. 작업 - 파이썬 최근 위 문제들과 같은 위상 정렬 문제를 몇 번 풀어서인지, 문제를 보고 얼마 지나지 않아 위상 정렬로 해결할 수 있겠다는 생각이 들었다. 모든 vertex가 edge로 연결되어 있지도 않고, "답이 여러 가지인 경우에는 아무거나 출력한다." 라는..

[백준] 27939. 가지 교배 - 파이썬

[백준 2023 가지컵 A번] [Bronze I] https://www.acmicpc.net/contest/problem/27939 풀이 '''P를 1, W를 0이라 한다면, P-우선 교배는 or 연산, W-우선 교배는 and 연산''' '''결국 조수들이 교배한 결과에서 W-가지가 하나라도 존재하면, 키위 교수가 교배할 때는 무조건 W-가지가 탄생.''' '''[교배해서 나온 품종을 포함하여 자신이 교배한 적 없는 품종이 하나만 남을 때까지 현재 가지고 있는 교배하지 않은 품종들을 모두 교배한다.]''' '''이 말인 즉슨, 교배의 결과물은 무조건 한 종..

[백준] 2056. 작업 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [백준] 1005. ACM Craft - 파이썬 과 매우 유사했던 문제. 풀이 [백준] 1005. ACM Craft - 파이썬 과 매우 유사해서 비슷하게 어려움 없이 풀었던 문제. DP와 위상 정렬(Topological Sort) 을 이용해서 풀이했다. from collections import deque N = int(input()) times = [] graph_in..