국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 10분 + a 1. 문제 설명 - 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 2. 접근 방식 - 점화식: 모든 0

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 1. 문제 설명 - https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 접근 방식 - 최대로 마실 수 있는 포도주의 양을 출력, n = 4 - 3까지는 입력해준다. - 만약 n일 때 마실 수 있는 경우의 수를 구하면 - n을 안 마시는 경우: dp[n-1] - n을 마시는 경우 처음일 ..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40분 + a 1. 문제 설명 -https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 접근 방식 - 길이가 i일 때를 1차 for문을 사용해서 구분하고, 2차에서는 1의 자릿수의 개수를 센다. - 1의 자리수가 0, 9일 때는 기존 패턴과 다른 경우가 생긴다는 것을 이해해야 한다. 3. 코드 n = int(input()) dp = [[], [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]] fo..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 접근 방식 - i가 6의 배수일 때, 3의 배수일 때, 2의 배수일 때를 나눠서 생각한다. 해당 위치에서, 어떻게 감소시키는게 더 효율적일지 생각한다. - Botton-up으로 dp를 쌓는다. 3. 코드 n =int(input()) dp = [0]* (10**6+1) dp[1] = 0 for i in range(2, 10..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 + a 1. 문제 설명 - https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 접근 방식 - 마지막 계단이 밟혀있다고 가정하고 시작한다. (뒤에서부터 시작) - 그 전의 계단은 End-1이거나, 맨 마지막 End-2일 것이다. - End를 End-1에서 왔을 경우(한 칸), "End + E..

오늘은 DP 총 3문제를 풀었는데, 꽤나 시간이 오래걸렸다. 한 문제에서 계속해서 오류가 떠서 무슨 문제인가 했었는데, 중간에 변경했던 코드에서 문제가 발생해서 미처 생각하지 못했다. DP 문제에 핵심인 DP는 잘 구현했지만 다른 부분에서 계속해서 문제가 발생해서 시간이 오래 걸린 점이 좀 아쉬운 것 같다. 그래도 DP 문제를 푸는데 예전에는 점화식을 아예 생각하지 못했었지만, 그래도 다양한 문제를 접하면서 점점 실력이 늘고있는 것 같아서 위로가 된다. 그리고 오늘 드디어 백준 골드 티어를 달성했다. 알고리즘 스터디를 시작한지 총 30일만에 골드 티어를 달성했는데, 내심 뿌듯하면서도 아직 갈 길이 멀다는 생각이 든다. 아직 코딩 테스트를 보기에는 조금 부족한 부분이 있기에 조금 더 공부를 하면서 내 코딩..