[백준] 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. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기..
[백준] 1759번 - 암호 만들기 C개의 알파벳 목록에서 길이 L인 암호(모음 최소 1개, 자음 최소 2개)를 모두 구하는 것으로 전형적인 완전탐색(백트래킹) 문제다. 풀이 방법은 DFS를 이용하거나 combinations 라이브러리를 이용하는 2가지 방식이 있다. combinations 풀이가 DFS보다 시간측면에서 효율적이기는 했지만 코딩테스트에서 combinations 라이브러리를 사용할 수 없는 경우도 있으므로 1번 풀이로도 풀 수 있어야 한다. (풀이1) DFS 이용 풀이 시간: 30분 이내 1) 문제 해결 아이디어 dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수) 를 넘겨주게 했다. dfs를 호출할 때마다 모음, 자음 개수도 함께 변경하여 넘겨주기 때문에 암호..
[백준] 1018번 - 체스판 다시 칠하기 풀이 시간: 40분 이내 1) 문제 해결 아이디어 n * m 의 보드에서 8 * 8의 크기로 잘라 체스판 처럼 인접한 검정색, 흰색이 번갈아가게 색을 칠해야 한다. 다시 칠해야하는 칸의 최소 개수를 구하는 문제로 모든 경우의수를 확인해봐야하는 완전탐색 문제다. n * m 의 2차원 리스트에서 r * c의 2차원 리스트를 추출하는 방법이다. 1. for문 이용 아래의 글에 의하면 numpy를 이용하면 쉽게 구할 수 있지만 코딩테스트에서는 보통 라이브러리 사용을 못하는 경우가 많으므로 꼭 기억해두자!! graph = [[0] * m for _ in range(n)]# n * m # n * m 2차원 리스트에서 r * c 2차원 리스트 추출하기 for i in ran..
[백준] 7568번 - 덩치 풀이 시간: 10분 이내 1) 문제 해결 아이디어 이 문제는 아주 쉽게 해결할 수 있는 문제였다. N명의 몸무게, 키 정보로부터 각 사람의 덩치 등수를 구해 출력하는 문제로 자신을 제외한 다른 사람들과 모두 비교를 해야하는 완전 탐색 문제다. 덩치가 크다는 의미는 몸무게, 키 2개 모두가 남보다 커야하기 때문에 이 조건을 만족할 때마다 카운트를 하면된다. 2) 소스코드 import sys input = sys.stdin.readline n = int(input()) # 사람 수 # n 명의 몸무게, 키 graph = [list(map(int, input().split())) for _ in range(n)] rank = [] # 덩치 등수 for i in range(n): c..
[백준] 14888번 - 연산자 끼워넣기 풀이 시간: 60분 이내 문제의 아이디어를 떠올리고 구현하는 것 자체는 30분 정도 걸렸는데 반례를 찾아 오류를 고치느라 시간이 오래 걸렸다. 추후 복습이 필요한 문제! N개의 수와 N - 1 개의 연산자가 주어졌을 때, 만들 수 있는 식의 최댓값과 최솟값을 구하는 문제로 DFS로 풀거나 permutations 라이브러리를 이용하면 푸는 방법 2가지가 있다. 처음에 입력받은 +, -, *, / 의 개수(cnt)로부터 연산자 리스트(operator)를 만드는 것이 중요하다. +, -, *, / 는 차례로 0, 1, 2, 3 이라고 생각하고 해당 개수에 따라 값을 넣어 리스트를 만든다. + - * / 0 1 2 3 예를 들어, 입력받은 연산자 개수가 0 1 0 2 이..
