반응형 알고리즘 테스트58 정렬 알고리즘 2 : 병합 정렬(합병 정렬, Merge sort) 두 번째로 알아볼 정렬 알고리즘은 바로 병합 정렬이다! 먼저 동작 방식을 간단하게 살펴보자 폰 노이만이 개발한 알고리즘으로 데이터 크기만 한 메모리가 더 필요하다는 점이 단점이다. 장점은 데이터의 상태에 영향을 받지 않는다는 점이 있다. 즉, 항상 O(n log(n))의 시간 복잡도를 갖는다. n-way 합병 정렬이라고 부르지만 나는 흔히 사용하는 2-way 합병 정렬을 알아보도록 하겠다. 리스트의 길이가 1이면 이미 정렬된 것으로 본다. (1개밖에 없으므로) 정렬되지 않은 리스트를 절반으로 잘라 두 개의 부분 리스트로 나눈다. 부분 리스트에 1, 2번 과정을 반복한다.(재귀 이용) 잘게 쪼개진 부분리스트 들을 임시 리스트에 합병해가면서 정렬한다. 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정을.. 2022. 1. 30. 정렬 알고리즘 1 : 버블 정렬 정렬 알고리즘을 정리하는 시간을 갖고자 한다. 첫 번째로 정리할 정렬 알고리즘은 바로 버블 정렬이다. 가장 기초적인 알고리즘으로 원소의 이동이 거품이 수면으로 떠오르는 모습이랑 비슷하여 지어진 이름이다. 버블 정렬을 실행하면 이러한 모습으로 정렬이 되게 된다. 실질적으론 사용하지 않는 알고리즘이다. 왜 사용하지 않는지는 아래 동작 예시를 보면 알게 된다! 방법 n개의 배열이 들어왔을 때 1번째와 2번째 원소를 비교하고, 2번째와 3번째,... , n-1번째와 n번째까지 정렬한다. 이를 n번 반복하면 된다. 이미 정렬되어있는 배열이 입력된다면 O(n)의 시간이 걸리겠지만 그게 아니라면 최대 O(n^2)의 시간이 걸린다. 예시 5 4 3 8 9 10 2 이러한 배열을 정렬한다면 첫 번째 사이클 (4 5) 3.. 2022. 1. 30. 백준 10989 : 수 정렬하기3(카운팅정렬) 수 정렬하기 3https://www.acmicpc.net/problem/10989 코드# https://teching.tistory.com/import sys# 계수정렬countingNum = [0] * 10001for _ in range(int(sys.stdin.readline().rstrip())): countingNum[int(sys.stdin.readline().rstrip())] += 1for i in range(10001): for _ in range(countingNum[i]): print(i)해설메모리 제한이 8MB로 빡빡한 문제이다. 계수 정렬을 구현해서 풀었다. 계수 정렬에 관한 내용은 https://teching.tistory.com/80에서 정리를 해두었다! .. 2022. 1. 30. 백준 2751 : 수 정렬하기2 (파이썬) 수 정렬하기 2https://www.acmicpc.net/problem/2751 코드# https://teching.tistory.com/import sys# 합병정렬def mergeSort(nums): size = len(nums) if size == 1: return nums mid = size // 2 left = mergeSort(nums[:mid]) right = mergeSort(nums[mid:]) new = [0] * size end = l = r = 0 while len(left) > l and len(right) > r: if left[l] > right[r]: new[end] = right[r] .. 2022. 1. 29. 백준 1018 : 체스판 다시 칠하기 (파이썬) 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 코드import sysN, M = map(int,sys.stdin.readline().split())board = [[m for m in sys.stdin.readline().rstrip()] for _ in range(N)]case1 = [[0 for _ in range(M)] for _ in range(N)]case2 = [[0 for _ in range(M)] for _ in range(N)]for n in range(N): for m in range(M): if (n+m)%2 == 0: if board[n][m] == 'W': case2[n][m] = 1 .. 2022. 1. 29. 백준 7568 : 덩치 (파이썬) 덩치문제 https://www.acmicpc.net/problem/7568 코드import syspeoples = []for _ in range(int(sys.stdin.readline())) : peoples.append(list(map(int,sys.stdin.readline().split())))for i in peoples: k = 0 for j in peoples: if i[0] 해설처음에는 등수를 계산하는걸 어렵게 생각해서 여러번 틀렸다.몇 번 틀리고 단순하게 자기보다 덩치가 큰사람이 몇 명 있는지 확인해주면 끝나는 간단한 문제라는 걸 깨닫고 바로 새롭게 코드를 구현해서 제출하니 정답... 너무 어렵게 생각하지말고 단순하게 문제를 풀자!!! 2022. 1. 28. 백준 11729 : 하노이 탑 이동 순서 (파이썬) 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 코드def hanoi(n): if n == 1: return ["1 3"] #짝수일때는 오른쪽으로 한칸씩 if n % 2 == 0: tmp = ["1 2", "2 3", "3 1"] #홀수일때는 왼쪽으로 한칸씩 else: tmp = ["1 3", "3 2", "2 1"] pre = hanoi(n - 1) new = [] for i in range(len(pre)): new.append(tmp[i % 3]) new.append(pre[i]) else: new.append(tmp[len(pre) % 3]) .. 2022. 1. 27. 백준 2447 : 별 찍기 - 10 (파이썬) 별 찍기 - 10https://www.acmicpc.net/problem/2447 코드 def star(n) : if n == 3 : return ["***", "* *", "***"] stamp = star(n//3) return [s*3 for s in stamp]+[s+' '*(n//3)+s for s in stamp]+[s*3 for s in stamp]print('\n'.join(star(int(input()))))해설*** 상* * 중*** 하먼저 패턴을 3부분으로 나누어 보자상, 중, 하으로 나누어서 생각하면 조금 편해진다.이게 무슨 소리냐면예로 n=9 이라면 구조가 아래 그림처럼 나온다.즉 star(9)의 배열은 총 9개의 배열을 가지게 되고각각 한줄씩 저장해 주.. 2022. 1. 26. 백준 1002 : 터렛 (파이썬) 터렛https://www.acmicpc.net/problem/1002 코드import sysfor _ in range(int(sys.stdin.readline().rstrip())) : x1,y1,r1, x2,y2,r2 = map(int,sys.stdin.readline().split()) d = (abs(x1-x2)**2 + abs(y1-y2)**2)**.5 #동심원 if d == 0 : #두 반지름이 같을 때 (교점은 무한대) if r1==r2 : print(-1) #두 반지름이 다를 떄 (만나지 않음) else : print(0) #동심원이 아닐 때 else : sum = r1+r2 d.. 2022. 1. 26. 이전 1 2 3 4 5 6 7 다음 반응형
