포도가게의 개발일지

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 1. 문제? string에서 원하는 값 찾아서 지우기 2. 어려웠던점 처음엔느 pythom에서 제공하는 replace함수를 이용하여 쉽게 구현할려했지만 47%에서 바로 시간초과로 터져버렸다 -> 그래서 문제 힌트를 보고 stack을 도입하여 clear -> 이러한 string문제에 대해 경험을 충분히 쌓아여되서 좋은 문제였던거같다 import sys sys.stdin = open('..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 ? 이친수를 만족하는 숫자의 개수를 찾아라 접근법 - 첫번째는 부분문자열로 일일이 다 검색을 해볼려했는데 자리수의 개수가 90인걸 보고 2**90을 볼수는 없으니 포기했다 ㅋㅋㅋ - 두번째로는 결국 종이에 써보다가 발견한 건데 신기하게도 피보나치수열을 만족한다는 것이였고 - 이 문제는 다이나믹 프로그래밍으로 연결된다 결구 f(n) = f(n-1) + f(n-2)로 문제를 풀 수 있..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 ? 마지막 도시까지 도달했을때 최소 cost비용을 찾는 문제 접근법 - 2번째 도시로 이동할땐느 반드시 기름을 채우고 이동해야한다 - 그럼 얼마나 기름을 채우고 이동해야하나?가 문제였고 - 접근하게 일단 채우고 이동했는데 가격이 더 비싸면 첫번째에서 더 넣고 싸면 두번째에서 넣는 방식으로 접근함 import sys sys.stdin = open('inputs.text') n =..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 문제 : 가장 작은 카드 조합 만들기 접근법 - 가장 작게 만드는 문제 - 전체 카드에서 가장 작은 카드 2개를 뽑아서 더한값이 nC2 조합중 가장 작은 수의 합이다 - 그리디 알고리즘으로 접근 및 우선순위 큐를 이용하여 접근 import sys import heapq #sys.stdin = open("inputs.text") n,m = map(int,sys...

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 : 주어진 수의 리스트중 + - 연산자를 활용하여 결과값이 나올 수 있는 경우의 수를 찾으시오 접근법 - 처음에는 두가지 경로로 나뉘는 경우의수여서 bfs로 접근할려 했지만 메모리 제한이 128mb라 dp로 접근하게 되었다. - dp 매트릭스는 가로축은 점수 세로축은 몇번째 값을 더하는지를 의미 한다. - dp[i][j+arr[i]] += dp[i-1][j]의 의미는 전 연산의 경우의..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 : 선발할 수 있는 신입사원의 최대 인원수 접근법 - 최대 최소문제이며 사이클이 돌지않음 - 그리디로 접근하였다 - subprob의 최적의 해가 total prob의 최적의 해와 일치 한다. - matrix를 정렬 하였을때 a,b중 하나라도 1등인애는 맨앞에 가게 되므로 반드시 신입사원 으로 뽑힌다 - 그리고 1등 이후의 등수들은 b의 등수가 앞선애보다 낮은 등수이기만 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 : 가장 많이 회의실을 쓸 수 있도록 배치 접근법 - 그리디 알고리즘 문제였다 - 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에서 최적의 해가 되는 것을 증명하는 문제이다 - 그래서 저는 시작 시간, 끝나느 시간, 시간의 차이로 매트릭스에 저장 후 - 우선 정렬을 끝나는 시간으로 순서대로 정렬 하였다. 힌트가 큰 도움이 됬다. -> 다음 정렬은 스타트 시간을 순서대로 정렬한다. - 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에 최적의 해가 부정되는 순간 문제자체가 성립 될..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 : 00와 1을 사용하여 만들 수 있는 경우의 수의 15746으로 나눈 나머지 접근법 - 타일의 개수의 따른 조합법을 찾았다 타일이 하나인 경우 조합이 1가지 타일이 둘인 경우 조합이 2가지 타일이 셋인 경우 조합이 3가지 타일이 넷인 경우 조합이 5가지 가 나왔으며 피보나치 수열처럼 f(n) = f(n-1) + f(n-2)로 움직이는 것을 확인 후 dp를 이용하여 접근 문제점 : 처음에는 top..