[백준] 12100번 - 2048 (Easy) 풀이 시간: 6시간 이내 (한줄평) 내 설계대로 구현이 잘 되지 않아 다른 사람의 풀이를 참고했음에도 어려웠던 문제 상하좌우 이동 부분이 구현을 하기가 굉장히 까다로워 변수/조건이 조금만 달라져도 오류를 고치다 늪에 빠져버린... 추후 처음부터 끝까지 전체 코드를 직접 짜봐야할 문제!! 1) 문제 해결 아이디어 이 문제는 이동을 통해 변경된 정보를 담아둘 2차원 리스트(temp)를 깊은 복사를 통해 생성하는 것이 중요하다. 3번에서 1) move 함수로 2차원 리스트(temp)를 변경하고 2) dfs를 호출하고 3) 2차원 리스트(temp)를 원상복귀해준다 는 흐름이 중요하다!! 잊지말자 절대~~~ 1. 깊이(depth)가 5이면 5번 이동했다는 것이므로 2..
[백준] 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를 이용한 풀이만 할 것이다. 중복 조합을 구할 때는 이전..
[백준] 15651번 - N과 M (3) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래 조건에 따르면 중복 순열을 구하는 문제다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 permutations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 중복 순열을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 중복 순열을 구할 때는 dfs 인자로 깊이(depth)만 넘겨주면된다!! 이전 선택 여부를 확인하지 않아도 된다!! 2) 소스코드 # 중복 순열 n, m = map(int, inp..
[백준] 15650번 - N과 M(2) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래의 조건 2개로부터 이 문제는 조합을 구하는 문제임을 알 수 있다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 combinations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 조합을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 조합을 구할 때는 이전에 선택한 값보다 큰 값을 골라서는 안되므로 dfs 인자로 깊이(depth)에 탐색시작값(idx)를 추가로 넘겨주어야 ..
[백준] 15649번 - N과 M(1) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래 조건에 따르면 순열을 구하는 문제다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 permutations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 순열을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 순열을 구할 때는 dfs 인자로 깊이(depth)만 넘겨주면된다!! 2) 소스코드 n, m = map(int, input().split()) temp = [] # 수열을 담을 곳 # DFS def dfs(..
[백준] 1759번 - 암호 만들기 C개의 알파벳 목록에서 길이 L인 암호(모음 최소 1개, 자음 최소 2개)를 모두 구하는 것으로 전형적인 완전탐색(백트래킹) 문제다. 풀이 방법은 DFS를 이용하거나 combinations 라이브러리를 이용하는 2가지 방식이 있다. combinations 풀이가 DFS보다 시간측면에서 효율적이기는 했지만 코딩테스트에서 combinations 라이브러리를 사용할 수 없는 경우도 있으므로 1번 풀이로도 풀 수 있어야 한다. (풀이1) DFS 이용 풀이 시간: 30분 이내 1) 문제 해결 아이디어 dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수) 를 넘겨주게 했다. dfs를 호출할 때마다 모음, 자음 개수도 함께 변경하여 넘겨주기 때문에 암호..
