- 퀵정렬
퀵 정렬은 앞의 두 알고리즘과 다르게 기준 데이터(pivot)를 설정해야 합니다. 기준을 설정한 다음 그 데이터를 기준으로 큰수와 작은 수를 교환하여 리스트를 반으로 나누는 방식으로 동작합니다.
inputlist = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(inputlist):
if len(inputlist)<=1:
return inputlist
pivot = inputlist[0]
newlist = inputlist[1:]
left = [x for x in newlist if x<=pivot]
right = [x for x in newlist if x>pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
- 삽입정렬
삽입 정렬은 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입하는 알고리즘입니다. 이 방법은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 매우 효과적입니다.
inputlist = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(inputlist)):
for j in range(i, 0, -1):
if inputlist[j] < inputlist[j]:
inputlist[j], inputlist[j-1] = inputlist[j-1], inputlist[j]
else:
break- 그 외의 정렬들도 외워두기!
▶ 스택 두 개 주고 큐만들기
Stack 1에 먼저 데이터를 A,B,C 순서대로 넣으면 C,B,A 같이 데이터는 쌓인다. 출력할때는 아래 Stack 2에 데이터를 옮겨서 출력해야 한다. Stack 1의 데이터를 순서대로 출력하면,
C,B,A 순으로 출력되며 순서대로 다시 Stack 2에 저장하면 아래와 같이 저장된다.
그럼 이제 Stack2 데이터를 출력하면 A,B,C 순서대로 출력이 가능하며 즉, Queue와 동일하게 FIFO(First in First out)이 가능해진다.
class Stack:
def __init__(self):
self.stack = []
def __repr__(self):
return f"{self.stack}"
def push(self, item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
def is_empty(self):
if len(self.stack)==0:return True
else: return False
class Queue:
def __init__(self):
self.qu=Stack()
self.stack2=Stack()
def __repr__(self):
return f"{self.qu}"
def push(self, item):
self.qu.push(item)
self.que=self.qu
def pop(self):
while not self.qu.is_empty():
self.stack2.push(self.qu.pop())
result=self.stack2.pop()
while not self.stack2.is_empty():
self.qu.push(self.stack2.pop())
return result
'''
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self, x):
self.input.append(x)
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
# output이 없으면 모두 재입력
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]
def empty(self):
return self.input == [] and self.output == []
'''
st=Stack()
st.push(1)
st.push(2)
st.push(3)
print(st) ## [1, 2, 3]
st.pop()
print(st) ## [1, 2]
qu=Queue()
qu.push(1)
qu.push(2)
qu.push(3)
print(qu)
qu.pop()
print(qu)
▶ 소수문제
어떤 수 n이 소수인지 아닌지 판별하기
import math
def is_prime(n):
for i in range(2, int(math.sqrt(n))+1):
if n%i==0:
return False ## 소수 아님
return True에라토스테네스의 채 : 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘, n보다 작거나 같은 모든 소수를 찾을 때 사용
import math
n=1000
arr=[True for i in range(n+1)]
for i in range(2, int(math.sqrt(n))+1): # 2부터 n제곱근까지의 수 모두 검사
if arr[i]==True: # i가 소수 일때
# i를 제외한 모든 배수 삭제
j=2
while i*j <= n:
arr[i*j] = False
j+=1
# 모든 소수 출력
for i in range(2,n+1):
if arr[i]:
print(i,end=' ')
▶ 길찾기 문제
최단경로 알고리즘인가...
- 다익스트라, 플로이드 워셜,벨만포드 : https://ga02-ailab.tistory.com/7
▶ 숫자중에 0이나, 7의 개수
??
▶ 팩토리얼 수중에 0인것
백준 1676번 문제 : https://www.acmicpc.net/problem/1676
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
n=int(input())
cnt=0
while n>=5:
cnt+=n//5
n//=5
print(cnt)팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하면 모든 값들의 소인수 분해 결과들은 2의 개수가 5의 개수보다 많아집니다. 다시 말해, 기본적으로 5의 개수에 따라 0의 개수가 변한다고 보면 됩니다.(실제 팩토리얼값, 소인수 분해 결과, 0의 개수 사이의 규칙을 보면 5의 배수마다 0의 개수가 증가하는 것을 알 수 있습니다. 여기서 확인할 수 있습니다!)
따라서 반복문을 통해 5로 나누면서 누적합을 해주어야 합니다.
▶ 피보나치
다이나믹 프로그래밍 이용해서 푸는 것
d = [0] * 100
d[1] = 1
d[2] = 1
n=99
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
▶ 완전탐색 기초적인것(DFS, BFS)
- 깊이 우선 탐색
def dfs(graph, v, visited):
visited[v] = True
print(v)
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
visited = [False] * 9
dfs(graph, 1, visited)- 너비 우선 탐색
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v)
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
visited = [False] * 9
bfs(graph, 1, visited)
▶ 달팽이문제
백준 2869번 문제 : https://www.acmicpc.net/problem/2869
import sys,math
a,b,v=map(int, sys.stdin.readline().split())
print(math.ceil((v-a)/(a-b))+1)
백준 1913번 문제 : https://www.acmicpc.net/problem/1913 ( 달팽이 모양으로 행렬 채우기)
n=int(input())
num=int(input())
mat = [[0]*n for _ in range(n)]
now, start, end = n*n, 0, n-1
while True:
if start-end == 0:
mat[start][end]=1
break
for i in range(start, end):
mat[i][start]=now
now-=1
for i in range(start, end):
mat[end][i]=now
now-=1
for i in range(end,start,-1):
mat[i][end]=now
now-=1
for i in range(end,start,-1):
mat[start][i]=now
now-=1
end, start = end-1, start+1
for i in range(n):
print(' '.join(str(ii) for ii in mat[i]))
for j in range(n):
if mat[i][j]==num: x,y=i,j
print(x+1,y+1)
▶ 배열돌리기
- 2차원 배열 90도 회전
def rotated(a):
n = len(a)
m = len(a[0])
result = [[0]* n for _ in range(m)]
for i in range(n):
for j in range(m):
result[j][n-i-1] = a[i][j] # 회전 전의 열 번호와 회전 후의 행 번호가 일치한다.
#그리고 회전 후의 열은 N-1 에서 회전 전의 행을 뺀 값과 같다.
return result
백준 16926번 배열돌리기 1 : https://www.acmicpc.net/problem/16926
반시계 방향으로 배열 돌리기
import sys
n, m, r = map(int, sys.stdin.readline().split())
matrix = []
for i in range(n):
matrix.append(list(map(int, sys.stdin.readline().split())))
for _ in range(r):
for i in range(min(n,m)//2):
x, y = i, i
svalue = matrix[x][y]
for j in range(i+1, n-i): ## 좌
x=j
pvalue = matrix[x][y]
matrix[x][y]=svalue
svalue=pvalue
for j in range(i+1, m-i): ## 하
y=j
pvalue=matrix[x][y]
matrix[x][y]=svalue
svalue=pvalue
for j in range(i+1, n-i): ## 우
x=n-j-1
pvalue=matrix[x][y]
matrix[x][y]=svalue
svalue=pvalue
for j in range(i+1, m-i): ## 상
y=m-j-1
pvalue=matrix[x][y]
matrix[x][y]=svalue
svalue=pvalue
for i in range(n):
print(' '.join(str(ii) for ii in matrix[i]))
▶ 해쉬맵으로 카운트해서 정렬하기
파이썬 dict를 key, value로 정렬하기
- key로 정렬 (오름차순)
my_dict = {'c': 3, 'a': 1, 'b': 2, 'e': 1, 'd': 2}
sorted_dict = sorted(my_dict.items(), key = lambda item: item[0], reverse = False)
print(sorted_dict) # [('a', 1), ('b', 2), ('c', 3), ('d', 2), ('e', 1)]
- value로 정렬 (내림차순)
my_dict = {'c': 3, 'a': 1, 'b': 2, 'e': 1, 'd': 2}
sorted_dict = sorted(my_dict.items(), key = lambda item: item[1], reverse = True)
print(sorted_dict) # [('c', 3), ('b', 2), ('d', 2), ('a', 1), ('e', 1)]
▶ 이진탐색트리
▶ 타켓 숫자를 주고 배열 중 두 수로 타켓숫자 만들기
??
'My Study > Interview' 카테고리의 다른 글
| ML직군 면접 질문 모음 (컴퓨터비전 관련 질문) (0) | 2023.03.09 |
|---|