작심백일

[BOJ] 11047. 동전

https://www.acmicpc.net/problem/11047 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접근 방법그리디에 대한 기초 배낭 문제이다.그리디는 현재 시점에서 최적의 해를 찾는 방법이며, 가장 최적의 해를 찾지 못할 수도 있다.아직까지는 내가 무턱대고 작성한 코드를 그리디라고 이해하고 있다.거스름돈을 주는 것처럼 가장 큰 금액부터 나누어 몫과 나머지를 구하는 것을 반복했다. 소스 코드import java.util.*;import ..

[BOJ] 11053. 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net접근 방법일반적인 DP 문제이다. DP 연습을 위해 풀었었다. 소스 코드import java.util.*;import java.io.*;public class Main { public static void main(String args[]) throws IOException { BufferedReader b..

[BOJ] 18870. 좌표 압축

https://www.acmicpc.net/problem/18870 Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/18870" data-og-url="https://www.acmicpc.net/problem/18870" data-og-image="https://blog.kakaocdn.net/dna/cEz0Bg/hySE6fFv82/AAAAAAAAAAAAAAAAAAAAAHPvGZsH9AXtcUGP0ZoJrHH0m5fL7AUsrC65ehXuZwGX/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1756652399&allow_ip=&allow_referer=&signature=ksmswNMXGZpAyBNHbaSyo1iAmzA%3D 좌표 압축수직선 위에 N개의 좌표 X1..

[BOJ] 7568. 덩치

https://www.acmicpc.net/problem/7568 7568번: 덩치우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩www.acmicpc.net접근 방법단순히 정보에 대해 각각 배열을 생성하여 이름 대신 인덱스로 구분하였다.이중 반복으로 두 개의 수를 중복 없이 비교하여 더 작은 쪽의 덩치 등수를 1씩 증가시켰다. 소스 코드import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException ..

[BOJ] 2798. 블랙잭

https://www.acmicpc.net/problem/2798 2798번: 블랙잭첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장www.acmicpc.net접근 방법카드 세 장의 합을 내면 되므로 3 중첩 반복문을 사용했다.반복문만 해도 O(N^3) 라서 부담스러운 건 사실이다.조합 문제니까 아마 내가 애용하는 백트래킹도 가능할 듯하다. 소스 코드import java.util.*;public class Main { public static void main(String[] args) { Scanner sc..

[BOJ] 10870. 피보나치 수 5

https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가www.acmicpc.net접근 방법피보나치 수열은 유우명한 DP 문제이다.반복문을 돌리기 위해 F[0], F[1] 값을 미리 저장해 두고 식을 반복했다. 소스 코드import java.util.*;public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in)..

[BOJ] 1978. 소수 찾기

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.www.acmicpc.net접근 과정단순 반복문을 이용했다.1을 for문에 포함하면 나머지 검사를 할 수 없기 때문에 따로 검사해서 제외했다.이후 2부터 n 전까지의 수로 나머지 검사를 하여 완전히 나눠지면 제외했다. 소스 코드import java.util.*;public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.next..

[BOJ] 16171. 나는 친구가 적다 (Small)

https://www.acmicpc.net/problem/16171 16171번: 나는 친구가 적다 (Small)첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 100) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주www.acmicpc.net접근 방법단순 반복문을 이용했다. 해당 char이 숫자일 경우 공백으로 치환하고 공백을 없앴다. 그렇게 해서 나온 문자열이 비교 문자열에 포함되는지 검사하면 된다. 소스 코드import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOEx..

[SWEA] 5642. 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQm2SqdxkDFAUo  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com접근 방법DP 형식의 일반 탐색을 했다. DP 배열을 사용하기엔 굳이라는 생각이 들었다.처음에는 input이 단순해서 Scanner를 사용했는데BufferedReader를 사용했을 때보다 30000 kb, 800 ms 정도가 더 디뎠다.이러한 사소한 것에서도 부담이 클 수 있다는 걸 알게 됐던 문제였다. 소스 코드import java.util.*;import java.io.*; class Solutio..

[SWEA] 11315. 오목 판정

https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com접근 방법백트래킹을 이용했다.왼쪽 위에서부터 차례대로 탐색하기 때문에 4 방향(아래, 오른쪽, 오른쪽 아래, 왼쪽 아래)만 비교했다.돌이 있을 경우에만 탐색했고, 도중 리턴 하는 경우는(1) 연속된 돌이 5개일 경우(2) 검사하려는 인덱스가 초과일 경우(3) 해당 위치에 돌이 없을 경우 이다.1번의 경우 check(ck)를 유효화해서 해당 방향의 탐색이 끝나면 더 이상의 탐색을 하지 않을 수 있다. 소스 코드import java.util.*;import ja..

[SWEA] 5215. 햄버거 다이어트

https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com접근 방법DFS와 조합을 이용했다. 메뉴를 2차원 배열로 받아들였다.이중 재귀 반복의 시작 인덱스를 1씩 증가시키며 필참한 수는 제외했다. 소스 코드import java.util.*; public class Solution { static int[][] m; static int T, N, L, point; public static void main(String[] args) { Scanner sc = new Scanner..

[SWEA] 3750. Digit sum

https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com접근 방법단순히 반복문을 이용했다.수를 문자열로 받아서 한 글자씩 정수로 만들어 합을 구하고 합이 한 자리 수가 될 때까지 반복했다.어떻게 하면 형태 변환을 간단하고 적게 할 수 있을지 고민했던 문제 같다. 소스 코드import java.util.*;import java.io.*; class Solution { public static void main(String[] args) throws IOException { Scanner sc = ..