[백준] 1904번 - 01타일 (한줄평) 아이디어는 쉽게 떠올렸으나 오류를 고치는데 시간이 걸렸던 문제! 나중에 다시 한 번 풀어봐야할 것 같다 (풀이1) 틀린 코드 풀이 시간: 20분 이내 1) 문제 해결 아이디어 1이상 1000000이하인 길이 n인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 구하는 문제다. 첫번째 오류. 메모리 초과 dp테이블의 크기를 n만큼 생성했는데 최대값이 1000000인 탓에 메모리 초과가 난 것 같다. 그래서 리스트를 사용하지 않고 값 2개를 저장할 수 있는 변수 2개(a, b)를 생성하여 문제를 해결했다. 두번째 오류. 시간초과 1%까지 되다가 시간초과가 났다. 15746으로 나눈 나머지를 출력시켜야 하는데 그냥 그 값을 출력시키도록해서 생긴 문제였다. 세번째..
[백준] 2749번 - 피보나치 수 3 (한줄평) 메모리 초과를 해결하지 못해 다른 사람의 풀이를 참고한 문제! 아예 생각조차 하지 못한 방식으로 해결이 가능하다... 답을 안봤으면 절대 못풀었을 문제^^; 유사 문제: 2747, 2748 https://hseungyeon.tistory.com/294 [다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 [백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다 hseungyeon.tistory.com 이 문제는 n이 1,000,000,000,000,000,000이하의 자연수 일 때..
[백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다. 2747번은 n의 범위가 45이하 자연수이고 2748번은 n의 범위가 90이하 자연수이다. 일단 두 문제 모두 일반 재귀로 피보나치 수를 구하려면 시간복잡도가 (2**n)으로 45이면 2**45(약 10**12), 90이면 2**90(약 10**27)으로 시간 초과가 나올 것이다. 그러므로 dp로 풀어야한다! (풀이1) 반복문 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 2) 소스코드 n = int(input()) # 1. 45이하 자연수, 2. 90이하 자연수 d = [0] * (n + 1..
t = int(input()) # 테스트 케이스 수 for _ in range(t): n = int(input()) # 정수 d = [0] * 11 # 11보다 작은 양수 d[1], d[2], d[3] = 1, 2, 4 for i in range(4, n + 1): d[i] = d[i - 3] + d[i - 2] + d[i - 1] print(d[n]) [백준] 9095번 - 1, 2, 3 더하기 (한줄평) 아이디어만 떠올린다면 쉽게 풀 수 있는 문제! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 11보다 작은 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. DP문제는 보통 아이디어만 잘 떠올리고 점화식을 세운다면 코드 자체는 간결하게 해결할 수 있는 문제..
[백준] 9184번 - 신나는 함수 실행 (한줄평) 재귀함수 그대로 구현하면 되지만 오류를 스스로 해결하지 못했던 문제..! 꼭 복습이 필요하다~ 풀이 시간: 60분 이내 1) 문제 해결 아이디어 이 문제는 a, b, c가 주어졌을 때 w(a, b, c)를 구하는 문제다. 이 문제는 아래의 재귀함수 그대로 구현을 하면 되지만 이렇게만 구현하게 되면 동일한 작업을 계속 반복하게 되어 그 값을 구하는데 매우 오랜 시간이 걸리게 되는 문제가 발생한다. 그래서 다이나믹 프로그래밍으로 해결해야하는데 다이나믹 프로그래밍의 핵심은 반복되는 계산을 피하기 위해서 dp테이블에 계산한 값을 저장해두고 나중에 그 값이 필요하다면 바로 그 값을 가져다 쓰는 것이다. if a 20, then w(a, b, c) returns:..
[백준] 1003번 - 피보나치 함수 (한줄평) 피보나치 수를 구하는 문제에서 약간 변형된 문제로 피보나치 수열 문제 풀 때 한번쯤 다시 풀어보면 좋을 것 같은 문제! 40이하의 자연수/0 이 n으로 주어질 때, fibo(n)이 호출되었을 때 fibo(0)과 fibo(1)이 호출되는 횟수를 구하는 문제다. 재귀 혹은 반복문을 이용하여 풀 수있고 두 방식 모두 메모리나 시간 측면에서는 동일하니 편한 방식으로 풀면 될 것 같다. (풀이1) 재귀 이용(내 풀이) 풀이 시간: 20분 이내 1) 문제 해결 아이디어 재귀를 이용한 풀이 방식이다. n번째 피보나치 수를 저장하는 dp 테이블(d)에 기존에는 피보나치 수 1개 값만 저장했다면 이 문제에서는 [피보나치 수, 0 호출 횟수, 1 호출 횟수] 3개 값을 저장..
[백준] 12100번 - 2048 (Easy) 풀이 시간: 6시간 이내 (한줄평) 내 설계대로 구현이 잘 되지 않아 다른 사람의 풀이를 참고했음에도 어려웠던 문제 상하좌우 이동 부분이 구현을 하기가 굉장히 까다로워 변수/조건이 조금만 달라져도 오류를 고치다 늪에 빠져버린... 추후 처음부터 끝까지 전체 코드를 직접 짜봐야할 문제!! 1) 문제 해결 아이디어 이 문제는 이동을 통해 변경된 정보를 담아둘 2차원 리스트(temp)를 깊은 복사를 통해 생성하는 것이 중요하다. 3번에서 1) move 함수로 2차원 리스트(temp)를 변경하고 2) dfs를 호출하고 3) 2차원 리스트(temp)를 원상복귀해준다 는 흐름이 중요하다!! 잊지말자 절대~~~ 1. 깊이(depth)가 5이면 5번 이동했다는 것이므로 2..
[백준] 10971번 - 외판원 순회 2 (한줄평) 설계자체는 단 시간에 했지만 시간초과를 해결하는데 시간이 오래걸렸던 문제로 꼭 복습 필요한 문제!! 이 문제는 외판원 순회 문제(TSP)로 N과 비용행렬이 주어졌을 때 외판원 순회에 필요하 최소 비용을 구하는 것이다. 1 ~ N 번호가 매겨진 도시들을 모두 거쳐 원래의 도시로 돌아오는 순회 여행을 말한다. 완전탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 풀이 시간: 90분 이내 1) 문제 해결 아이디어 1. 비용(graph) 입력 및 이동 경로(temp), 방문 여부(visited)를 저장할 리스트 생성 2. dfs(0, 0) 호출 -> 깊이= 0, 비용= 0으로 시작 3. n개 도시를 다 선택했고 마지막 도시→처음 도시로 가는 비용이 0이 아..
