늦깍이 코린이

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 문제 문제 풀이 기본 재귀함수 문제다. 푼 방법 1) base case 를 생각한다. 2) 피보나치의 수는 0 과 1로 시작한다. 첫 번째, 두 번째 수가 이미 정해져있으므로, base case는 fibo(0), fibo(1)이 되겠다. 3) 피보나치는 f(n) = f(n-1) + f(n-2)를 하면 되는데, 앞서 base case가 설정되어있기 때문에, 0..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 기본 재귀함수 문제다. *재귀함수란? - 본인을 다시 호출하는 함수 - (주의) 본인을 다시 호출하는 함수이기 때문에 무한 루프에 빠질 가능성이 있다. - (중요) 무한 루프에 빠지지 않기 위해 base case를 만들어 놓는 것이 매우 중요 푼 방법 1) 정수 N 이 1일때, 1을 return해주는 base case 를 만들어 무한 루프에 빠지지 않도록 한다. 2) 정수 N 까지의 곱을 구하는 팩토리얼이므로, factorial 함수는 정수 N 과 factorial(N-1)이 계속해서..

인프런의 '영리한 프로그래밍을 위한 알고리즘 강좌' 내용 정리입니다. Recursion이란? 자기 자신을 호출하는 함수 ( 재귀 함수 ) pubilc class Code01 { public static void main(String [] args) { func(); } public static void func() { System.out.println("Hello..."); func();// 재귀 함수 } } 무한 루프에 빠지지 않는 재귀 함수 적어도 하나의 recursion에 빠지지 않는 경우를 만들면 된다. pubilc class Code01 { public static void main(String [] args) { int n = 4; func(n); } public static void func..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 문제 풀이 전형적인 큐 문제이다. 순서대로 k번째 사람에 접근해야되는데, 큐 문제가 될 수 있는 이유는 Circular queue를 생각하면 된다. 원을 이루고 있기 때문에, 1번째부터 k-1번째 사람을 순서대로 뒤로 붙여, 순서를 뒤로 미루는 방식으로 접근하면 된다. k번째 사람이 1번째 순서가 될 때까지 앞의 사람들을 다 뒤로 보내고 k번째 사람이 1번째 순서가 되면 해당 사람을 빼버리면 된다. 푼 방법 1. 큐를 두 개 만든다.(qu, qu2) 2. 1부터 N까지 순서대로 qu..

scanner 보다 BufferedReader가 빠르기 때문에 필자는 BufferedReader만 쓴다. BufferedReader 백준 문제풀이를 할때, 처음에 제일 어려웠던 건 입력 받는 방법 자체였다. 그렇기 때문에 BufferedReader를 통해 어떻게 입력을 받을 수 있는지 정리해보자. import 해야하는 것들 // 기본적으로 import 해야하는 패키지들 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; // 공백을 기준으로 한 줄을 나눠서 받고 싶을 때 import java.util.StringTokenizer; main public static void main(Strin..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 문제 풀이 백준 10828번 스택과 매우 유사한 구현 문제이다. 큐(queue)와 스택(stack)의 차이를 알고 있다면 구현에 어려움은 없을 것이다. 큐와 스택의 차이는 큐는 FIFO(First In, First Out), 스택은 LIFO(Last In, First Out), 즉 선입선출, 후입선출의 차이가 있다는 걸 알아야한다. LIFO : 스택의 후입 선출은 들어온게, ..

Queues란? FIFO(First In, First Out) 선입 선출 리스트의 제한된 형태 : 한쪽 끝에서만 넣고, 다른 쪽 끝에서만 뺀다. Enqueue(넣기) Dequeue(빼기) Front(맨 앞의 값) Rear(맨 뒤의 값) Array-based Queue의 경우 다음과 같이 계속해서 사용하게 되면, 배열의 한쪽 끝으로 점점 이동하게 된다는 문제점이 있다. 따라서 아래와 같이 실행하였을 때, 영구적으로 배열을 사용할 수 있게 된다. 그림처럼 배열을 원이라고 생각하고, 한쪽 끝으로 점점 이동했을 때, 다시 맨 앞으로 돌아가서 재활용하는 방법을 사용하면 된다. 이를 코드로 생각해보면, 아래의 코드처럼 사용할 수 있다. enqueue(E item){ rearIdx = (rearIdx+1) % si..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 문제 풀이 스택의 구현 문제이다. 기존의 스택을 import해오는 것이 아닌 직접 구현하는 방식으로 하자. 푼 방법 1. 구현 시 노드(링크)와 배열을 통해 구현이 가능한데, 배열로 구현하도록 하였다. 2. 배열로 구현시 각 명령에 대해 어떻게 하는지 보도록 하자. *size의 초기값을 -1로 설정하였는데, 그 이유는 인덱싱을 할 때 size를 변형하지 않고 사용하고 싶었기..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 문제 풀이 전형적인 스택 문제이다. 0일 경우 pop을 해주고 나머지의 경우 push만 해주면 된다. 푼 방법 1. stack을 생성한다. 2. if else 구문을 사용하여 입력된 수가 0인 경우, stack.pop()을 해준다. 3. 입력된 수가 0 이외의 수을 경우, stack.push()을 해준다. JAVA code import java.io.IOEx..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 문제 풀이 전형적인 스택 문제이다. 자바의 경우 stack을 import해와서 사용하면 된다. 스택엔 push, pop, peek의 기능이 있다.(자바의 경우) push는 스택에 자료를 넣고, pop은 스택에서 자료를 뺀다. peek은 스택의 가장 나중에 들어간 자료를 보여만 주는 기능을 한다. NO가 나오는 ..