공부하는 블로그

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩� www.acmicpc.net 각 인원마다 키와 몸무게가 주어진다. 이 때 덩치 순서를 출력하는 문제이다. 덩치를 비교할 때에는 키와 몸무게가 모두 비교 대상보다 커야 덩치가 크다고 할 수 있다. 만약 키는 더 크지만 몸무게는 더 적게 나간다면 덩치는 비교할 수 없어 같은 순위로 기록되게 된다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new ..

2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 분해합이 주어지면 그 분해합을 만들 수 있는 생성자를 찾는 문제이다. 분해합이란 어떤 수 N과 N을 이루는 각 자리수의 합을 의미하는데 이 때 N을 생성자라고 한다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.clos..

Brute Force 브루트 포스(Brute Force)는 완전 탐색이라고도 불리는 알고리즘이다. 말 그대로 모든 경우의 수를 전부 체크해보는 알고리즘이다. 탐색 알고리즘 풀이 시 가장 간단하게 사용할 수 있으나 시간이 최대로 발생하게 된다. 보통 for문 / if문을 활용하는 방법과 재귀 함수를 이용하는 방법이 있다. Backtracking 백트래킹(Backtracking)은 깊이우선 탐색(DFS)를 기반으로 하는 일종의 트리 탐색 알고리즘이다. Algorithm | DFS & BFS DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다. DFS (Depth First Search) 깊이 우선 탐색(DFS)은 ..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전들의 가치와 총 가치 K가 주어진다. 이 때 총 가치 K에 딱 맞도록 하는 동전의 최소 개수를 찾는 문제이다. 쉽게 말해 거스름돈 문제라고 생각하면 된다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.n..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 주어진 수열에서 연속합이 가장 큰 경우를 찾는 문제이다. 연속합이란 수열에서 연속된 수를 선택해서 구할 수 있는 합이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] sum = new int[n];// i번째까지의 합을 저장하는 수열 int[] dp..

Binary Search 이진 탐색(Binary Search)은 오름차순으로 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다. 이진 탐색의 과정은 다음과 같다. 1. 배열의 중간에 위치한 임의의 값을 선택한다. 2. 선택된 값과 찾고자 하는 값 X와 비교한다. 3-1. X가 더 작으면 중간값을 기준으로 왼쪽에 있는 데이터들을 대상으로 1 - 3번을 반복한다. 3-2. X가 더 크면 중간값을 기준으로 오른족에 있는 데이터들을 대상으로 1 - 3번을 반복한다. 예시를 통해 이진 탐색을 이해해보자. {1, 5, 6, 8, 11, 15, 30, 33, 35, 48}의 배열에서 5를 찾아보자. {1, 5, 6, 8, 11, 15, 30, 33, 35, 48}에서 11을 중간값으로 선택하고 5와 비교한다. 5..

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 S(1) S(k+1) > S(k+2) > ··· > S(n-1) > S(n)을 만족하는 수열이다. 주어진 수열의 부분 수열 중에서 가장 긴 바이토닉 수열을 찾는 문제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열(Longest Common Subsequence, LCS)를 찾는 문제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.next(); String str2 = sc.next(); sc.clo..