전체 글
Python 백준 1874 스택수열 알고리즘
Python 백준 1874 스택수열 알고리즘 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net n = int(input()) # 처음 입력하는 n값 # 이 수에 따라 총 몇개의 원소를 가진 수열인지 정해짐 s = [] # 수열을 판단할 임시 리스트 op = [] # 나중에 출력할 +, - 리스트 count = 1 temp = True for i in range(n): num = ..
Python 백준 4949 균형잡힌세상 / 스택 알고리즘
Python 백준 4949 균형잡힌세상 / 스택 알고리즘 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net while True: bracket = input() if bracket == ".": break bracket_stack = [] answer = True for j in bracket: if j == "(" or j =="[": bracket_stack.append(j) elif j == ")": if len(bracket..
Python 병합정렬 알고리즘
Python 병합정렬 알고리즘 테스트를 보는 곳이나 면접에서도 직접 구현해보라고 하는 구현방법들이다. 병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘. 예를 들어서 A - 1, 2, 3, 5 B - 4, 6, 7, 8 이 두 집합을 합쳐가면서 정렬하는 방법 병합 # 병합 array_a = [1, 2, 3, 5] array_b = [4, 6, 7, 8] def merge(array1, array2): result = [] array1_index = 0 array2_index = 0 while array1_index < len(array1) and array2_index < len(array2): # index값이 커질 때 즉 한 바퀴 다 돌 때 탈..
Python 백준 2805 나무자르기 / 이진탐색 알고리즘
Python 백준 2805 나무자르기 / 이진탐색 알고리즘 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net N, M = map(int, input().split()) tree = list(map(int, input().split())) start, end = 1, max(tree) # 이분탐색 검색 범위 설정 # 1을 시작, end를 나무 중 긴 길이 # 원하는 나무 높이 while start = mid:..
Python 백준 11651 좌표정렬하기2 / 파이썬 알고리즘
Python 백준 11651 좌표정렬하기2 / 파이썬 알고리즘 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) array = [] for i in range(n): [x, y] = map(int, input().split()) array.append([y, x]) s_array = sorte..
Python 재귀함수 알고리즘 - 백준 11729 하노이탑
Python 재귀함수 알고리즘 - 백준 11729 하노이탑 www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net def move(n, start, end): if n == 1: print(start, end) return move(n - 1, start, 6 - start - end) # 시작부분에서 저장하는 곳으로 다 옮긴 것 print(start, end) # 시작부분에서 끝부분으로 이동 move(n - 1, 6 - start - end, end)..
Python 이분탐색 알고리즘 활용
Python 이분탐색 알고리즘 활용 shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"] shop_orders = ["오뎅", "콜라", "만두"] def is_available_to_order(menus, orders): shop_menus.sort() # 정렬 for order in orders : # order를 orders에서 하나하나 뽑아서 밑에있는 이분탐색 함수를 돌려보면 될 것 if not is_existing_target_number_binary(order, shop_menus): # 하나라도 존재하지 않는다면 return False return True ## 이분탐색의 코드 def is_existing_target_number_binary(target, arr..
Python 재귀함수 알고리즘 Factorial, 회문 검사
Factorial # Factorial(N) = N*Factorial(N-1) # ... # Factorial(1) = 1 def factorial(n): if n == 1: return 1 return n * factorial(n-1) print(factorial(5)) factorial 예시. 함수에 5를 넣었을때 5x4x3x2x1 이렇게 작동되어 결과값 120이 나온다. 여기서 주의할 점은 탈출 조건을 만들어야 한다. 이 경우는 if를 활용하여 n이 1과 같아질 때 1을 돌려주어 함수가 끝난다. 만약 그렇지 않을 경우엔 계속해서 n * factorial(n-1)이 작동되어 곱셈을 더해간다. 회문 검사 input = "소주만병만주소" def is_palindrome(string): if string[..