Coding Test (50) 썸네일형 리스트형 [백준] 15686번 - 치킨 배달 (구현 + 백트래킹) 문제 링크: https://www.acmicpc.net/problem/15686 구현 문제는 특히나 명확한 풀이를 생각해내지 못하면 정답을 못맞추는 채로 시간만 흘러간다. 따라서 문제를 도식화해서 100프로 이해를 해야한다.1. 문제 이해두칸 사이의 거리 공식: |r1 - r2| + |c1 - c2|0은 빈칸, 1은 집, 2는 치킨집집과 가장 가까운 치킨집과의 거리 = 치킨 거리모든 치킨 거리의 합 = 도시의 치킨 거리M개의 치킨집을 고른 도시에서 가장 작은 도시의 치킨 거리 구하기2. 문제 제약N: 2 ~ 50M: 1 ~ 133. 문제 풀이M개의 치킨집 고르기: 조합이므로 백트래킹가장 작은 도시의 치킨 거리 구하기각 집과 치킨 집 사이의 거리 중 가장 작은 값 구하기집을 기준으로 가장 짧은 치킨집 거리.. [Programmers] 84512번 - 모음사전 (백트래킹) 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839문제 정의: 모음의 개수만큼 조합한 문자열의 순서를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)word의 길이는 1 이상 5 이하입니다.word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.2. 문제 풀이1. 문제 접근모음을 조합해서 문자열을 생성할수있다. 문제에서 주어진 조건을 만족하는 해(word)의 조합을 찾아야하므로 완전탐색을 써야한다.word가 AAAAE인 경우, "A" -> "AA" -> "AAA" -> "AAAA" -> "AAAAA" -> "AAAAE" 이므로 6번째 단어이다.각 모음마다 모든 모음을 탐색하는 .. [Programmers] 86971번 - 전력망을 둘로 나누기 (간선 제거 후 DFS 완전탐색) 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971문제 정의: 트리에서 간선을 하나 끊고 두개로 나눠진 트리의 가장 작은 개수 차이를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)n은 2 이상 100 이하인 자연수2. 문제 풀이1. 핵심 풀이 접근일단, 양방향 그래프를 분할했을때의 분할된 두 트래의 개수차가 가장 적은 차를 구해야한다. 그래프 탐색를 해야하고 모든 경로를 탐색하는 완전탐색 문제이다.이문제에서 핵심은 "트리 분할을 어떻게 할것인가?" 였다.주어진 간선으로 트리를 끊을 생각을 했어야했다.1. 간선을 끊은 트리의 완전 탐색트리는 일반적인 그래프 탐색이 필요하므로 DFS, BFS 중에 아무거나 쓰면된.. [Programmers] 87946번 - 피로도 (백트래킹) 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946문제 정의: 여러 던전중 가장 많이 탐색할수있는 던전의 개수는?문제의 제약 파악 (입력값 크기, 상수 조건)k는 1 이상 5,000 이하인 자연수입니다.dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.2. 문제 풀이1. 문제 접근모든 던전을 시작점으로부터 탐색 가능한 모든 경로를 찾는 것이므로 완전탐색을 수행해야한다. 그리고 다음 조건을 만족해야하므로 백트래킹이 떠올랐다.탐색가능: 남은 피로도 - 최소 필요 피로도 >= 0탐색 경로 복원: 남은 피로도 -= 소모 피로도2. 핵심 문제 풀이 도출그러면 일반적인 백트래킹 로직에다가, 방문한.. [Programmers] 42842번 - 카펫 (Brute Force) 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=java문제 정의: 노란색 직사각형이 가운데 위치하는 카페트의 가로와 세로를 찾아라.문제의 제약 파악 (입력값 크기, 상수 조건)갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.2. 문제 풀이1. 문제 접근직사각형을 나눠떨어지는 약수로 가로와 세로를 정한다.카펫의 가로 세로는 Y로 만드는 직사각형의 가로 세로 보다 +2 이상 커야한다.카펫은 Y와 B로 생성할수있다.따라서 Y로 생성한 직사각형.. [Programmers] 42839번 - 소수 찾기 (Backtracking) 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839문제 정의: n자리수애서 각 자리수의 조합으로 만드는 모든 소수를 판별해서 카운팅문제의 제약 파악 (입력값 크기, 상수 조건)numbers는 길이 1 이상 7 이하인 문자열numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미2. 문제 풀이1. 문제 접근나는 문제를 다음의 4가지로 크게 나누었다.,모든 자리수의 조합 찾는 로직문자열을 숫자로 변환하는 로직소수 찾는 로직소수를 카운팅하는 로직완전 탐색 문제란것은 알았지만, 곧바로 백트래킹으로 풀생각을 못했다.아래와 같이 조합하는 경우의 수를 나열해보면.. [백준] 16928 - 뱀과 사디리 게임 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/16928문제 정의: 주사위를 던져서 나온 눈만큼 이동하거나, 사다리를 만나면 올라가거나, 뱀을 만나면 내려가는 모든 탐색 경로에서 최단거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?주사위를 던져서 나온 눈만큼 이동하거나, 사다리를 만나면 올라가거나, 뱀을 만나면 내려간다. 1번재 칸부터 시작해서 이동한 지점이 100번 칸이 될때까지 이동한 경로중 최단거리를 찾는 것이다. 이 문제는 2차원 좌표로도 표현할수있지만, 100만큼 이동하면되므로 좌표를 .. [백준] 2206번 - 벽 부수고 이동하기 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/2206문제 정의: N×M의 행렬에서 0 값만 이동가능하고 1값은 딱 한번만 이동이 가능하다. (1, 1)에서 (N, M)의 위치까지 걸리는 최단거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)점 N(0 ≤ N ≤ 1000), K(0 ≤ K ≤ 1000)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일반적인 문제풀이와 같이 벽을 안부수을때의 최단거리는 12이다.0 1 1 0 0 00 1 0 0 1 00 0 0 0 1 0 다만, 하나의 벽을 부수는 경로는 4가지이다.벽 좌표 (1, 1): 최단거리 10벽 좌표 (0, 2): 최단거리 12벽 좌표 (2, .. 이전 1 2 3 4 ··· 7 다음