모항이코딩한다

그리디 알고리즘의 개념 부분적인 최적 전략을 반복적으로 취하는 알고리즘이다. 당장 눈앞에 놓인 것들 중 제일 이득인 선택지를 골라잡아가며 해결하는 방식도 그리디 알고리즘 중 하나이다. 어떤 문제가 그리디인가? 각각의 부분 문제의 최적해들이 전체 문제의 최적해의 일부인 문제. 그리디 문제를 풀 때 고려해야 하는 것 전체 문제를 어떻게 쪼개어 부분 문제들로 나눌 것인가? 각 부분 문제의 최적해를 구할 방법, 즉 부분 문제의 최적 전략은 무엇인가? 그 최적 전략 실행의 제약사항은 없는가? 있다면 어떻게 충족시킬 것인가? 부분 문제들에 대해 특정 순서로 최적 전략을 반복하면 정말로 전체 문제의 최적해가 나오는가? 일반적으로, 아무리 어려운 그리디 문제라도 대부분 위와 같은 사고의 과정이 어려울 뿐 복잡한 자료구..

동적 프로그래밍의 개념 전체 문제를 여러 개의 부분 문제로 나누어 풀 수 있을 때에 사용하는 문제풀이법이다. 예를 들어 팩토리얼을 구한다고 하자. 1! 부터 100!까지를 모두 구하라는 문제가 주어졌다. 그런데, 5!을 구하려고 할 때 $1 \times 2 \times 3 \times 4 \times 5$ 와 같이 네 번의 곱셈연산을 수행할 수도 있지만, 이미 4!의 값을 알고 있다면 4!$\times 5$ 와 같이 한 번의 곱셈연산으로 5!를 구할 수 있다. 빨간 글씨의 방법처럼 각 팩토리얼을 구하면 1!을 구하기 위해서 0번의 곱셈, 2!을 구하기 위해서 1번의 곱셈, 3!을 구하기 위해서 2번의 곱셈, ... 100!을 구하기 위해서 99번의 곱셈이 필요하다. 총 4950번의 연산이 필요하다. 파란..

9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 수학 DP로 풀 수도 있고, 수학적으로 증명하여 풀 수도 있는 문제이다. 아래는 수학적 증명을 통해 문제를 풀어낸 과정이다. 2022.04.04 어떻게 풀지 고민하던 중, 카테고리가 DP라는 것을 발견했다. DP 문제의 풀이를 도저히 모르겠을 때 꿀팁이 있다. 펜과 종이를 꺼내서 첫 몇 개의 경우의 수를 직접 계산해 보는 것이다. 그럼 데이터의 규칙성이 눈에 띄게 된다. 이 규칙성을 이용해 점화식을 세우면 DP식 해결법을 찾아낼 수 있다. DP는 노가다가 통한다는 점이 참 좋은 것 같다. 그래서 돌멩이 한 개의 경우부터 열 개의 경..

풀이방법 2022.04.02 조건문을 사용하여 풀면 되는 문제이다. 한 글자 당 count 변수를 1씩 늘려주되, 크로아티아 특수문자에 해당하는 글자가 있다면 인덱스를 조정하여 한 글자 혹은 두 글자를 건너뛰어주면 된다. ArrayIndexOutOfBounds 오류가 발생하지 않도록 신경 써야 한다. 코드 Java(2022.04.02) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub Bu..

풀이방법 사용된 것: BigInteger 2022.03.31 매우 큰 숫자를 다룰 때 사용하는 BigInteger 클래스를 이용하거나, $n!$의 인수를 활용해 0의 개수를 세면 풀 수 있는 문제이다. 아래는 BigInteger 클래스를 사용한 정답 코드이다. 코드 Java(2022.03.31) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method s..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.30 "ACAYKP"와 "CAPCAK"를 예로 들어 설명하겠다. 다음의 표를 보자. C A P C A K A 0 1 1 1 1 1 C 1 1 1 2 2 2 A 1 2 2 2 3 3 Y 1 2 2 2 3 3 K 1 2 2 2 3 4 P 1 2 3 3 3 4 C A P C A K A 0 1 1 1 1 1 C 1 1 1 2 2 2 A 1 2 2 2 3 3 Y 1 2 2 2 3 3 K 1 2 2 2 3 4 P 1 2 3 3 3 4 (1, 1)은 "ACAYKP"의 첫 번째 글자까지와 "CAPCAK"의 첫 번째 글자까지, 즉 "C"와 "A"를 비교하였을 때 가장 긴 공통 부분수열의 길이이다. "C"와 "A"는 서로 공통된 글자가 하나도 없으므로 (1, ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) TreeSet 각각의 동전의 가치 값들을 저장하는 데 트리셋을 사용하였다. 중복값을 없애기가 편하고, 집합에 포함된 모든 값을 각각 한 번씩만 이용할 때 pollFirst()가 편해서 사용하였다. 2022.03.30 다이나믹 프로그래밍 문제이다. k원의 금액을 만들어야 할 때, 1원의 금액의 경우부터 k원의 금액에 이르기까지 자신보다 적은 금액의 동전 개수를 이용해 자신의 금액을 구해가며 차근차근 최적의 데이터를 알아낼 수 있기 때문이다. 크기가 k+1인 정수형 1차원 배열 dp를 만든 다음, dp[i]에 i원을 만들기 위한 최소의 동전 개수를 저장한다. 그 후 dp[k]의 값을 이용하여 답을 구하면 된다. 첫 몇 개의 데이터를 가지고 손으로 직접 구해보면..

백준 4344번 문제를 풀다가 유용한 메소드를 알게 되어 정리해둔다. 문자열, 정수, 날짜와 시간 등 여러 가지 형식으로 데이터를 재단할 수 있다. public static String format(String format, Object... args);//형식 설정 public static String format(Locale l, String format, Object... args);//국가별로 다양한 형식 설정

풀이방법 사용된 것: 반복문 2022.03.29 매우 간단한 문제이다. 문제에서 말하는 과정을 계속 반복해주면서, 몇 번 반복했는지 세어주면 된다. 앞 숫자는 (수)/10 으로, 뒷 숫자는 (수)%10 으로 구할 수 있다. 코드 Java(2022.03.29) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new Inp..

풀이방법 사용된 것: BufferedReader BufferedWriter 2022.03.29 빠른 입출력 방식을 사용해야 풀리는 문제이다. Scanner와 System.out.print의 반복적인 사용으로는 풀 수 없다. BufferedReader, BufferedWriter, StringBuilder 등을 사용하면 된다. 문제는 쉽지만 궁금증이 하나 생겨서 적어둔다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokeniz..