728x90 백준 썸네일형 리스트형 [백준알고리즘] 11066번: 파일 합치기 -Python [백준알고리즘] 11066번: 파일 합치기 -Python https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 추가) 새로 풀어봤다. 밑에 나오는 크누스 최적화를 사용 안 하고 그냥 .. 더보기 [백준알고리즘] 1912번: 연속합 -Python [백준알고리즘] 1912번: 연속합 -Python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2019-08-20 첫 번째 풀이 이번 문제는 LCS에서처럼 뻘짓을 하지 않아서 좀 빨리 풀렸다!!ㅎㅎ 주어진 수열에서 연속하는 부분 수열들 중 최대 합을 구하면 된다. 이번에는 단순히 max만 비교해서 유지했기 때문에 풀면서 딱히 배열을 사용하지 않았다. 풀면서 max_val이라는 전체에서 여태까지 구한 최대합을 나타내는 변수와 tmax라는 max_val을.. 더보기 [백준알고리즘] 9251번: LCS -Python [백준알고리즘] 9251번: LCS -Python https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이번 문제는 LCS(Longest Common Subsequence) 문제이다. 임의의 두 문자열에서 각각의 sub sequence가 같을 때, 가장 긴 길이를 구하는 문제다. 이와 같은 문제를 전에 풀었었는데 엉뚱한 데에 정신이 팔려서 시간을 많이 잡아먹었다.. 문제를 풀기 위해서는 작은 sub seq.. 더보기 [백준알고리즘] 2565번: 전깃줄 -Python [백준알고리즘] 2565번: 전깃줄 -Python https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 20200408 아래부분에 새롭게 푼 코드를 올렸다. 내용은 동일한데 코드가 더 깔끔하다. 전깃줄 문제를 풀어봤다. 저번 문제에 이어서 LIS를 응용하는 문제라고 설명이 되어있습니다. '이게 왜 LIS 문제이냐'라고 한다면, 최소.. 더보기 [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 밑에 새로 풀면서 추가 설명을 적어놨다. 첫 풀이가 어려우면 밑의 풀이를 보면 된다. 2019-08-13 첫 번째 풀이 LIS(Longest Increasing Subsequence)의 응용문제 중 하나이다. 문제를 보면 뽑아낸 부분수열이 증가하다가 감소하는 형태를 가질 때의 최대길이를 구하는 문제이다. 쉬운 버전인 11053번의 경우 증가하는.. 더보기 [백준알고리즘] 1520번: 내리막 길 -Python [백준알고리즘] 1520번: 내리막 길 -Python https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 20200408 아래 새로 풀었다. 요즘 계속 DP를 다시 보고 있다. 오늘은 내리막 길을 풀어봤는데 금방 풀렸다. 개인적으로 dp 중에서는 쉬운 편이었다고 생각을 한다. 이번에는 최저의 방법을 구하는 것이 아닌 가능한 경우의 횟수를 구하는 문제다. 그러다.. 더보기 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python https://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 제목처럼 평범한 Dynamic Programming문제이다 처음에는 DFS와 upper bound를 이용한 Branch and Bound를 사용하려 하다가 사실상 Brute Force보다 조금 나은 수준의 코드가 되어버린 것.. 더보기 이전 1 ··· 11 12 13 14 다음