[12일차] TIL
[1] 오늘 공부한 내용 📝
재귀함수 알고리즘 문제
재귀 함수가 뭔가요?
- 백준 17478
- 링크: https://www.acmicpc.net/problem/17478
- 나의 코드
import java.util.Scanner;
public class Main {
static int N;
public static void ans(int i) {
String u = "____".repeat(i);
if (i < N) {
System.out.printf("%s\"재귀함수가 뭔가요?\"\n", u);
System.out.printf("%s\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", u);
System.out.printf("%s마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", u);
System.out.printf("%s그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n", u);
ans(i + 1);
System.out.printf("%s라고 답변하였지.\n", u);
}
if (i == N) {
System.out.printf("%s\"재귀함수가 뭔가요?\"\n", u);
System.out.printf("%s\"재귀함수는 자기 자신을 호출하는 함수라네\"\n", u);
System.out.printf("%s라고 답변하였지.\n", u);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
ans(0);
}
}- 풀이과정
재귀함수를 사용해서 문장을 출력하는 문제이다.
이 문제의 킥은 '____'를 i번 반복하는 것이므로 이 부분에 주의해야 한다.
맨 처음에 작성했던 코드는 아래와 같다.
import java.util.Scanner;
public class Main {
static int N;
public static void ans(int i) {
String u = "____".repeat(N);
// ... (중략)
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
ans(N);
}
}
이 코드의 문제는 repeat을 N번 반복하고, main()에서 ans(N)을 호출하기 때문에 언더바(_)만 N번 반복하고, 시작을 N에서 출발해버리는 엉뚱한 상황이 되었다. (뭔 N을 그리 좋아하는지..)
문제 해결책이 전혀 떠오르지 않아서 내사랑 GPT의 도움을 받았다.
이 문제는 어찌저찌 해결하긴 했다. 다른 분들 풀이도 찾아봐야겠다.
하노이의 탑
- 백준 1914
- 링크: https://www.acmicpc.net/problem/1914
- 코드는 아직 없다 (어려워서 추가 공부해야한다..)
재귀함수 관련 추가 학습 내용
재귀함수는 print 위치가 중요하다고 어디선가 들었었는데, 왜 중요한지 이해를 못 하고 있어서 강의를 찾아봤다.
public static void 재귀함수 (int i) {
if (n == 0) return;
else {
System.out.println(i + " "); // 출력: 3 2 1 (1)
재귀함수(n - 1);
System.out.println(i + " "); // 출력: 1 2 3 (2)
}
}
(1)처럼 print가 재귀함수 내 재귀함수 앞에서 사용되면 내림차순으로 출력되고,
(2)처럼 print가 재귀함수 내 재귀함수 뒤에서 사용되면 오름차순으로 출력된다.
이는 재귀함수를 만나는 순간 함수의 첫번째 줄로 올라가는데, 이때 재귀함수 앞에 print가 있으면 print 다음 재귀함수 호출이므로 n .. 3 2 1 내림차순으로 출력되는 것이다.
근데 재귀함수 뒤에 print가 있으면 print가 나오기 전에 재귀함수가 즉시 호출되므로 stack에 값이 쌓이게 된다
(ex. [1 2 3] → 1 pop → 2 pop → 3 pop ⇒ 1 2 3 출력).
그래서 뒤에 print가 있으면 1 2 3 .. n 으로 오름차순으로 출력되는 것이다.
순열 (Permutation)
- 정의: n개의 원소 중 r개를 뽑는 것 (순서 중요)
- 알고리즘 문제는 재귀함수로 푼다.
- 8P8 까지는 시간복잡도가 괜찮은데, 9P9가 되면 시간이 오래 걸려서 공간복잡도로 푸는 것 같았다 (이 부분을 통으로 놓쳐서 내 추측)
[2] 어려웠던 내용 😇
일단 하노이의 탑이 원리가 이해되려다가 실제로 옮겨보면 이해가 안 돼서 미치겠다. 이 부분은 강의를 찾아봐야 할 것 같다.
그리고 순열 부분도 코드는 이해가 됐는데, 이건 문제를 실제로 풀어봐야 할 것 같다.
GPT에게 순열 관련 문제를 뽑아내라고 했으니 일단 적어두고, 일단 브론즈부터 풀어야지
- 브론즈
1. 백준 10872 (Bronze 3) – 팩토리얼
2. 백준 10870 (Bronze 2) – 피보나치 수
3. 백준 2309 (Bronze 1) – 일곱 난쟁이
4. 백준 2750 (Bronze 2) – 수 정렬하기
- 실버, 골드
1. 백준 15649 (실버 3) - N과 M (1)
2. 백준 10974 (브루트포스, 실버 수준) - 모든 순열
3. 백준 1722 (골드 5) - 순열의 순서
[3] 궁금한 내용 / 부족한 내용 ⁉️
진심 전부 다 부족하고 궁금하다..
[4] 오늘의 총평 📮
아 너무 어렵다 진짜!!!!!! 특히 알고리즘을 자바로 풀자니 문법도 몰라서 미칠 것 같다 ㅜㅜ 알고리즘 잘 푸는 사람들은 어떻게 공부하길래 그런 알고리즘들이 떠오르는 건지 너무 궁금하다
알고리즘 공부 방법을 빨리 찾고 공부해야겠다 ..
