파운데이션 3부작(트릴로지) 중 3번째 작품, 제2파운데이션을 읽었다. 황금가지 출판사가 출판한 파운데이션 시리즈는 총 7권인데 대부분의 사람들이 3권까지만 읽어도 솔직히 충분하다는 말에 일단 ‘제2파운데이션’까지 읽어보자고 마음먹게 되었다. 그런데 생각보다 술술 읽히고 너무나도 재미있어서 바쁜 시기가 조금 지나면 나머지도 구입해서 읽어볼 예정이다. 읽다보니 소설 내용과 apple tv+의 스토리가 완전 딴판이어서 세계관을 공유하는 아예 다른 작품을 읽는 느낌이 들었다. 소설은 셀버 하딘의 이야기가 초반부에서 끝나고 바로 세대 교체되지만, 드라마에서는 초능력과 예지력을 지닌 하딘이 주축이 되어서 이야기를 전개해 나가니까 (성별도 다름) 아예 다른 스토리로 이해해야 한다. 그래도 드라마에서 잘 다뤄지지 않았던 파운데이션의 배경 이야기를 들을 수 있다는 것만으로도 의미가 있었다. ...

백준 1904번 문제 바로가기 조합(combinations)을 이용한 풀이 (시간초과) # 입력 import sys import math n = int(sys.stdin.readline()) ans = 0 # 처리 for i in range(n//2 + 1): ans += math.comb((n-i), i) print(ans) # N=4 # 4C0 1111 # 3C1 0011, 1001, 1100 # 2C2 0000 dp 풀이 조합으로 풀었더니 시간초과 문제가 발생해서, dp 방식으로 풀어보기로 했다. (참 쉽지 않구만!) 하긴 0.75초의 시간제한이 걸려있는걸 보면 bruteforce는 아니겠구만! 생각이 들긴 하다. 그래서 생각한 것은 dp 방식으로 풀어보자! (길이가 n일 떄의 가짓수) = $ a_{n} $ 이라면, $ a_{n} = a_{n-1} + 2 * a_{n-2} $ 을 만족한다 (n-1에 1을 추가하는 경우) (n-2에 11또는 00을 추가하는 경우) ...

백준 2193번 문제 바로가기 재귀를 통한 풀이 (시간초과..) 재귀를 이용하여 풀어보려고 했건만, 시간초과로 실패했다. 시간제한 2초인데도 걸리다니 빡세구만… # 입력 import sys n = int(sys.stdin.readline()) count = 0 # 처리 def pinary(arr = [1]): if len(arr) == n: global count count += 1 return else: if arr[-1] == 1: pinary(arr + [0]) else: pinary(arr + [0]) pinary(arr + [1]) pinary() print(count) dp을 이용한 풀이 러닝타임을 줄이기 위해서 주어진 이친수의 규칙을 파악해보았다. (0으로 끝나는 길이가 n인 이친수의 갯수)를 $ a_{n} $ (1로 끝나는 길이가 n인 이친수의 갯수)를 $ b_{n} $ 이라고 두면 $ a_{n} = a_{n-1} + b_{n-1} $ $ b_{n} = a_{n-1} $ 의 식을 만족한다. $ a_{0} = 0, b_{0} = 1 $ 의 초항을 대입하여 점화식을 풀면 n길이의 이친수의 갯수를 쉽게 구할 수 있다. ...

파운데이션 1권을 읽고 나서 ‘바로 이거다!!’ 싶어서 곧바로 읽게 된 2권 ’파운데이션과 제국’ 역시 기대했던 것처럼 처음부터 끝까지 긴장감있게 이야기를 읽어낼 수 있었다. 너무나 재미있어서 하루만에 단숨에 다 읽어버렸다.ㅎㅎ 일단 시리즈 7권 중에서 앞의 3권만 구입했는데, 재미있으면 나머지 4권도 다 구입해버리는건 아닌지 ㅋㅋ (이럴 줄 알았으면 그냥 세트로 저렴하게 구입할 걸 그랬나??) ⚠️ 주의! 이 글은 ‘파운데이션과 제국’ 책의 내용에 대한 직접적인 언급을 담고 있습니다. ⚠️ 돌연변이 ‘뮬’의 등장과 제1파운데이션의 위기. 제국과는 다른 길을 걸을 것이라 예견했던 것과는 달리, 파운데이션의 권력층은 세습을 시작하고 지도부는 해리 셀던의 역사심리학을 맹신한 나머지 그들에게 닥칠 위험에 대한 경보조차 무시해버린다. 일명 ‘필승 신화’에 심취해있던 그들은 결국 ‘뮬’의 군대 앞에서 무릎을 꿇게 된다. ...

백준 15649번 문제 바로가기 permutations을 이용한 풀이 처음에는 보자마자 itertools에서 permutations을 불러와서 사용했다. 간편하고 빨라서 만족하면서 제출했는데 역시나 정답! 하지만 이 문제를 분석하면서 알고리즘 분류를 봤더니 백트래킹이라는 처음 보는 개념을 가리키고 있었다. 백트래킹에 대한 개념을 알아보고 그 풀이로 다시 풀어보기로 했다. # 입력 import sys from itertools import permutations n,m = map(int, sys.stdin.readline().split()) arr = [i+1 for i in range(n)] # 처리 for ans in permutations(arr, m): print(*list(ans)) 백트래킹(backtracking)이란? 백트래킹은 간단하게 말하자면 가지치기라고 말할 수 있다. DFS의 경우 모든 가지를 다 커버할 떄까지 탐색을 진행하지만, 백트래킹의 경우 특정 조건을 만족시키면 뒤로 돌아가서 다른 경우의 수를 찾아나간다. 이런 특징 때문에 Back+Tracking이라는 이름을 가지게 되었다. 백트래킹에 대한 추가 설명은 이 분이 정말 잘 설명해주셨으니 참고 바란다. (이거보다 더 잘 설명할 자신이 없다…) ...