계수 정렬 특정한 조건이 부합 될 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 갯수가 N, 데이터중 최댓값이 K일 때 최악의 경우에도 수행시간이 O(N+K)를 보장한다. 동작 예시 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다. 2. 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 3. 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다. 소스 코드 # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (..
Python
백준 2579 파이썬 문제 풀이 : 계단 오르기 문제 링크 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 입출력 예시 제출 코드 n = int(input()) s = [int(input()) for i in range(n)] d = [0] * (n) if len(s) < 2: print(sum(s)) else: d[0] = s[0] d[1] = s[0] + s[1] for i in range(2,n): d[i] = max(d[i-3]+s[i-1]+s[i], d[i-2]+s[i]) print(d[-1])
퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 병렬 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 가장 기본적인 정렬은 첫 번째 데이터를 기분 데이터로 설정한다. 동작 예시 1. 첫번째 원소를 피벗으로 설정한다. 2. 왼쪽에서 부터 피벗 값보다 큰 값, 오른쪽에서부터 피벗 값보다 작은 값을 선택한다. 3. 선택된 두개의 값들의 위치를 바꾸어준다. 4. 위 동작들을 반복한다. 5. 위치가 엇갈리는 경우 피벗 값과 작은 값의 위치를 바꾸어준다. 6. 피벗 값을 기준으로 좌우로 나누어 2개의 리스트로 분할하여 준다. 7. 왼쪽 오른쪽 리스트에 대해 1번부터..
백준 파이썬 문제 풀이 : 문제 링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 입출력 예시 제출 코드 n = int(input()) # 컴퓨터 수 v = int(input()) # 연결선 수 graph = [[] for i in range(n+1)] # 그래프 생성 visited = [0] * (n+1) # 방문 여부 for i in range(v): a, b = map(int, input().split()) graph[a] += [b] graph[b] += [a] # 양방향 연결 def dfs(v):..
정렬 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 가장 앞의 데이터와 바꾼다. 앞선 1번의 과정을 반복한다. 정렬되지 않은 데이터가 하나가 남은 경우 처리하지 않아도 완성이 된다. array = [7, 3, 5, 4, 2, 6, 1, 0] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j a..
