반응형
1. 파이썬 문법 부수기
#리스트 컴프리헨션 (아래와 같은 값)
array = [i for i in range(20) if i % 2 == 1] #0~19 홀수 담은 리스트
print(array)
#리스트 일반적 코딩
array = []
for i in range(20):
if i % 2 ==1:
array.append(i)
print(array)
#NxM행렬 초기화
n=4
m=3
array = [[0]*m for _ in range(n)] #반복 수행에서, 변수값 무시할 때 언더바(_)사용
print(array)
#sort()
#변수.sort() 오름차순정렬
#변수.sort(reverse=True) 내림차순정렬(True에서 'T'는 대문자)
#변수.reverse() 변수앞뒤로 뒤집기
#집합자료형
a = [1, 1, 3, 4, 2, 5, 6]
remove_set = {3, 5}
result = [i for i in a if i not in remove_set] #remove_set에 포함 '안'된 것들만 a=[]에서 빼온다
print(result)#input()보다 빠르게 입력 받기
import sys
data = sys.stdin.readline() #rstip()는 '\n'제거역할
print(data)
#F-String
answer = "파이썬"
print(f'정답은 {answer}입니다.') #중괄호{} 안에 변수명을 기입하여, 문자열과 정수를 함께 출력 가능
#논리연산자
#X and Y #X,Y가 모두 참일 때 True
#X or Y #X,Y가 하나만 참이어도 True
#not X #X가 거짓일 때 True
#X in List[] #리스트 안에 X가 있을 때 True
#X not in 문자열 #문자열 안에 X가 없을 때 True
#반복문 안에서의 continue
result = 0
for i in range(1,10):
if i % 2 == 0: #짝수이면, result += i를 건너뛴다. 즉, '홀수합'을 구하라.
continue #반복문에서 continue 뒤의 코드 실행을 skip하고, 다음 반복을 새롭게 진행
result += i
print(result)#내장함수
print(eval('(3+5)*7')) #eval() : 수식으로 표현된 결과를 '숫자'로 반환해주는 함수
print(sorted([9, 1, 4, 3, 5, 7], reverse=True)) #sorted() : list와 같은 반복 가능한 개체가 들어왔을 때, 각 원소의 정렬값을 반환
from itertools import permutations #순열
data = ['a', 'b', 'c']
print(list(permutations(data, 2))) #3개중 2개를 뽑은 순열 구하기 = 6가지
from itertools import combinations #조합
print(list(combinations(data, 2))) #data에서 2개를 뽑는 조합의 수 = 3가지
from itertools import product
print(list(product(data, repeat=2))) #중복 허용한 순열 = 9가지
from itertools import combinations_with_replacement
print(list(combinations_with_replacement(data, 2))) #중복 허용한 조합 = 6
from collections import Counter
counter = Counter(['red', 'blue', 'green', 'red', 'blue', 'blue'])
print(counter['blue']) #blue가 등장한 횟수 출력 = 3
print(dict(counter)) #사전자료형으로 변환
2. 그리디&구현
''' 그리디1 : 거스름돈
1) 최적의 해를 구하기 위해 '가장 큰 화폐 단위부터' 돈을 거슬러 준다.
2) 500원, 100원, 50원, 10원 순으로
3) N=1,260 일 때를 예시로 확인
'''
n = 1260
count = 0
array = [500, 100, 50, 10]
for coin in array:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 갯수
n %= coin #거슬러주고 남은 돈
print(count) #500x2, 100x2, 50x1, 10x1
''' 그리디2 : 1이 될때까지(★)
1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.
이 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하기
예를 들어, n=17, k=4일 때, 1.를 1번 수행, 2.를 2번 수행하면
n=1에 도달하며, 시행 횟수는 3회
'''
n, k = map(int, input().split())
result = 0
while True:
target = (n // k) * k # 몫에 k을 곱한 이유? k로 나누어 떨어지는 가장 가까운 수를 찾고자 할 때
result += (n - target) # result는 연산 수행 횟수로, 1을 빼는 연산을 몇 번 수행할지 확인
n = target
if n<k:
break
result += 1
n //= k #k로 나누기, k로 나누는 연산을 1번 수행하므로 += 1 해줌
result += (n - 1) #n이 1보다 크다면, 1이 될 수 있도록 하기 위해 남은 수에서 1씩 빼기
print(result)
''' 그리디3 : 곱하기 혹은 더하기
왼쪽부터 오른쪽으로 x혹은 +연산을 해 만들어 질 수 있는 가장 큰 수를 구하기
단, x을 먼저 계산하는 방식과는 달리 왼쪽부터 순차적으로 이루어지도록
예를 들어, 02984는 (0+2)x9x8x4 = 576
'''
data = input() #02342
result = int(data[0]) #첫번째 문자를 숫자로 변경하여 대입
for i in range(1, len(data)):
num = int(data[i])
if num <= 1 or result <= 1: #두 수 중 하나라도 0 or 1인 경우 더하기 수행
result += num
else:
result *= num
print(result)
''' 그리디4 : 모험가길드
모험가 n명을 대상으로 공포도가 x인 모험가는 반드시 x명 이상으로 구성한
모험가 그룹에 참여해야 하며, 만들 수 있는 그룹의 최댓값을 구하시오
예를 들어, n=5이고, 각 모험가의 공포도가 2 3 1 2 2 라면, 1 2 3인 그룹1과
2 2 인 그룹2 총 2개의 그룹을 만들 수 있다
'''
n = int(input())
data = list(map(int, input().split()))
data.sort() #오름차순
result = 0 #총 그룹 수
count = 0 #현재 그룹에 포함된 모험가 수
for i in data: #공포도를 낮은 것부터 하나씩 확인
count += 1 #현재 그룹에 모험가를 일단 포함시키고
if count >= i: #현재 그룹의 모험가 수가 공포도 이상이면 그룹 결성
result += 1 #그룹 수 증가시키기
count = 0 #현재 그룹에 포함된 모험가 수 초기화
print(result)'''[Tip] 구현'''
#1. 2차원 공간 = 행렬
for i in range(5):
for j in range(5):
print('(', i,',',j ,')', end=" ")
print()
#2. 시뮬레이션, 완전 탐색 = 2차원 공간에서 '방향 벡터' 활용됨
#동, 북, 서, 남
dx = [0, -1, 0, 1] #x는 세로축(열)을 의미
dy = [1, 0, -1, 0] #y는 가로축(행)을 의미
#현재 위치
x, y = 2, 2
for i in range(4):
#다음 위치
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)
''' 구현1 : 상하좌우
가자 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (n,n)에 해당
여행가A는 상, 하, 좌, 우 방향으로 이동 가능하며, 시작 좌표는 항상 (1,1)
여행가A가 NxN크기의 정사각형 공간을 벗어나는 움직임은 무시하며
여행가가 최종적으로 도착할 지점의 좌표 (x,y)를 공백 기준으로 구분하여 출력
입력 예시 : 5 RRRUDD , 출력예시 3 4
'''
n = int(input())
x, y = 1, 1
plans = input().split()
dx = [0, 0, -1, 1] #L, R, U, D
dy = [-1, 1, 0, 0]
move = ['L','R','U','D']
#이동 계획을 하나씩 확인하기
for plan in plans:
#이동 후 좌표 구하기
for i in range(len(move)):
if plan == move[i]:
nx = x + dx[i]
ny = y + dy[i]
#공간을 벗어나는 경우 무시
if nx<1 or ny<1 or nx>n or ny>n:
continue
#이동 수행
x, y = nx, ny
print(x,y)
''' 구현2 : 시각
정수n이 입력되면 00시00분00초부터 n시59분59초까지의 모든 시각 중에서
3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 작성
예를 들어, 1을 입력하면 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각
00시00분03초, 00시13분30초
입력예시: 5, 출력예시: 11475
'''
h = int(input()) #하루는 24x60x60=86400초 이므로 1씩 증가시켜 3이 하나라도 포함되어있는지 확인
#시,분,초를 각각 for문을 돌린다.
count = 0
for i in range(h+1):
for j in range(60):
for k in range(60):
#매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if '3' in str(i) + str(j) + str(k) : #시분초를 문자열형태로 만들어서 더해버림
#print(str(i) + str(j) + str(k))
count +=1
print(count)
''' 구현3 : 왕실의 나이트
8x8좌표 평면으로, 나이트는 L자 형태로만 이동할 수 있으며 평면 밖으로 나갈 수 없다.
L자 이동(1. 수평2칸 이동 후 수직 1칸 이동 / 2. 수직2칸 이동 후 수평 1칸 이동)
행은1-8, 열은a-h로 표현하며, c2에 있을때 경우의 수는 6가지(입력:c2, 출력:2)
'''
#현재 나이트의 위치 입력받기
#나이트가 이동할 수 있는 8가지 방향 정의
#각 방향으로 이동 가능여부 확인
#현재 나이트 위치 입력받기 ex)a1, c2
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1 # ord(문자) <=> chr(정수) ex) ord('a')=97, chr(97)='a'
#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1),
(2,1), (1,2), (-1,2), (-2,1)]
#각 방향으로 이동 가능여부 확인
result = 0
for step in steps:
#이동하고자 하는 위치 확인
next_row = row + step[0] #step[0] = step[]배열 내 튜플()중 앞의 값
next_column = column + step[1] #step[1] = 뒤의 값
#해당 위치로 이동이 가능하다면 카운트 증가
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)
''' 구현4 : 문자열 재정렬
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어지며, 모든 알파벳을
오름차순으로 정렬하여 이어서 출력한 뒤 그 뒤에 모든 숫자를 더한 값을 이어서 출력
예를 들어, K1KA5CB7 입력 시, ABCKK13 출력
'''
#문자를 입력받고, 리스트 형태의 결과값에 이어붙인 후, 리스트를 문자열로 변환
#리스트->문자열 : ''.join(문자열)
data = input()
result = []
value = 0
#문자를 하나씩 확인하며
for x in data:
if x.isalpha(): #알파벳인 경우 결과 리스트에 삽입
result.append(x)
else:
value += int(x) #숫자는 따로 더하기
result.sort() #알파벳 오름차순 정렬
if value != 0: #숫자가 하나라도 존재하는 경우, 숫자->문자 변경 후 가장 뒤에 삽입
result.append(str(value))
print(''.join(result)) #리스트를 문자열로 변환하여 출력
3. DFS&BFS
#탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정
#DFS, BFS는 대표적인 그래프 탐색 알고리즘이며, 코테에서 항상 출제되는 유형
#스택(Stack) : 선입후출 자료구조, 입구와 출구가 동일한 형태, 삽입/삭제로 이루어짐
#리스트 자료형(stack=[])을 사용, append()와 pop() 메소드를 사용, 리스트[::-1] = 스택 순서 뒤집기
#큐(Queue) : 선입선출 자료구조, 입구와 출구가 뚫려있는 터널 형태, 대기열(차례차례)을 표현할 때 사용
#deque라이브러리 사용, append()와 popleft() 함수를 사용, 큐.reverse() = 역순으로 바꾸기
#재귀함수(Recursive Function) : 자기 자신을 '무한히' 호출하는 함수, DFS구현 시 자주 사용
#반복문 대신 사용 가능하며, 코드 초기에 종료 조건을 반드시 기재
#컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓이므로,
#스택(Stack) 사용 시, 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음
#재귀함수 예제1 : 팩토리얼(n!) 구현
#수학적으로 0! = 1! = 1
#1. 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
print('반복적으로 구현:', factorial_iterative(5))
#2. 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)
print('재귀적으로 구현:', factorial_recursive(5))
#재귀함수 예제2 : 최대공약수 계산(유클리드 호제법)
#유클리도 호제법 = 두 자연수의 최대공약수를 구하는 대표적 알고리즘
#두 자연수 a, b(a>b)에 대해 a를 b로 나눈 나머지를 r이라 할때,
#a와 b의 최대공약수는 b와 r의 최대공약수와 같다
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192, 162)) #ans:6
''' DFS
1.깊이 우선 탐색(Depth-First Search)으로 스택(or 재귀함수)를 이용
2.동작과정
1) 탐색 시작 노드를 스택에 삽입하고 방문 처리
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면
그 노드를 스택에 넣고 방문 처리하며, 방문하지 않은 인접 노드가 없으면
스택에서 최상단 노드를 꺼냄
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
'''
#그래프 표현 = 2차원 리스트 graph = [[], [], [], ... []]
#방문 처리 = 1차원 리스트, default는 False로 초기화(False = 방문하지 않았다.)
#그래프 문제 = node가 1번부터 시작하는 경우가 많으므로, index[0] 부분은 비워둠
def dfs(graph, v, visited): #dfs는 graph와 방문처리여부가 기록된 리스트를 이용
visited[v] = True #현재 노드 방문처리
print(v, end=" ")
#현재 노드(스택 최상단 노드)와 다른 노드를 하나씩 확인하면서 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2,3,8], # node1과 연결된 것은 2, 3, 8 임을 의미
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9 #node !~8까지 가지고 있으므로 index[0]은 사용 않도로 하기 위해 하나 더 큰 크기(8+1)로 1차원 리스트를 초기화할 수 있다
dfs(graph, 1, visited) #dfs 함수 호출
''' BFS
1.너비 우선 탐색(Breadth-Frist Search)으로 큐(Queue)를 이용, 가까운 노드부터 탐색
2.동작과정
1) 탐색 시작 노드를 큐에 삽입하고 방문 처리
2) 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를
모드 큐에 삽입하고 방문처리
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
'''
#queue사용을 위한 deque 라이브러리 호출
from collections import deque
def bfs(grpah, start, visited):
queue = deque([start]) #시작노드[start]를 queue에 넣어주기
visited[start] = True #시작노드를 방문처리
while queue: #queue가 빌 때까지 반복
v = queue.popleft() #queue에서 하나의 원소를 뽑아 출력
print(v, end=" ")
for i in graph[v]:
if not visited[i]: #아직 방문하지 않은 인접한 노드를 queue에 삽입
queue.append(i)
visited[i] = True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
bfs(graph, 1, visited)
''' DFS&BFS1 : 음료수 얼려 먹기 (DFS)
NxM 크기의 얼음 틀에서 구명이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시
얼음틀 모양이 주어졌을 때 생성되는 총 아이스크림 개수를 구하는 프로그램 작성
구명이 뚫려 있는 부분끼리 상하좌우로 붙어 있을 때, 서로 연결된 것으로 간주
예를 들어, (입력: 4 5, 출력 3)
00110
00011
11111
00000 의 경우 총 3개의 아이스크림이 생성
'''
def dfs(x,y):
#주어진 범위 벗어날 경우 즉시 종료
if x<=-1 or x>=n or y<=-1 or y>=m:
return False
#g현재 노드를 아직 방문하지 않았다면, 방문처리
if graph[x][y] == 0: # 0인 것은 1로 바꾸고, 인접한 것까지 1이면 True
graph[x][y] = 1
#상하좌우 위치들도 재귀적 호출
dfs(x-1,y)
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)
return True
return False
n, m = map(int, input().split())
graph = []
for i in range(n): #n줄에 걸쳐서 2차원 리스트의 맵 정보 입력 받기
graph.append(list(map(int, input())))
'''이때 입력은 공백 없이 0과 1로 구성된 문자열 형태로 주어지기 때문에,
한 줄로 입력 받은 후 각 원소를 정수형으로 바꿔서 다시 리스트형태로 만들어주면,
모든 원소가 0혹은 1인 정수리스트가 들어가진다. 아래 print(graph)를 해서 확인
'''
#print(graph)
#모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
#현재 위치에서 dfs 수행하여, 방문처리 됐다면 result카운트 수행
if dfs(i,j) == True:
'''dfs는 한 번 수행 되면, 해당 노드와 연결된 모든 노드들도 방문처리 할 수 있도록 하고,
시작노드가 방문처리 되었다면(=처음 방문하는 것이라면) 그때만 result값을 증가시키기로 한다'''
result += 1
print(result)
''' DFS&BFS2 : 미로 탈출 (BFS)
NxM의 미로에 시작위치는 (1,1)이며 출구는 (N,M)의 위치에 존재
한 번에 한 칸씩 이동할 수 있으며, 괴물이 있는 부분은 0, 없는 부분은 1로 표시
움직여야할 최소 칸의 개수는?
예를 들어, (입력 : 5 6, 출력 : 10)
101010
111111
000001
111111
111111
'''
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m: #공간 벗어나면 무시
continue
if graph[nx][ny] == 0: #벽인 경우 무시
continue
if graph[nx][ny] == 1: #해당 노드를 첫 방문하는 경우에만 최단거리 기록
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1] #가장 오른쪽 아래까지 최단거리 반환
#입력 및 2차원리스트 생성
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
#네 가지 방향 벡터 (상하좌우)
dx = [-1,1,0,0]
dy = [0,0,0,1]
print(bfs(0,0))
4. 정렬 알고리즘
#선택정렬(Selection Sort)
'''
처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 데이터와 교환
시간복잡도 : O(N^2)
'''
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i #the smallest index
#print(list(map(int, str(min_index)))) : [0] [1] [2] ...[9] *Debug
for j in range(i+1, len(array)):
if array[min_index] > array[j]: #현재 가장 작은 원소보다 더 작은 원소[j]가 있다면, 그 위치 index인 j값이 min_index가 된다
min_index = j
#print(min_index) : 1 3 3 3 5 7 *Debug
array[i], array[min_index] = array[min_index], array[i] #swap
print(array)
#삽입정렬(Insertion Sort)
'''
처리되지 않은 데이트를 하나씩 골라 적절한 위치에 삽입
선택정렬보다 구현이 어렵지만, 동작이 효율적
(현재 리스트의 데이터가 거의 정렬된 상태에서 매우 빠르게 동작함)
시간복잡도 : O(N^2), 최선의 경우 O(N)
'''
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
#print(i) : *Debug
for j in range(i, 0, -1): #index i부터 1까지 1씩 감소하며 반복, range()함수 내 세번째는 step을 의미
#print(i)
if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
#print(array) #: *Debug
else: #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
#퀵정렬(Quick Sort)
'''
임의의 Pivot(기준 데이터)를 설정 후 '분할&정복' 방식으로 동작 (재귀함수 이용)
일반적 상황에서 많이 사용되는 알고리즘 중 하나로, pivot기준 왼->오(큰값), 왼<-오(작은값) 실시
시간복잡도 : O(NlogN), 최악 : O(N^2)
'''
array = [5, 7, 9, 0 , 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료
return
pivot = start #첫 원소를 피벗으로 설정
left = start + 1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1 #피벗보다 큰 데이터를 찾을 때까지 반복
while right > start and array[right] >= array[pivot]:
right -= 1 #피벗보다 작은 데이터를 ~
if left > right: #엇갈렸따면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: #엇갈리지 않았따면 ~
array[left], array[right] = array[right], array[left]
#분할 이후 왼쪽과 오른쪽 각가에서 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)
''' 리스트 슬라이싱과 컴프리헨션을 이용한 간단한 방식'''
array = [5, 7, 9, 0 , 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:] #pivot을 제외한 리스트
left_side = [x for x in tail if x <= pivot] #분할된 왼쪽 부분
right_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분
return quick_sort(left_side) + [pivot] + quick_sort(right_side) #list(map(int, str(pivot))) = [pivot]
print(quick_sort(array))
#계수정렬(Counting Sort)
'''
데이터의 범위가 제한(작을때)적일 때 사용
동일한 값을 가지는 데이터가 여러개 등장할 때
(count의 index값 = array의 element값)
데이터수:N, 데이터 중 최대값:K 일때, 시간O(N+K)
'''
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array)+1) #모든 범위를 포함하는 리스트 선언(값은 0으로 초기화)
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스 값 증가
#ex) array[0]인 7을 count[]의 7의 인덱스(8번째)에 1값을 더해준다는 의미
for i in range(len(count)): #0~9, 길이:10
for j in range(count[i]):
print(i, end=" ") #리스트에 기록된 정렬 정보 확인
#정렬알고리즘 비교 및 기초 문제 풀이
''' 대부분의 언어에서 지원하는 '표준정렬 라이브러리'는 최악의 경우에도
O(NlogN)을 보장하도록 설계되어 있으므로, 문제에서 정렬 함수를 구현하라고 하지 않는다면
표준 정렬 라이브러리(pythond에선 randint)를 사용하는 것을 추천
'''
from random import randint
import time
array = []
for _ in range(10000):
array.append(randint(1,100)) # 0~100의 랜덤 정수 10,000개를 배열화
#print(array)
start_time = time.time()
#선택정렬 구현
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
array[i], array[min_index] = array[min_index], array[i]
#print(array)
end_time = time.time()
print("선택정렬성능측정:", end_time - start_time)
''''기본 정렬 라이브러리 사용 시'''
array = []
for _ in range(10000):
array.append(randint(1,100))
start_time = time.time()
array.sort() #기본(표준) 정렬 라이브러리
end_time = time.time()
print("기본정렬라이브러리측정:", end_time - start_time)
''' 정렬1 : 두 배열의 원소 교체
두 개의 배열a, b이 있으며, 둘 다 n개의 자연수로 구성된 배열
최대 k번의 바꿔치기 연산 수행 가능, a배열의 모든 원소 합이 최대가 되는 것이 목표
예를 들어, n=5, k=3이고 a=[1,2,5,4,3], b=[5,5,6,6,5]일때,
a의 1과 b의 6, a의 2와 b의 6, a의 3과 b의 5를 교환하는 연산 3번을 실시
a=[6,6,5,4,5], b=[3,5,1,2,5]이며 a원소의 합 = 26(최대)
'''
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(sum(a))
5. 이진 탐색
'''
순차탐색 : 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법
이진탐색 : 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색(시작,끝,중간점이용)
이진탐색의 시간복잡도 : logN
'''
#1. 재귀함수이용
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2 #중간값 설정
if array[mid] == target:
return mid
elif array[mid] > target:
#중간값보다 찾을 값이 작으면 왼쪽
return binary_search(array, target, start, mid-1)
else:
#중간값보다 찾을 값이 크면 오른쪽
return binary_search(array, target, mid+1, end)
#입력값을 'list'로 받기
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result+1)
#2. 반복문 이용
def binary_search(array, target, start, end):
while start <= end:
mid = (start+end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
#bisect : 활용하면 좋을 파이썬 이진탐색 라이브러리
'''
bisect_left(a,x) : 정렬 순서를 유지한 채 배열a에 x를 삽입할 가장 왼쪽 인덱스 반환
bisect_right(a,x) : ~ 유지한 채 배열a에 x를 삽입할 가장 오른쪽 인덱스 반환
'''
from bisect import bisect_left, bisect_right
a = [1,2,4,4,8]
x = 4
print(bisect_left(a,x)) #2
print(bisect_right(a,x)) #4
''' 값이 특정 벙위에 속하는 데이터 개수 구하기'''
from bisect import bisect_left,bisect_right
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
a = [1,2,3,3,3,3,4,4,8,9]
print(count_by_range(a,4,4)) #2
print(count_by_range(a,-1,3)) #6
#파라메트릭 서치(Parametric Search)
'''
이진탐색을 활용해야 할 문제가 출제되는 경우 파라메트릭 서치로 출제되는 경우가 많으며,
최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법
'''''' 이진탐색1 : 떡볶이 떡 만들기
절단기 높이 : H
높이가 19, 14, 10, 17인 떡과 절단기 높이가 15라면, 자른 뒤 떡의 높이는
15, 14, 10, 15가 될 것이며, 잘린 떡 길이는 4, 0, 0, 2입니다. 손님은 6을 가져갑니다
손님의 요청 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는
높이 최댓값은?
'''
#떡 갯수:n, 요청 떡길이:m
n, m = map(int, input().split(' ')) # 4 6
array = list(map(int, input().split())) # 19 15 10 17
#이진탐색을 위한 시작점, 끝점 설정
start = 0
end = max(array)
result = 0
while start <= end:
total = 0 #항상 값을 저장할 변수를 하나 만든다
mid = (start + end) // 2
for x in array: # x : 현재 떡 길이
if x > mid:
total += x - mid
if total < m: #떡 양이 부족한 경우 : 더 많이 자르기(=왼쪽 부분 탐색)
end = mid - 1
else: #떡 양이 충분한 경우 : 덜 자르기(=오른쪽 부분 탐색)
result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
print(result) # 15
''' 이진탐색2 : 정렬된 배열에서 특정 수의 개수 구하기
n개의 원소를 포함한 수열이 오름찬순으로 정렬되어 있는데, 이때 수열에서 x가 등장하는
횟수를 계산하기.
예를 들어, {1,1,2,2,2,2,3}에서 x=2라면, 2인 원소가 4개이므로 4를 출력
시간복잡도는 O(logN)이므로, 선형탐색은 시간 초과 판정을 받기 때문에, 알고리즘을
설계해서 풀어야 합니다.
'''
from bisect import bisect_left,bisect_right
#값이 [left_value, right_value]인 데이터 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
right_index = bisect_right(array, right_value)
left_index = bisect_left(array, left_value)
return right_index - left_index
n, x = map(int, input().split())
array = list(map(int, input().split()))
count = count_by_range(array, x, x) #[x,x]범위에 있는 데이터 개수 계산
if count == 0: #값이 x인 원소가 존재하지 않는다면
print(-1)
else:
print(count)
6. 다이나믹 프로그래밍
'''
DP는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이며,
이미 계산된 결과는 별도의 메머리 영역에 저장하여 다시 계산하지 않도록 합니다.
구현은 top-down과 bottom-up 방식이 있습니다.
DP는 동적계획법으로 불리지만, 자료구조 등에서 말하는 동적(프로그램이 실행되는 도중에
실행에 필요한 메모리를 할당하는 기법)의 의미와는 무관합니다.
DP는 다음 조건을 만족할 때 사용할 수 있습니다.
1) 최적부분구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.
2) 중복되는부분문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 합니다.
DP활용 예시) 피보나치수열 : 1,1,2,3,5,8,13,21,34,55,89,~ : an = an-1 + an-2
'''
#피보나치수열
'''
시간복잡도 = 1)세타표기법: 0(1.618~), 2)빅오표기법: O(2^n)
시간복잡도는 DP로 해결 가능 하며, O(N)으로 줄어들 수 있습니다.
'''
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4)) #3
#메모이제이션(Memoization) : DP의 Top-Down방식
'''
한 번 계산한 결과를 메모리 공간에 메모하는 기법 = 캐싱(Caching)
Top-Down방식으로, 큰문제 해결을 위해 작은문제를 활용한는 방법으로 재귀함수 활용
단, DP의 전형적 형태는 Bottom-Up방식이며, 결과 저장용 리스트는 DP테이블 이라 합니다.
'''
#한 번 계산된 결과를 메모이제이션 하기 위해 리스트 초기화
d = [0]*100
#fibo를 재귀함수로 구현(top-down방식)
def fibo(x):
#print('f('+ str(x) + ')', end=" ") #f(99) f(98) ... f(1) f(1) f(2) .. f(97)
if x==1 or x==2:
return 1
if d[x] != 0: #이미 계산한 적이 있다면, 그 값을 그대로 반환
return d[x]
d[x] = fibo(x-1) + fibo(x-2) #계산한 적이 없다면, 점화식에 따라 결과 반환
return d[x]
print(fibo(99))
#fibo를 반복문으로 구현(bottom-up방식)
d[1] = 1
d[2] = 1
n = 99
for io in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
''' DP vs 분할정복
DP와 분할정복(Quick Sort)는 모두 '최적 부분 구조'를 가질 때 사용할 수 있으며,
DP와 분할정복의 차이점은 '부분 문제의 중복'입니다.
DP는 부분 문제가 중복되지만, 분할정복은 동일한 부분 문제가 반복적으로 계산되지 않습니다.
'''''' DP1 : 개미전사
개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소 한 칸 이상
떨어진 식량창고를 약탈해야 합니다.
예를 들어, 식량창고가 {1,3,1,5}일 때 개미전사는 두번째,네번째를 선택했을 때 최대의
식량을 빼앗을 수 있습니다.
식량창고 n개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최대값은?
예시)입력 : 4, 1 3 1 5 출력 : 8
ai = i번째 식량창고까지의 최적의 해(얻을 수 있는 식량의 최댓값)
ki = i번째 식량창고에 있는 식량의 양
점화식 : ai = max(ai-1, ai-2+ki), (i-3)번째 이하는 생각할 필요X
'''
n = int(input())
array = list(map(int, input().split()))
d = [0]*100 #DP테이블 초기화
d[0] = array[0] #bottom-up방식
d[1] = max(array[0], array[1])
for i in range(2,n):
d[i] = max(d[i-1], d[i-2]+array[i])
print(d[n-1])
''' DP2 : 1로 만들기
정수x가 사용할 수 있는 연산 4가지를 활용하여 값을 1로 만들기, 연산 횟수 최솟값 출력
1) 5로 나누어 떨어지면, 5로 나누기
2) 3으로 나누어 떨어지면, 3으로 나누기
3) 2로 나누어 떨어지면, 2로 나누기
4) x에서 1을 빼기
예를 들어, 26 -> 25 -> 5 -> 1 이므로 연산의 최솟값은 3
ai = i를 1로 만들기 위한 최소 연산 횟수
ai = min(ai-1, ai/2, ai/3, ai/5) + 1
'''
x = int(input()) #26
d = [0]*30001
#4가지 경우 중 가장 적은 값을 골라서 1을 더한 값을 넣을 수 있도록 점화식을 설정
for i in range(2, x+1):
#(현재 수에서 1을 빼는 경우)의 값에 1을 더한 값 => dp테이블에 들어갈 수 있도록
d[i] = d[i-1] + 1
if i%2 == 0:
d[i] = min(d[i], d[i//2]+1)
if i%3 == 0:
d[i] = min(d[i], d[i//3]+1)
if i%5 == 0:
d[i] = min(d[i], d[i//5]+1)
print(d[x]) #3
''' DP3 : 효율적인 화폐 구성
n가지 종류의 화폐를 최소한으로 이용해 합이 m이 되도록 프로그램 작성
예를 들어, 2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해 3원 5개를 사용하는 것
입력: 2 15, 2 3 / 출력: 5
ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
k = 각 화폐 단위
ai-k를 만드는 방법이 존재하는 경우: ai = min(ai,ai-k+1)
ai-k를 만드는 방법이 존재 않은 경우 : ai=INF(무한)
'''
n, m = map(int, input().split()) #N개 화폐, 합이 M이 되도록 입력
array = [] #N개의 화페 단위 정보 입력 ex)5원,10원,50원 등
for i in range(n):
array.append(int(input()))
#DP테이블 초기화 : 0원부터 m원까지 각각의 금액에 대한
#최소한의 화폐 개수를 구하고자 하기 때문에, m+1 크기의 DP테이블 초기화
d = [10001]*(m+1)
d[0] = 0
for i in range(n): #i는 각각의 화폐 단위, j는 각각의 금액을 의미
#현재금액d[j]에서 현재 확인하고 있는 화폐단위의 금액array[i]을 뺀 금액을 만들 수 있다면
#즉, (i-k)원을 만드는 방법이 존재하는 경우
for j in range(array[i], m+1):
#print(j, d[j], array[i]) #Debug i, 10001, arrayp[i]
if d[j-array[i]] != 10001:
d[j] = min(d[j], d[j-array[i]]+1) ''''''#비교하여 더 작은값으로 갱신
if d[m] == 10001: #m원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m]) #d[m] = m원을 만드는 방법 수
''' DP4 : 금광
NxM 금광에 1x1크기 칸으로 나눠져있으며, 채굴자는 첫 번째 열의 어느 행에서든 출발가능
이후 m-1번에 걸쳐, 맨 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야
채굴자가 얻을 수 있는 금의 최대 크기는?
왼쪽위, 왼쪽아래, 왼쪽 총 3가지 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에
갱신하여 문제 해결
array[i][j] = i행 j열에 존재하는 금의 양
dp[i][j] = i행 j열까지의 최적의 해(얻을 수 있는 금의 최댓값)
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])
'''
for tc in range(int(input())): # test case입력 :2
n, m = map(int, input().split()) # 금광 정보 입력 :3 4, 4 4
array = list(map(int, input().split())) # 1 3 3 2 2 1 4 1 0 6 4 7
# 1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
dp = []
index = 0
for i in range(n):
#열의 크기(m)단위로 슬라이싱해서 dp=[]테이블에 담아주는 방식으로 전체 데이터를 2차원 데이터로 담아 표현가능
dp.append(array[index:index+m])
index += m
for j in range(1,m): #bottom-up 방식으로 dp진행, j(열)을 기준으로
for i in range(n):
#1.왼쪽 위에서 (다음 열로) 오는경우
if i==0: left_up=0 #index범위 벗어나는 경우
else: left_up = dp[i-1][j-1]
#2. 왼쪽 아래에서 오는 경우
if i==n-1: left_down=0
else: left_down = dp[i+1][j-1]
#3. 왼쪽에서 오는경우
left = dp[i][j-1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result=0
for i in range(n):
result = max(result, dp[i][m-1])
print(result) #19, 16
''' DP5 : 병사 배치하기
N명의 병사 무작위 나열, 병사 배치 시 전투력이 높은 병사가 앞쪽에 도록 내림차순 배치
병사에 대한 정보가 주어졌을때, 남아 있는 병사의 수가 최대가 되도록 하기 위해
열외시켜야 하는 병사의 수를 출력하는 프로그램 작성
기본 아이디어는 '가장 긴 증가하는 부분 수열(LIS)'로, 예를 들어,
array={4,2,5,8,4,11,15}일때, 가장 긴 증가하는 부분 수열은 {4,5,8,11,15}입니다.
D[i] = array[i]를 마지막 원소로 가지는 부분수열의 최대 길이라 했을 때,
모든 0<=j<i에 대해, D[i]=max(D[i], D[j]+1) if array[j]<array[i] 입니다.
{4 2 5 8 4 11 15}
i=0일때, 1 1 1 1 1 1 1 <-값1로 초기화
i=1일때, 1 '1' 1 1 1 1 1
i=2일때, 1 1 '2' 1 1 1 1
i=3일때, 1 1 2 '3' 1 1 1
i=4일때, 1 1 2 3 '2' 1 1 <- ???
i=5일때, 1 1 2 3 2 '4' 1
i=6일때, 1 1 2 3 2 4 '5'
'''
n = int(input()) #7
array = list(map(int, input().split())) # 4 2 5 8 4 11 15
#순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
#DP테이블 초기화
dp = [1]*n # 1 1 1 1 1 1 1
#가장 긴 증가하는 부분수열LIS 알고리즘 수행
for i in range(1,n):
for j in range(0,i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j]+1)
#열외해야 하는 병사의 최소 수 출력
print(n - max(dp))
7. 최단 경로 알고리즘
반응형
'PS > Python' 카테고리의 다른 글
| Python [AtoZ] Chapter 06. 정렬 (3) | 2024.11.08 |
|---|---|
| Python [AtoZ] Chapter 05. DFS/BFS (3) | 2024.09.19 |
| Python [AtoZ] Chapter 04. 구현 (1) | 2024.09.16 |
| Python [AtoZ] Chapter 03. 그리디 (1) | 2024.09.15 |
| Python [AtoZ] Chapter 01. 기본문법 및 복잡도 총정리 (4) | 2024.09.14 |
