[백준] 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(..
[백준] 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. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기..
