본문 바로가기

알고리즘16

[코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. 1940년 Richard Bellman이 처음으로 Dynamic Programming이란 단어를 사용했는데 멋있어 보여서 이름 붙였다고 한다. (궁금해서 찾아보니까 벨만-포드 알고리즘의 그 벨만이 맞았다.) 다이나믹 프로그래밍으로 문제를 풀기 위한 조건 1. Overlapping Subproblem 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 2. Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 각 문제들은 Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정.. 2022. 8. 29.
[코딩테스트/ 백준 알고리즘] 15829번 : Hashing (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 문제 설명 문제 풀이 나머지 연산의 분배법칙을 모르면 풀기 까다로운 문제였다. (A * B) % m = (A % m) x (B % m) % m 이게 곱셈에서의 나머지 연산 분배법칙이다. 이 문제는 파이썬이면 아무 생각 없이 풀 수 있는 문제(파이썬은 수 범위가 무한이니까)지만 그 외 언어를 쓴다면 나머지 연산에 작업을 해주어야 한다. 그렇지 않으면 31⁵⁰이라는 엄청난 범위의 수를 담아낼 .. 2022. 8. 4.
[코딩테스트/백준 알고리즘] 1920번 : 수 찾기 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 설명 코드 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedWriter bw = new BufferedWrit.. 2022. 8. 4.
[코딩테스트/백준 알고리즘] 10816번 : 숫자 카드 2 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 설명 문제 풀이 계수 정렬(카운팅 정렬)을 할 때 사용하는 방법을 사용하기로 했다. 계수 정렬은 정렬할 데이터에 해당 요소가 몇 개씩 있는지 센 후 이를 앞 순서대로 차례대로 써주면 된다. 계수 정렬 예시 ex) 입력 데이터 : {1, 1, 4, 7, 8, 5, 6, 2, 3, 3, 7 ,7 ,9, 10} 1 : 2개 2 : 1개 3 : 2개 4 : 1.. 2022. 8. 3.

티스토리툴바