본문 바로가기

분류 전체보기

 (215)
백준 1003 피보나치 함수 (Java) 1. 문제 링크 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 N번째 피보나치 수를 구하는 과정에서 1번째 피보나치 수와 0번째 피보나치 수가 몇 번 호출되었는지를 구하는 문제이다. 초반인 0번 피보나치와 1번 피보나치를 잘 설정한다면 풀 수 있다. 그 이후에는 원래 피보나치를 구하는 것과 같이 arr[i] = arr[i-1] + arr[i-2]를 하면 된다. 이 식이 그대로 적용되는 이유는 N번째 수를 구하기 위해서는 N번과 N-1번째 수가 필요하고 그 과정을 쭉쭉.. 하면 결국 0번과 1번을 호출하게 되는데 그 과정에서 저장된 값을 계속 사용해야 하기 때문이다..
백준 1074 Z (Java) 1. 문제 링크 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 분할정복의 대표적인 문제이다. 4개의 범위로 나눠서 각 범위 안에 들어왔을 때 재귀한다. 점점 작은 범위가 되고 값을 찾게 된다면 size가 1이 되면서 재귀가 끝난다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static int visit, R, C; publi..
백준 16435 스네이크버드 (Java) 1. 문제 링크 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 과일의 높이를 정렬한다. 뱀의 길이와 비교하면서 과일의 높이보다 뱀이 길거나 같다면 과일을 먹을 수 있다. 과일 배열에서 첫번째를 지우고 뱀의 길이를 +1한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
백준 3040 백설공주와 일곱 난쟁이 (Java) 1. 문제 링크 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일곱 난쟁이 모자에 적힌 숫자를 전부 더한다. 거기서 두 값을 빼면서 100이 되는 경우를 찾았다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Excep..
백준 9084 동전 (Java) 1. 문제 링크 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp로 하는데 money[만들 수 있는 가격]에 경우의 수를 저장한다. 동전마다 만들 수 있는 경우의 수를 money 배열에 더한다. money 배열은 해당 동전으로 만들 수 있는 인덱스부터 시작해야 하기 때문에 j=i부터 시작하게 했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..
백준 18870 좌표 압축 (Java) 1. 문제 링크 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일단 clone()을 이용해 배열을 복사한다. 배열을 정렬하고 그 순서대로 HashMap에 추가한다. (Map이 중복 불가이기 때문) 그러면 그 보다 작은 수의 개수는 i가 아니라 index로 별도로 구해야 한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
백준 2563 색종이 (Java) 1. 문제 링크 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 100x100 도화지에 10x10 색종이를 붙인다. x 좌표와 y 좌표를 입력받을 때마다 반복문을 돌려서 각각 10칸씩 방문했다고 체크한다. 색종이 개수만큼 반복문을 돈 이후에는 전체 도화지에서 방문했던 칸의 수를 센다. 그 수가 바로 검은 영역의 넓이이다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class M..
백준 1992 쿼드 트리 (Java) 1. 문제 링크 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 N이 언제나 2의 제곱수라는 것에서 분할 정복을 해야한다고 생각했다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 압축이 된다고 하니 4분면으로 나누고 재귀를 했다. => round 메서드 (시작 x 좌표, 시작 y 좌표, 탐색할 길이) 만약 4분면이 모두 동일한 값이라면 재귀를 하지 않고 값을 내보낸다. => same 메서드 (시작 x 좌표, 시작 y 좌표, 검사할 길이) 4. 코..

티스토리툴바