늦깍이 코린이

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 문제 풀이 정렬 문제다. 한번 틀림😇 삽입 정렬의 시작 복잡도는 O(n²)이다. 너무 오래 걸린데!!! 단순히 출력문 문제일줄 알았는데 아니였다. Tim Sort로 풀어야하는 문제이다. Merge Sort(합병 정렬) + Insertion Sort(삽입 정렬)이 합쳐진 정렬이다. 아직 정확히 몰라서 구글링을 했다... 푼 방법 1) 시간을 지키는 게 매우 중요한 문제니까, Buff..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 문제 풀이 브루트포스 알고리즘(Brute Force Algorithm)이란? Brute Force 난폭한 힘을 의미한다. 모든 숫자를 다 넣어서 조합해 맞춰보는 알고리즘이다. 해당 문제의 경우, 한 사람의 키와 몸무게를 다른 모든 사람과 일일이 대조해보면 된다. 푼 방법 1) 키와 몸무게를 담을 배열을 만든다.(2차원 배열로 만들어도 되지만, 그냥 1차원 배열 두 개로 했다.) ..

https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제 문제 풀이 전형적인 재귀 문제다. 구현할 때 헷갈렸던 부분 "라고 답변하였지." 를 어떻게 구현해야할까? 푼 방법 *지역변수와 전역변수를 잘 활용하자. 1) "____"를 담아둘 전역 변수 underbar1를 ""로 초기화하여 생성한다. 2) 재귀함수 내의 지역 변수 down을 "____"로 저장한다. 3) 지역 변수 underbar를 전역 변수 underbar1의 값을 받도록 한다. *1..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 문제 풀이 전형적인 재귀함수 문제다. 왜 재귀인가? 1) N개의 원판이 있을 때, 크기가 N인 마지막 원판을 1 ➡ 3으로 옮겨야한다. 2) N - 1 개의 원판들이 모두 1 ➡ 2로 옮겨져야한다. 3) 크기가 N - 1인 마지막 원판을 1 ➡ 2로 옮겨야한다. 4) N - 2 개의 원판들이 모두 1 ➡ 3으로 옮겨야한다. ... ... 1) ~ 4)와 같은 순서로 계속 반복될 ..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 // 입력 27 // 출력 *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** *************************** * ** ** ** *..

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)이 계속해서..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 문제 풀이 전형적인 큐 문제이다. 첫 번째 수는 버리고, 두 번째 수는 맨 뒤로 보내 순서를 바꾸는 것을 반복하면 된다. 앞과 뒤가 있으므로 큐를 활용하는 것이 가장 좋다. 푼 방법 1. 큐를 만든다(qu) 2. 1부터 N까지 순서대로 qu에 넣어준다. (front = 1 , back = N) 3. while문을 통해 qu의 size가 1이 될 때까지(size가 1이 되면 break해준다.)..

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..