[TIL] 2023.04.08(토)

WEEK01 - 컴퓨팅 사고로의 전환

이번주는 컴퓨팅 사고로의 전환 WEEK01주 차여서 파이썬을 사용하여 배열, 문자열, 반복문과 재귀함수, 시간복잡도, 정렬, 완전탐색, 정수론 등을 학습하는 시간입니다. 

 

평소 파이썬을 자주 사용해보지않아서 기초 문법이 많이 부족한 상태였는데 e-book과 유튜브 강의를 통해 조금이나마 발전할 수 있었던 것 같습니다. 

 

https://www.youtube.com/watch?v=T6z-0dpXPvU 

 

위 강의는 나도코딩 유튜브강의인데 100분짜리로 기본적인 문법들을 설명해 줘서 한 번쯤 듣기 좋은 거 같아요!

 

 

문제 소개

오늘 풀어본 알고리즘들 중에서 백준 알고리즘(9020번 - 골드바흐의 추측)과 (1914번 - 하노이탑)에 대해서 간단하게 정리해보려고 합니다.

 

 

1. 골드바흐의 추측 (백준 - 9020)

먼저 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

 

이를 구하려면 우선 문제에서 입력 값으로 주어진 4부터 10000 이하 사이의 소수들을 리스트에 넣어서 소수 리스트를 만들어 줍니다.

 

또한 이문제에서는 시간을 효율적으로 줄이기 위해 소수를 판별하는 방법에서 조건을 달리 줘야 합니다.

 

자연수의 약수에 존재하는 원리를 사용하면 좀 더 효과적으로 빠르게 작동할 수 있습니다. 예를 들어서 1과 자기 자신을 제외한 약수가 존재하는지 확인하려면, 자기 자신의 제곱근(루트)까지만 확인하면 된다는 뜻입니다.

 

그래서 아래의 사진과 같이 범위를 지정해 주면 됩니다.

 

소수를 빠르게 구해서 리스트에 넣었으니 이제 두 소수의 차이가 가장 작은 것을 찾는 방법을 찾아보면 , 두 소수의 합이 결국 입력값이 되는 것이기 때문에 입력값을 반으로 나눠서 중간지점부터 찾아가면 가장 작은 것을 찾는 방법과 동일합니다.

 

 

 

2. 하노이의 탑 (백준 - 1914)

하노이의 탑이란 시작 막대에서 목표 막대까지 둥근 원반을 옮기는 것입니다.

 

여기서는 조건이 몇 가지가 있는데,

- 우선 한 번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐입니다. 

- 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다.

 

이 하노이의 탑을 푸는 데에 있어서 가장 중요한 개념은 재귀함수입니다.

재귀(recursion)이란 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것이고, 이렇게 재귀적인 호출을 사용하는 함수를 재귀함수라고 합니다.

 

먼저 이동 횟수를 살펴보면 

 

N이 원판개수일 때 

N=1 -> 1

N=2 -> 3

N=3 -> 7

N=4 -> 15라는 것을 확인해 보면 이를 통해 N의 제곱 -1이라는 값을 추론해 낼 수 있다.

 

또한 가장 중요한 재귀함수의 부분을 확인해 보면 아래와 같이 

1. 처음 기둥(a)에서 n-1개의 원반을 서브 기둥(b)으로 옮긴다.

2. 처음 기둥(a)에서 1개의 원반을 목표 기둥(c)으로 옮긴다.

3. 서브 기둥(b)에서 n-1개의 원반을 목표 기둥(c)으로 옮긴다.

 

위의 세 가지 규칙으로 이루어져 있어서 해당 부분을 활용하면 N이 20 이하일 경우 모든 케이스의 원반 경로를 확인할 수 있다.

 

 

해당 문제들의 전체코드는 https://github.com/dbscks97/KraftonJG-BOJ/tree/main/%EB%B0%B1%EC%A4%80/Silver

여기서 확인하면 될 것 같습니다. 

 

오늘 여러 개의 알고리즘을 풀어봤는데 아직은 많이 부족한 상태라고 느껴졌다,, 정확한 해답이 한 번에 떠오르지 않아서 많은 알고리즘들을 풀어보면서 사고력을 기르는 훈련을 해야 할 것 같다.. 많이 풀다 보면 익숙해지고 생각하는 게 달라지겠지..?