[백준] 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이 아..
[백준] 14889번 - 스타트와 링크 (한줄평) 아이디어를 떠올리고 구현하는 것은 어렵지 않았으나 시간단축을 위한 방법을 고민해봐야했던 문제! 1 ~ N 번호를 가진 사람들이 있을 때 두 팀으로 나누었을 때 각 팀의 능력치(팀에 속한 모든 쌍의 능력치의 합)의 차이의 최솟값을 구하는 문제였다. 두 팀으로 나눌 수 있는 모든 경우의 수를 따져봐야하는 완전 탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 물론 조합을 구할 때 combinations 라이브러리를 사용할 수도 있다. 여기서 풀이 1, 2 둘다 DFS를 이용하여 구현했고 설계방식에 조금 차이가 있는데 풀이2가 메모리, 시간 측면에서 더 효율적이므로 풀이2를 추천한다. (풀이1) 내 풀이 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이..
[백준] 2580번 - 스도쿠 풀이 시간: 70분 이내 (한줄평) 어렵진 않았으나 오류를 고치는데 시간이 걸린 문제. 한번쯤 복습 필요!! 스도쿠는 어렸을 때부터 많이 해봤기 때문에 딱히 아이디어를 떠올릴 필요가 없이 쉽게 구현할 수 있었다. 다만 나의 고정관념으로 인해 생긴 문제들때문에 오류를 고치느라 시간이 좀 걸렸다. (풀이1) DFS를 이용한 시간초과, 틀렸습니다 실패 코드 1) 문제 해결 아이디어 첫번째 오류. 시간 초과 1. Python3으로 제출하였더니 5%까지 되다가 시간초과가 떴다. 2. PyPy3로 제출했더니 11%까지 되다가 시간초과가 떴다. 3. target을 리스트 대신 집합으로 선언하고 discard()를 썼지만 여전히 11%까지 되다가 시간초과가 떴다. 4. graph를 tem..
[백준] 15652번 - N과 M (4) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 M개를 고른 비내림차순 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래 조건에 따르면 중복 조합을 구하는 문제다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 combinations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 중복 조합을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 중복 조합을 구할 때는 이전..
[백준] 15683번 - 감시 풀이 시간: 2시간 이내 1) 문제 해결 아이디어 사각 지대의 최소 크기를 출력하는 문제다. 처음에는 아무생각없이 BFS로 풀어도 되나하는 문제였지만 cctv들의 방향을 설정하는 모든 경우의 수를 고려하여 풀어야 하는 완전탐색 문제로 DFS를 이용하여 풀어야했다. 지금까지 풀었던 문제는 되게 단순하고 정형화된 문제였기때문에 새로운 방식으로 풀려고 아이디어를 떠올리는데 시간이 많이 걸렸다. 추후 꼭 복습이 필요한 문제!! 나는 북, 동, 남, 서 방향을 차례대로 0, 1, 2, 3 으로 설정하였다. CCTV 번호에 따른 방법(방향 경우의 수)수는 다음과 같다. 첫번째 오류. 틀렸습니다 nx, ny를 x, y로 초기화해야 하는데, dx를 1번 더해준 값으로 초기화해서 문제가 생..
[백준] 2503번 - 숫자 야구 굉장히 익숙한 소재라 문제를 이해하고 설계를 하는데 어려움이 없었으나 오류를 고치느라 시간이 좀 걸렸다. 서로 다른 숫자로 구성된 세자리수를 영수가 생각하고 있을 때, (민혁이가 질문한 세자리수, 스트라이크 개수, 볼 개수)를 보고 가능성이 있는 답의 총 개수를 구하는 문제로 전형적인 완전탐색 문제다. 영수가 생각할 수 있는 수의 모든 경우의 수는 순서가 상관이 있기 때문에 순열로 풀 수 있는데 DFS를 이용하거나 permutations를 이용한 방식 2가지가 있다. (풀이1) DFS 이용 풀이 시간: 40분 이내 1) 문제 해결 아이디어 1. 깊이가 3일 때 종료 num이 세자리수가 되었으므로 종료 1-1. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기..
