# GCD
# GCD : Greatest common divisor : 최대공약수
# 유클리드 호제법
# : a,b에 대해 a를 로 나눈 나머지를 r이라 하면
# a,b의 최대 공약수는 b와 r의 최대 공약수와 같다.
# a b
# 192 162
# 162 30
# 30 12
# 12 6 >> 최대 공약수 6
def gcd(a, b):
print("---" + str(a) + ", " + str(b))
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
Depth-first search : 깊이 우선탐색 - 스택(선입후출, 바구니, append, pop), 재귀함수로 구현 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있으면 << 방문기준 문제마다 임의. 작은걸로 임의 정함 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더이상 2번의 과정을 수행할수 없을 때까지 반복
그외 - Backtracking : 꼬리잡기 : 한노드의 처음부터 끝까지 탐색하는 과정, 비효율적 어려울때 쓰는 최후의 보루. - 트리 운행법 inorder : 좌측 가운데 우측 preorder : 가운데 좌측 우측 postorder : 좌측 우측 가운데
BFS
breadth-first search :너비 우선탐색 - 큐(선입선출, 터널, append, popleft - from collections import deque 라이브러리 임포트)로 구현 - 인접노드 방문, 주로 최단거리 문제 - 모든 노드 방문안해도 됨.
1. 탐색 시작 노드를 큐에 삽입하고 방문처리 2. 큐에서 노드를 꺼낸뒤 해당 노드의 인접노드 중에서 방문하지 않는 노드를 모두 큐에 샆입 방문처리 3. 더이상 2번과정 수행없을 때까지 반복
def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: #print("-- " + str(i)) #print(visited) if not visited[i]: dfs(graph, i, visited)
# N x M 얼음틀.
# 구멍뚫려 있는 부분 0, 칸마기 1
# 상, 하, 좌, 우 붙어있는경우 서로 붙어있는것으로 간주.
# 생성되는 아이스크림갯수는?
# 1<=N, M<-1000
print("입력하세요")
#5 4
#00110
#00011
#11111
#
00000
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
print(graph)
graph.pop()
print(graph)
def dfs_ice(x,y):
if x <= -1 or x >= n -1 or y <= -1 or y >= m-1:
return False
elif graph[x][y] == 0:
graph[x][y] = 1
dfs_ice(x-1, y)
dfs_ice(x, y-1)
dfs_ice(x+1,y)
dfs_ice(x,y+1)
return True
return False
result = 0
for i in range(n):
for j in range(m):
if dfs_ice(i, j):
result +=1
print(result)
# 미로탈출 최소 칸이 갯수
#
"""
5 6
101010
111111
000001
111111
111111
10
"""
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
print(graph)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1,1]
def bfs_miro(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
elif graph[nx][ny]==0:
continue
elif graph[nx][ny] ==1:
graph[nx][ny]= graph[x][y] +1
queue.append((nx, ny))
return graph[n-1][m-1]
print(bfs_miro(0,0))
Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
# Q. 음이 아닌 정수들로 이루어진 배열이 있다.
# 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다.
# 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
# -1+1+1+1+1 = 3
# +1-1+1+1+1 = 3
# +1+1-1+1+1 = 3
# +1+1+1-1+1 = 3
# +1+1+1+1-1 = 3
# 사용할 수 있는 숫자가 담긴 배열 numbers,
# 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히
# 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
# 3
# +1 #+1 2
# -1 0
# +1 #+1 2
# -1 0
# 2 4 8
input_array = [1, 1, 1, 1, 1]
target_number = 3
count_number = 0
def get_plus_minus_sum(index, input_array, result_number):
#print(index,"|",result_number)
if len(input_array) <= index:
if result_number == target_number:
global count_number
count_number += 1
return
get_plus_minus_sum(index + 1, input_array, result_number + input_array[index])
get_plus_minus_sum(index + 1, input_array, result_number - input_array[index])
get_plus_minus_sum(0, input_array, 0)
print(count_number)
#Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
# 예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다.
# 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
# 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
# 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
input="01110"
def find_count_to_turn_out_to_all_zero_or_all_one(input):
number_sum = 0
for num in input:
if num == "1":
number_sum += 1
#print(len(input)//2 , number_sum)
if len(input)//2 >= number_sum:
return number_sum
else:
return len(input) - number_sum
print(find_count_to_turn_out_to_all_zero_or_all_one(input))
# 005 정수입력시 그이하 소수 출력
number = 20
# 소수 : 약수가 1과 자기자신밖에 없는것.
# N이 N의 제곱근보다 크지 않은 어떤소수로도 나눠지지 않는다.
def find_prime_list_under_number(number):
prime_list = []
count = 0
for n in range(2, number + 1):
for i in prime_list:
count += 1
if n % i == 0 and i * i <= n:
break
else: # 브레이크가 한번도 실행안되었을때
prime_list.append(n)
print("최종:", count)
return prime_list
def find_prime_list_under_number1(number):
prime_list = []
count = 0
for n in range(2, number + 1):
for i in range(2, n):
count += 1
if n % i == 0:
break
else:
prime_list.append(n)
print("1:", count)
return prime_list
def find_prime_list_under_number2(number):
prime_list = []
count = 0
for n in range(2, number + 1):
for i in prime_list: # 2~ n-1 중에서 소수인 친구들만
count += 1
if n % i == 0:
break
else: # 브레이크가 한번도 실행안되었을때
prime_list.append(n)
print("2", count)
return prime_list
print(find_prime_list_under_number1(number))
print(find_prime_list_under_number2(number))
print("최종: ", find_prime_list_under_number(number))
# Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
# "abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!
import re
#input = "abadabac"
input = "abab"
def find_not_repeating_first_character(input):
ascii_a = ord("a")
ascii_z = ord("z")
occured_alphabet = [0] * (ascii_z - ascii_a + 1)
# print(ord("z")-ord("a")+1)
input_param = input.lower()
input_param = re.sub("[^a-z]", "", input_param)
for text in input_param:
occured_alphabet[ord(text)-ascii_a] += 1
#print("occured_alphabet: ",occured_alphabet)
for text in input_param:
if occured_alphabet[ord(text) - ascii_a] == 1:
return text
return "_"
print(find_not_repeating_first_character(input))
#Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
#단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
input = [0, 3, 5, 6, 1, 2, 4]
# 1이하는 더하고 크면 곱한다.
def find_max_plus_or_multiply(input):
result = input[0]
for idx in range(1,len(input)):
if input[idx] >= 1 :
result += input[idx]
else:
result *= input[idx]
return result
print(find_max_plus_or_multiply(input))
