본문 바로가기

알고리즘 코딩테스트

[D-day] 기하 📍 기하점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘이다.실제 코딩 테스트에서의 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있다. 📍 CCW✅ 정의CCW(Counter-ClockWise)는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘이다.세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정할 경우 CCW의 공식은 다음과 같다.// CCW의 공식CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3)​✅ CCW 공식 도출 과정1. 첫번째 점을 뒤에 한 번 더 쓴다.2. 오른쪽 아래 방향 화살표 곱은 더하고, 왼쪽 아래 방향 화살표의 곱은 뺀다.✅ 방향에 따른 CCW의 결과CCW 결과의 절.. 더보기
[D-1] 11049 : 행렬 곱 연산 횟수의 최솟값 구하기(Java) 📍 백준 11049번시간제한메모리제한제출정답맞힌 사람비율1초256 MB41457185781340143.615%✅ 문제크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.같은 곱셈이.. 더보기
[D-2] 1915 : 가장 큰 정사각형(Java) 📍 백준 1915번시간제한메모리제한제출정답 정답맞힌 사람정답 비율2 초128 MB163204923380834.168%✅ 문제n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. ✅ 입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. ✅ 출력첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.  예제 입력 1 4 40100011111100010예제 출력 1 4​ ✅ 정답 코드더보기import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IO.. 더보기
[D-3] 10844 : 쉬운 계단 수(Java) 📍 백준 10844번시간제한메모리제한제출정답 정답맞힌 사람정답 비율2 초128 MB163204923380834.168%✅ 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. ✅ 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. ✅ 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 1예제 출력 1 9예제 입력 2 2예제 출력 2 17✅ 정답 코드더보기import java.util.Scanner; public class Main { static Long[][] dp;.. 더보기
[D-4] 14501 : 퇴사 준비하기(Java) 📍 백준 14501번시간제한메모리제한제출정답맞힌 사람비율2 초512 MB110687570253752550.740%✅ 문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다... 더보기
[D-5] 1722 : 순열의 순서(Java) 📍 백준 1722번시간제한메모리제한제출정답 정답맞힌 사람정답 비율2 초128 MB163204923380834.168%✅ 문제1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다.k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지.. 더보기
[D-6] 조합 📍 조합코딩 테스트에서 자주 출제되는 주제이다.동적 계획법을 이해하는데 기초가 되는 매우 중요한 장이다.조합 점화식 도출 방법에 대해 꼼꼼히 학습하는 것을 추천한다.✅ 정의조합(combination)은 n​Cr​로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.순서를 고려하지 않는다. ✅ 조합의 점화식1. 특정 문제를 가정하기- 적당한 조합 문제를 가정한다.- 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정해본다.2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기- 모든 부분 문제가 해결된 상황이라고 가정해본다.- 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.- 모든 부분 문제가 해결된 상황이라고 가정하는 방법은 조합뿐 아니라 다이내.. 더보기
[D-7] 최소 공통 조상 📍 최소 공통 조상✅ 정의트리 그래프에서 처음 공통으로 만나게 되는 부모 노드를 뜻한다.임의의 두 노들르 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 부르는 뜻이다. ✅ 핵심 이론일반적인 최소 공통 조상 구하기- 주로 트리의 높이가 크지 않을 때 구하는 방법이다.- 트리의 높이가 커질 경우, 시간 제약 문제에 직면할 수 있다. 이 경우 아래의 '최소 공통 조상 빠르게 구하기' 방법을 이용한다.✔️ 선택된 두 노드의 깊이가 다른 경우,     더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춘다.     이 때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다. ✔️ 선택된 두 노드의 깊이가 같은 경우,     동시에 부모 노드로.. 더보기

티스토리툴바