CodingTest

퍼즐게임챌린지문제설명난이도, 현재시간이 입력값으로 주어진다.그때 가지고 있는 숙련도가 있는데 숙련도보다 난이도가 높다면 (이전시간+현재시간) * 차이나는 횟수 + 현재 시간을 총 더했을 때 제한 시간보다 작아야한다. 그때의 숙련도의 최소값을 구하면 된다문제 해결 방법나는 처음에 단순 구현으로 숙련도를 1부터 늘려가서 총 시간이 제한시간보다 작을 때까지 while문을 돌렸다.그랬더니 시간초과가 났다... 그래서 숙련도의 최솟값을 찾는것, 그리고 1부터 늘려나가는건 비효율 적이라고 생각해서 그럴 때는 이진탐색 방법을 사용해야 한다고 깨달았다. start와 end 는 최솟값이랑 최대값으로 설정을 해준다.int start = Integer.MAX_VALUE;int end = Integer.MIN_VALUE;//..

삼성 코테를 준비하면서 코드트리를 써봤는데, 문제별로 유형이 다양해서 매번 문제를 고르는 나한테 딱이었다..그래서 요즘은 백준, 프로그래머스 보다 코드트리를 쓰는 중.. 코드트리 모든 문제를 푸는 게 목표(?)  BackTracking: 가능한 수열 중 최솟값 구하기문제설명4,5,6으로 만들 수 있는 수열 중에서 인접한 연속 부분 수열 중에서, 사전순으로 (오름차순)에서 가장 앞에 있는 수열을 출력하기 해결방법1. 중복 순열을 만든다.2. check()함수를 만들어서 만든 중복 순열이 인접한 부분이 있는지 없는지 확인해준다. ==> 결론: 시간초과 ㅜ_ㅜ 내가 했던거는 대강 3^(n^3)이정도 인듯하다. 인접한 수열을 확인하는 부분에서 3중배열로 돌렸기에 이런 결과가 난듯하다. 그래서 다른 해결 방법을 ..

BackTracking: 아름다운 수 문제설명n자리 아름다운 수가 몇 개 있는지 출력한다.여기서 "아름다운 수"란 각 숫자마다 반복되는 숫자가 일치하는 것을 말한다. 만약 1이 나오면 1이 1번 반복되어야 하고, 3이 나오면 3이 3번 나와야 한다. 이것을 모두 만족 하는 것이 아름다운 수이다. 해결방법1. n자리 숫자를 중복 순열로 만들어준다. (완전탐색을 하는 것)2. 순열로 만든 숫자를 모두 검사해서 "아름다운 수" 인지 아닌지를 판별한다.3. 만든 순열이 아름다운 수인지 만족하는 것만 개수를 세서 출력한다.  중복순열을 만든 것까지 코드를 짰는데 아름다운 수를 판별하는 방법이 좀 이해가 안갔다.판별하는 방법은 시작점(시작하는 위치: i)부터 그 시작점이 가리키는 값(arr[i])까지 같은 숫자를 ..

#13023 ABCDE문제설명5명의 인물이 모두 연결 되어 있으면 1출력5명의 인물이 모두 연결 되어 있지 않으면 0을 출력해준다.  해결방법친구관계의 연결을 '이중행렬'로 표현했고 관계파악은 dfs와 백트래킹으로 해주었다. 여기서 다시 유의할 점은1. 시작 노드가 정해지지 않았으니까 모든 경로에서 dfs를 돌려야한다.2. A부터 D까지 경로는 5니까 cnt가 5일때까지만 찾으면 된다.3. 백트레킹으로 경로가 실패한 경우에는 되돌아가줘야 한다. 전체코드더보기import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BojA..

#1074 Z문제설명1. N이 주어진다. 여기서 N은 2^N * 2^N으로 주어진다.2. 행과 열이 주어질 때, 몇번째로 그 행과 열을 방문한지 출력해야 한다.    해결방법고안1. 예시를 보면 분할 정복 문제임을 알 수 있다. 1사분면, 2사분면, 3사분면, 4사분면으로 계속해서 나눌 수 있다.2. 따라서 재귀로 몇사분면인지 찾고, 몇번째로 방문했는지 계속해서 더하면 된다. 그래서 find함수를 작성해서 사분면으로 나누고 몇번째인지 count를 더해주었다.private static void find(int r, int c, int size){ if(size == 1) { return; } if(r = size/2){ //2사분면 find(r, c-size/2, ..

#2110 공유기 설치문제 이해처음에는 문제 이해가 가지 않았다.... 흠냐문제를 이해하자면 우선, '거리'에 집중하면 된다. 1. 집 n 개가 있다.2. 집의 좌표가 주어진다.3. 공유기의 개수가 주어진다.4. c개의 공유기를 n개의 집에 설치한다.5. 이때 최대 거리를 출력한다.    해결방법 고안'이진탐색'으로 접근하자 나는 이진탐색 문제라고 해서 항상 하던 것처럼 인덱스를 잘라서 접근하려고 했다..근데 이번에는 거리에 이진탐색으로 반씩 줄여서 접근하면 된다.최소부터 최대까지, 공유기를 설치할 수 있는 수에서 거리의 최댓값을 구하면 되는 것이다 나는 무슨 단어에 집착하는 경향이 있는데 이번에도 '인접한'이라는 단어에 넘어가서 좀 헤맸다. ㅜ_ㅜ이진탐색으로 구한 거리를 사용해서 집에 설치, 그 집 좌..

문제 이해 문제보러가기   문제 이해부터 해보자.핵심은 아래와 같다.   이렇게 갈 수 있는 거리의 최대값을 구해야 한다.!!!! 문제 이해를 하면 DFS + 백트레킹이 떠오를 것이다.Why?1.  모든 가능한 경로를 탐색하면서 가장 긴 경로를 찾는 유형의 문제 -> dfs2. 각 경로에서의 최대 길이를 저장하고, 경로의 조건에 맞지 않는 경우 -> 백트래킹  해결방법 고안 K만 없으면 그냥 dfs 하면 되는데 k 때문에 고려해야 하는 상황이 있다;; 그래서 K를 아직 안쓴 경우와, K를 써버린 경우로 나누었다.    k가 없을 때 로직// k가 없을 때if (!flag) { // 자신보다 작으면 이동 if (h > map[nx][ny]) { visited[nx][ny] = tru..

#3109 빵집문제보러가기 문제이해1열에서부터 마지막 열까지 도착해야한다.한번 방문한 곳은 다시 방문할 수 없다오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선을 방문할 수 있다.해결 방법 고안1. dfs라고 생각했다. 그 이유는 경로를 찾는거여서 한길을 찾으면 마지막 열에 도착할 수 있는 길을 계속해서 찾아야 했다.2. 방문 처리가 필요하다. 한번 선택하면 다시 선택할 수 없어서 visited를 true로 놓으면 된다.3. 백트래킹은 필요없다. 마지막 열에 도착하면 바로 return 한다. 코드더보기import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTok..