Python

이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동장 예시 이미 정렬된 10개의 데이터 중에서 값을 찾는 방법 시작점, 끝점과 중간점을 설정한다. - 중간 값이 2개일 경우 소수점 이하 제거 중간점을 기준으로 찾는 데이터가 우측에 있는지 좌측에 있는지 구분 만약 좌측에 있다면 시작점은 그대로 내버려두고 현재의 중간점을 끝점으로 수정 수정한 시작점과 끝점을 기준으로 중간점을 다시 설정 이후 중간점 위치의 값이 찾고자하는 데이터가 같아질 때까지 반복 시간복잡도 단계마다..

계수 정렬 특정한 조건이 부합 될 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 갯수가 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] # 모든 범위를 포함하는 리스트 선언 (..

백준 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):..