Back/Algorithm
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 재귀함수 알고리즘 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[..
Python 이진탐색 알고리즘
Python 이진탐색 알고리즘 1~100 사이에서 숫자 하나를 맞춰야 한다면 알고리즘의 관점에선 가장 효율적인 방법은 범위의 절반인 50을 시도해보는 것이다. 대답이 UP이라면 1~49는 후보에서 없어지고, 대답이 DOWN이라면 51~100이 후보에서 없어지기 때문이다. 이러한 방법을 이진탐색이라 한다. finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(target, array): current_min = 0 current_max = len(array) -1 current_guess = current_min + curren..
백준 알고리즘 4344 파이썬
www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net n = int(input()) for _ in range(n): # for문으로 위에서 입력한 n의 범위만큼 반복 시킨다. nums = list(map(int, input().split())) # for문 안에 input을 만들어 입력한 input값을 list로 nums에 저장시킨다. avg = sum(nums[1:])/nums[0] # 평균값을 구한다. 윗줄에 만든 nums리스트의 1번쨰부터 더해간다. 0번째는 학생 수 cnt = 0 # 평균 이상의 학생을 구하기 위해 cnt란 변수를 ..
백준 알고리즘 4673 파이썬
def d(n): next = n # 계산 결과 저장 for value in list(str(n)): # 숫자를 문자열로 하나씩 분리 next += int(value) #문자열을 다시 숫자로 변환 return next excap = [] #생성자가 있는 수 리스트 for count in range(10001): excap.append(d(count)) #생성자가 있는 수 저장 excap.sort() #생성자가 2개 있는 경우가 있기 때문에 정렬하여 구분 for count in range(1,10000): # 계속 돌리고 excap에 해당되지 않는 것을 프린트 돌린다. if count in excap: continue else: print(count)