본문 바로가기

분류 전체보기

 (328)
[백준] 11053번 : 가장 긴 증가하는 부분수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 1) 먼저 부르트포스 방식으로 2중 for 문을 이용하여 O(n^2)의 시간 복잡도로 문제를 해결 할 수 있다. dp 테이블을 n-1 개 생성하여 {1} , {1,5} , {1,5,2} {1,5,2,1}, {1,5,2,1,4} ... {1,5,2,1,4,3,4,5,2}, {1,5,2,1,4,3,4,5,2,1} 로 ..
[백준] 2293번 : 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 테스트 케이스인 1,2,5를 예를 들어 문제를 풀어보겠습니다. n = 3이고 k=10인 문제에서, k=10이기때문에 10일때 1,2,5 동전으로 만들 수 있는 경우의수를 구해야한다. 우선 10까지 구하는 방법을 나열해본다. 동전 1) - 1일때 : 1 - 2일때 : 11 - 3일때 : 111 - 4일때 : 1111 - 5일때 : 11111 - 6일때 : 111111 - 7일때 : 1111111 - ..
[백준] 11066번 : 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 해당 문제는 브루트포스 알고리즘으로 문제를 해결할 경우 시간복잡도가 O(!(N-1))으로 문제를 해결 할 수 있습니다. 예를들어 40, 30, 30, 50 이라는 수가 주어져 있을때 1. 40, (30,30,50) 에서 더해지는 경우 2. (40,30), (30,50) 에서 더해지는 경우 3. (40,30,50),50 에서 더해지는 경우 숫자가 N개 일때 N-1 경우의 수가 발생한다. 즉..
[백준] 1916번 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 위의 문제는 데이크스트라 알고리즘인 최단경로 알고리즘 문제를 풀고 오면 똑같은 방식으로 문제를 해결 할 수 있다. 우선순위큐로 가장 짧은 거리인 노드부터 방문하고, 방문하려는 거리가 이미 더 짧은 거리라면 탐색을 멈춘다. https://bigkwangs.tistory.com/23 [백준] 1753번 : 최단경로 https://www.acmicpc.net/probl..
[백준] 1753번 : 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 가장 간단하게 구현 할 수 있는건 깊이 우선탐색으로 시작 노드로 부터 관련된 노드를 방문하면서 가중치 테이블들 만들어 최대 값보다 작을 경우 업데이트를 하는 방법이다. 아래의 코드는 위의내용을 구현한 코드이다. import sys sys.setrecursionlimit(10**6) V, E = map(int, input().split()) # 점점의 개수, 간..
[백준] 1520번 : 내리막길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해당 문제는 깊이 우선탐색으로 자기자신보다 값이 낮을 경우 이동하면 된다. 0,0 의 위치에서 N,M의 위치까지 탐색을 하면 되는데 상,하,좌,우로 갈 수 있고 상,하,좌,우 중에서 자기자신보다 값이 낮으면 해당 위치를 깊이 우선 탐색을 하면 된다. 그러나 예제의 문제 2번째와 3번째는 20 의 위치를 지날때 중복되는 것을 알 수 있다. 3번째 탐색을 할때에 20을 위치를 지날때 이미 2번째에서 이미 ..
[백준] 9252번 : LCS2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제를 풀기전 아래의 문제를 먼저 이해해야 합니다. https://bigkwangs.tistory.com/18 [백준] 9251번 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부..
[백준] 2156번 : 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 마실수 있는 포도주 양의 최대값을 구하여라. 1. 포도주잔을 선택하면 모든 포도주를 마셔야하고, 원래위치에 다시 놓는다. 2. 연속으로 3개 놓여있는 포도주는 마실 수 없다. 테스트 케이스 분석 6 6 10 13 9 8 1 dp[1] = 6 dp[2] = 12 dp[3] = max(juice[1]+juice[3], dp[2]) dp[4] = max(dp[1]+juice[3]+juice[4] ,dp[..

티스토리툴바