Algorithm & Data Structure

[JAVA] 백준 9461번 : 파도반 수열

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그..

[JAVA] 백준 11726번 : 2Xn 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 - 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력. 풀이 처음부터 노가다로 구해보니까 점화식이 나왔다. DP[N] = DP[N-1]+DP[N-2] 임을 확인할 수 있다.. public class bj11726 { public static void main(String[] args) { //..

[JAVA] 백준 2225번 : 합분해

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 - 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램 - 덧셈의 순서가 바뀐 경우 다른 경우로 셈(1+2와 2+1은 다른경우) - 한 개의 수를 여러번 쓸 수 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200) 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력. 풀이 만약 입력에 5, 3가 주어졌다고 가정했을 때, 생각할 수 있는 경우의 수는 아래와 같다. 5 = 0 (2번 더해서 0이 되는 경우)+ 5 5 = 1 (2번 더해서 1이 되는 경우)+ 4 5 = 2 (2번 더해서 2이 되는 경우)+..

[Algorithm] DP(Dynamic Programming) / 동적 프로그래밍이란?

DP(Dynamic Programming) 이란? 동적 프로그래밍이라고도 불리는 동적 계획법은 분할 정복 기법과 굉장히 유사하다. 분할 정복 기법이란, 알고리즘을 짤 때 큰 문제를 한 번에 해결하지 않고 작은 여러 개의 문제로 나누어서 푸는 기법이다. 이렇게 풀다보면 같은 문제를 반복적으로 풀게되는데, 이를 매번 재계산하지 않고, 값을 저장해두었다가 재사용하는 기법이 바로 동적 계획법이다. 동적 계획법의 종류 Top-down - 하향식 계산법 - 큰문제부터 시작해 작은 문제로 분할 - 메모제이션 : 동일한 계산을 반복해야 할 경우, 한 번 계산한 결과를 메모리에 저장해두었다가 꺼내씀으롰 중복계산방지를 할 수 있게 하는 기법으로, 동적 계획법의 핵심 기술이다. 즉, 메모리라는 공간비용을 늘림으로써 계산에 ..

[Data Structure] 큐(Queue)란?

큐(Queue) 란? Queue는 차례를 기다리는 사람이나 승용차의 열 이라는 의미도 가지고 있는데, 이런 대기열은 줄을 선 순서대로 앞에서 부터 빠져나가게 된다. 이처럼 큐는 나중에 집어넣은 데이터가 먼저나오는 스택과는 반대되는 개념으로, 가장 먼저 들어온 데이터가 가장 먼저 나가게 되는 구조이다. 따라서 큐는 '선입선출 방식의 자료구조', 또는 'FIFO(First in First Out)의 자료구조 라고 한다. 데이터를 넣는 것은 Enqueue, 반대로 데이터를 꺼내는 것을 Dequeue 라고 하며 새로운 데이터가 들어가는 위치는 가장 뒤인 Back에 들어가게되고, 데이터 나가는 위치는 가장 앞인 Front에서 꺼낸다. 큐 연산 - enqueue : 큐에 데이터를 저장함 - dequeue : 큐의 ..

[Data Structure] 스택(Stack)이란?

스택(Stack) 이란? - 스택은 접근하는 것이 제한되어있는 나열 구조 - 삽입과 삭제가 목록의 끝인 "Top"에서만 가능하다. 쉽게 생각해서 말그대로 stack, 쌓여있는 것으로 예를 들어, 바닥에 동전을 여러개 쌓아올린다고 했을때 다시 동전을 치우려면 가장 나중에 쌓은 동전부터 치울 수 밖에 없다. 이처럼 스택은 한쪽이 막힌 구조라, 나머지 한 쪽에서만 넣고 뺄 수 있어 나중에 들어간 것이 먼저 나올 수 밖에 없는 구조이다. 그래서 스택은 '후입선출 방식의 자료구조', 또는 'LIFO(Last-In, First Out) 구조의 자료구조' 라고도 불린다. 자료를 넣는 것을 푸쉬(push), 반대로 꺼내는 것을 팝(pop)이라고 한다. 스택 연산 - pop() : 스택의 가장 윗 데이터(마지막에 저장된..