알고리즘12 [python] 백준 1914번 - 하노이 탑 아주 유명한 하노이 탑 문제.. 시작 기둥에 쌓여있는 n개의 원판 모두를 특정 규칙에 따라서 목표 기둥으로 옮겨야 하는 문제이다. 규칙은 다음과 같다 1. 한 번에 한 개의 원판만 다른 탑으로 옮길 수 있다. 2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 원판의 개수 N이 주어지면 옮긴 횟수, 그리고 그 옮긴 과정들을 출력해야 한다. 원판을 옮기는 과정에는 어떤 규칙이 있을까? A를 시작 기둥, B를 임시 기동, C를 목표 기둥이라고 하자. 가장 먼저 n == 1인 경우에는 단순히 A에 있는 원판을 C로 옮기면 된다. 다음으로는 n == 2인 경우를 보자. 원판 두 개를 옮기려면 다음과 같은 과정을 거쳐야 한다. A -> B A -> C B -> C 일단 A에 있는 작은 원판을 임시.. 2024. 7. 13. [python] 백준 28278번 - 스택 2 스택을 구현하는 문제 시간 초과 떠서 pypy 3로 풀었다. ㅎimport sysN = int(sys.stdin.readline())stack = []def one(X): stack.append(X)def two(): if len(stack) > 0: a = stack[-1] del(stack[-1]) print(a) else: print(-1)def three(): print(len(stack))def four(): if len(stack) == 0: print(1) else: print(0)def five(): if len(stack) > 0: print(stack[-1]) .. 2024. 7. 12. [python] 백준 4779번 - 칸토어 집합 모든 선의 길이가 1이 될 때까지 선을 3등분 한 후, 가운데를 공백으로 바꾸는 문제.재귀로 분류되어 있는 문제이다. 가장 먼저 규칙을 찾아 보았다. 더보기N == 0일 때"-" N == 1 일 때"- -" N == 2일 때"- - - -" N == 3일 때"- - - - - - - -"칸토어 집합의 규칙에 따라서 선을 그리게 되면N번째 선은 N - 1번째 선을 2개 이어 놓았다는 것을 알 수 있다.그리고 두 선의 사이에는 3^(N-1)의 공백이 생기는 규칙이 있다.그래서 위의 규칙을 구현하는 코드를 다음과 같이 작성하였다.def fn(n): if n == 0: return '-' else: prev_line = fn(n - 1) .. 2024. 7. 9. [python] 백준 9625번 - BABBA 초기에는 A가 표시 되어있고, 버튼을 누를 때마다 A->B, B->BA로 바뀐다. 버튼을 K번 눌렀을 때, A와 B의 개수를 구하는 문제이다. 다음과 같이 무작정 경우의 수를 적다보니 규칙을 발견할 수 있었다. AB기본값101번 누름012번 누름113번 누름 124번 누름 235번 누름 356번 누름58A는 2번 누를 때 부터, B는 1번 누를 때 부터 피보나치 수열로 나타나는 것을 발견할 수 있었다. 그래서 n번째 피보나치 수를 구하는 함수를 재귀를 사용하여 푸는 것을 큰 틀로 잡았다. 첫 시도def fib(n): if n == 1 or n == 2: return 1 else: return fib(n - 1) + fib(n - 2) K = int(input()) if K == 1: A = 0 B = 1.. 2024. 7. 8. [python] 백준 14425번 - 문자열 집합 집합과 주어진 문자열들이 주어지면 총 몇 개가 집합에 포함되어 있는지 출력하는 문제. N, M = map(int, input().split())s = ["a"] * Nfor i in range(N): s[i] = input()check = ["a"] * Mfor j in range(M): check[j] = input()s_set = set(s)cnt = 0for k in range(M): if check[k] in s_set: cnt += 1print(cnt)s와 check이라는 리스트에 미리 N, M개만큼 문자열을 넣어두고, for문으로 새로 대입하는 식으로 문자열을 구성하였다. 2024. 7. 7. [python] 백준 1181번 - 단어 정렬 입력한 문자열들을 기준에 따라 정렬하는 문제. N = int(input())words = [0] * Nfor i in range(N): words[i] = input()words = list(set(words))words.sort(key = lambda x : (len(x), x))for j in range(len(words)): print(words[j])sort() 함수는 기본적으로 리스트의 요소들을 오름차순으로 정렬 해주는 기능이 있다.하지만 sort() 함수는 다양한 기준으로도 정렬 할 수 있다. list.sort(reverse = True)를 하면 리스트를 내림차순 정렬이 가능하다. (reverse = False가 디폴트이다.)또한 위의 코드처럼 key를 사용해 새로운 기준을 설정할.. 2024. 5. 5. 이전 1 2 다음
