코딩 테스트

[백준][silver5][JAVA] 1010-다리 놓기

[문제 설명] www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이 과정] M개 중에 N개 선택하여 조합하는 경우의 수를 구하는 문제다. 조합 경우의 수를 구하는 방법은 여러가진데 메모이제이션을 이용하면 가장 효율적으로 풀 수 있다. * 메모이제이션을 이용한 조합 경우의 수 구하기 - 메모이제이션(memoization) 기법은 동적 프로그래밍의(dynamic programming)의 일종이다. 메모를 할 배열을 만들어 놓고 처음 계산한 값은 배열에 저장한다..

[백준][silver4][JAVA]터렛

[문제 설명] www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net [풀이 과정] 조규현, 백승환 각 좌표와 떨어진 거리를 반지름으로 원을 그려보면 두 원이 만나는지 여부를 알 수 있다. 두 원이 만나는 접점의 개수가 류재명이 있을 수 있는 좌표의 개수이다. 총 6가지 경우가 있다. 1. 두 점에서 만남 한 점에서 만남 2. 외접 3. 내접 반지름의 차 r1 + r2) 5. 두 중점 거리 < 반지름의 차이 (d < r2 - r1) 6. 두 중점..

[프로그래머스][Level3][Java]징검다리 건너기

[문제 설명] programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr [풀이 과정] 파라매트릭 서치(Parametric search)를 이용하여 푸는 문제다. 단순 코딩으로도 문제를 풀수는 있지만 파라매트릭 서치를 활용하지 않으면 효율성 체크에서 실패가 난다. 파라매트릭 서치는 이분탐색과 유사한 알고리즘으로 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. * 최적화 문제 - 최적의 해가 무엇인가를 묻는 문제 - 주로 문제 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제 * 결정 문제 - 어떤 조건이 예-아니요로 답이 있는 문제 예시)..

[프로그래머스][Level3]셔틀버스 -JAVA

[문제] https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr [풀이] 어떤 알고리즘을 알아야만 풀수 있는 문제가 아닌 문제에 주어진 상황을 코드로 구현할 수 있는지 보는 문제같다. 1. 큰 틀은 다음과 같이 구현했다. 1) 탑승객들을 빨리 도착한 시간 순서대로 줄 세운다(PriorityQueue 사용) ..

[프로그래머스][Level3][Java] 길 찾기 게임

[문제 설명] programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr [풀이 과정] 이진 탐색 트리(Binary Search Tree)의 개념을 확실히 알 고 있는지 보는 문제다. 1. 이진 탐색 트리를 만들 수 있는지. 2. 전위 순회(preOrder)로 이진 탐색트리를 조회 할 수 있는지. 3. 후위 순회(postOrder)로 이진 탐색트리를 조회 할 수 있는지. 풀이 과정은 다음과 같다. 1) 노드 클래스 만들기 이진 탐색 트..

[프로그래머스][Level3][JAVA] 야근 지수

[문제 설명] programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr [풀이 내용] 야근 피로도(각 작업량 제곱의 합)이 최소가 되려면 가장 큰 수의 작업량부터 처리해야 한다. 완전탐색으로 정답이 될 수 있는 모든 경우의 수를 나열해 보았는데 최소작업량이 더 작은 것보다 최대작업량이 더 작은것이 야근피로도가 더 적었다. 이유는 큰 수와 작은 수가 1차이가 나더라도 제곱의 차이는 확 커지기 때문이다. 따라서 주어진 n..