[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 으로 오름차순으로 출력되는 것이다.

print가 재귀함수 앞에 있을 때 출력값

print가 재귀함수 뒤에 있을 때 출력값

 

순열 (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] 오늘의 총평 📮

아 너무 어렵다 진짜!!!!!! 특히 알고리즘을 자바로 풀자니 문법도 몰라서 미칠 것 같다 ㅜㅜ 알고리즘 잘 푸는 사람들은 어떻게 공부하길래 그런 알고리즘들이 떠오르는 건지 너무 궁금하다
알고리즘 공부 방법을 빨리 찾고 공부해야겠다 ..