오늘은 쪽지 시험이 있는 날이다.
쪽지 시험에 관한 주요한 내용들과 오늘 공부한 내용을 정리하겠다.
강한 결합 요소 ( 강연결성분 : Strongly Connected Component )
강한 결합 요소란?
그래프의 특정 부분 집합 내의 모든 정점 V 이 집합 내 다른 정점 U로 도달할 수 있으며 반대로 U도 V로 도달할 수 있는 집합
또한 기본적으로 싸이클이 발생하는 경우 무조건 SCC에 해당한다는 특징이 있음.
쪽지 시험 대비 팀원 코어 타임
서로 2주차 내 어떤 키워드가 중요할 지 생각해보고 서로 문제를 출제했다.
화이트보드에 문제를 풀어보며 토론했는데,
다익스트라에 대해 조금 이해가 부족하다고 생각되서 다시 자세히 정리해보자.
다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다.
인공위성, GPS 소프트웨어 등에서 가장 많이 사용된다.
다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
하지만 음의 간선은 포함할 수 없다.
다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '여러 개의 최단 거리를 모아 최종의 최단거리를 찾는 알고리즘' 이기 때문이다.
다익스트라의 구체적인 작동 과정은 다음과 같다.
1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 3~4번의 과정을 반복
위 과정을 전부 마친 후 1번으로부터 걸리는 모든 정점에 대한 비용은 다음과 같이 배열에 저장된다.
과정을 코드로 정리하면 다음과 같다.
import sys
import math
INF = float("inf") #양의 무한대
n = 6 #정점의 개수
graph_matrix = [[0,2,5,1,INF,INF],
[2,0,3,2,INF,INF],
[5,3,0,3,1,5],
[1,2,3,0,1,INF],
[INF,INF,1,1,0,2],
[INF,INF,5,INF,2,0]] #인접 최소 비용 행렬
visited = [False for _ in range(n)]
lowest_cost = [INF for _ in range(n)] #시작점에서의 index 정점까지 최소 가중치
def getSmallIndex(): #시작점에서 가장 가까운 정점을 인덱스로부터 찾아오는 함수
global n
min = INF
index = 0
for i in range(n):
if lowest_cost[i] < min and not v[i]:
min = lowest_cost[i]
index = i
return index
def dijkstra(start):
global n
for i in range(n):
lowest_cost[i] = graph_matrix[start][i]
visited[start] = True
for _ in range(n-2):
current = getSmallIndex()
visited[current] = True
for j in range(n):
if not visited[j]:
lowest_cost[j] = min(lowest_cost[current]+graph_matrix[current][j]
dijkstra(0)
for i in range(n)
print(lowest_cost[i]
다익스트라의 실행 과정은 쪽지 시험의 문제로 이해해보자.
처음노드를 다익스트라 함수에 집어넣은 후,
노드에서 갈 수 있는 최단 거리를 리스트에 저장,
그후 최소의 경로 값의 노드를 방문하고,
그 노드와 연결되어있는 노드들까지 포함한 경로에서의 최소거리를 리스트에 저장
그 후 다시 방문하지 않은 노드 중 최소의 경로 값인 노드를 방문하는 방식.
프로세스 vs 쓰레드
프로세스와 쓰레드의 차이점은 무엇인가?
이는 보통 시스템 자원, 독립 VS 공유 키워드로 설명할 수 있다.
프로세스란?
독립적으로 실행되는 프로그램의 인스턴스로, 자체적인 주소 공간, 메모리, 데이터 스택 및 다른 시스템 자원을 갖는다.
쓰레드란?
프로세스 내부의 실행 흐름 단위로, 프로세스의 자원과 주소 공간을 공유하며 실행된다.
자원 공유 측면에서는..
프로세스는 각 독립적인 메모리 공간과 시스템 자원을 가지므로,
프로세스 간 자원 공유는 IPC(Inter-Process Communication) 메커니즘을 통해 이루어 진다.
쓰레드는 같은 프로세스 내의 쓰레드끼리 코드, 데이터 및 시스템 지원을 공유한다.
BaekJun - #14888:연산자 꽁가넣기(DFS?)
문제 출처 : https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱
www.acmicpc.net
연산자를 끼워넣는다는데 왜 정글 키워드로 DFS라고 하신건지 모르겠다..
큰 뜻이 있는 걸까요 원장님..
키워드와 맞지 않는 문제였다면,
키워드를 보지 않고 푸는 연습이 확실히 필요할 것 같다.
문제를 이해하고 순열을 쓴다는 아이디어를 제공받아 permutations 함수를 사용했다.
문제 풀이를 위한 뇌 흐름 방향은 다음과 같았다.
1. 일단 수를 받자 (n개)
2. 연산자를 숫자별로 받자(n-1개)
3. 2에서 갯수별로 받은 연산자를 1열로 쭉 나열한 리스트를 permutations 돌려서 모든 경우의 연산자 조합 리스트를 생성
4. 연산자 별로 연산자에 맞게 연산을 해주는 로직을 넣기.
5. 결과 리스트에 0번째 인덱스에 최소값, 1번째 인덱스에 최대값을 갱신하는 방식으로 모든 경우의 연산자 조합을 수에 대입하여 for문으로 돌리기
6. 결과 출력
코드는 다음과 같다.
from collections import deque
from itertools import permutations
import sys
import heapq
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline().strip())
num_list = list(map(int,sys.stdin.readline().strip().split()))
plus,minus,mul,div = map(int,sys.stdin.readline().strip().split())
math_task_list = []
for i in range(plus):
math_task_list.append("+")
for i in range(minus):
math_task_list.append("-")
for i in range(mul):
math_task_list.append("*")
for i in range(div):
math_task_list.append("/")
math_task_list = list(set(permutations(math_task_list)))
# print(num_list)
# print(math_task_list)
INF = float('inf')
result = [INF,-1*(INF)]
for i in range(len(math_task_list)):
temp = num_list[0]
temp_list = math_task_list[i]
for j in range(n-1):
if temp_list[j] == '+':
temp += num_list[j+1]
elif temp_list[j] == '-':
temp -= num_list[j+1]
elif temp_list[j] == '*':
temp *= num_list[j+1]
elif temp_list[j] == '/':
if temp >= 0 :
temp //= num_list[j+1]
else:
temp = -1*((-1*(temp))//num_list[j+1])
result[0] = min(result[0],temp)
result[1] = max(result[1],temp)
for i in range(1,-1,-1):
print(result[i])결과는 성공 ~
이 문제는 백준 내에서는 브루트 포스, 백트래킹의 알고리즘이라고 적혀있다.
백트래킹을 쓰는 방법이 있다는 거면 내가 볼 때, 내 방식과 다른 더 효율적인 방식이 있나봄.
내가 쓴건 브루트 포스에 좀 가까운 것 같다.
+++연산자 끼워넣기 DFS + 백트래킹 풀이 코드
백트래킹과 DFS 알고리즘을 이용해서 모든 경우의 연산을 순열 돌리는 함수 없이 구현할 수 있다.
코드는 아래와 같다.
n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
Max = -1e10
Min = 1e10
def dfs(i, now):
global Max, Min, add, sub, mul, div
if i == n:
Max = max(Max, now)
Min = min(Min, now)
else:
if add > 0:
add -= 1
dfs(i+1, now + data[i])
add += 1
if sub > 0:
sub -= 1
dfs(i+1, now - data[i])
sub += 1
if mul > 0:
mul -= 1
dfs(i+1, now * data[i])
mul += 1
if div > 0:
div -= 1
dfs(i+1, int(now / data[i]))
div += 1
dfs(1, data[0])
print(Max)
print(Min)처음엔 이해가 잘 안됬지만, 플로우를 써나가면서 생각해보니 백트래킹을 하면서 모든 경우를 다 커버하는 코드이다.
신박하니 메모.
BaekJun - #2573 : 빙산 (DFS/BFS)
문제 출처 : https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
2차원 배열 공간에서 특정 환경에 맞춰 그래프 탐색으로 확인 + 계산을 해줘야 하는 전형적인 그래프 탐색 문제였다.
문제에서 어려운 점은
DFS를 하면서 인접 배열 0 의 개수만큼 해당 빙하 값을 -1씩 줄여야 하는데
탐색도중 빙하였던 배열이 녹아 0이되면 다른 빙하들이 탐색도중 해당 영역을 바다로 생각하게 된다.
하지만 문제 상황에서는 모두 동시에 녹기에 먼저 탐색한 부분이 바다가 되어도 그 영역을 바다로 인식하면 안된다.
따라서 DFS시 해당 좌표의 영역에 녹아야 될 값을 저장하는 watering 배열을 생성하여, 그 배열에 녹이는 task를 append하는 방식을 사용했다.
from collections import deque
from itertools import permutations
import sys
import heapq
sys.setrecursionlimit(10**6)
n,m = map(int,sys.stdin.readline().strip().split())
ice_world = []
for _ in range(n):
ice_world.append(list(map(int,sys.stdin.readline().strip().split())))
def ice_to_water(): #이번 년도에 막 바다가 된 것과 이미 바다여서 면을 카운트해주는 공간을 구분해주기 위해 0과 -1로 구분
for i in range(n):
for j in range(m):
if ice_world[i][j] == 0:
ice_world[i][j] = -1
visited = [[False for _ in range(m)]for _ in range(n)]
watering = []
def bfs(x,y):
global n
global m
queue = deque()
queue.append((x,y))
visited[x][y] = True
while queue:
count = 0
now_x,now_y = queue.popleft()
for i,j in (0,1),(1,0),(0,-1),(-1,0):
if n>now_x+i>=0 and m>now_y+j>=0:
if not visited[now_x+i][now_y+j] and ice_world[now_x+i][now_y+j] > 0:
queue.append((now_x+i,now_y+j))
visited[now_x+i][now_y+j] = True
elif ice_world[now_x+i][now_y+j] == 0:
count += 1
icing = max(0,ice_world[now_x][now_y]-count)
watering.append((now_x,now_y,icing))
result = 0
while True:
visited = [[False for _ in range(m)]for _ in range(n)]
count = 0
for i in range(n):
for j in range(m):
if ice_world[i][j] > 0 and not visited[i][j]:
count += 1
bfs(i,j)
if count > 1:
break
elif count == 0:
result = 0
break
for x,y,icing in watering:
ice_world[x][y] = icing
watering.clear()
result += 1
print(result)빙하를 녹이는 과정은 제일 마지막에 watering을 분해하는 for문에서 진행했다.
처음에 계속 시간 초과가 나서 오래 고민을 했는데,
watering을 매 해 단위인 while문 사이클마다 clear()를 하지 않아 발생한 것이었다.
BaekJun - #2617 : 구슬찾기 (플로이드 워셜 알고리즘)
출처 : https://www.acmicpc.net/problem/2617
2617번: 구슬 찾기
모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서
www.acmicpc.net
드디어 2주차 마지막 문제를 풀어냈다.
마지막 문제로 상 문제를 놔둔건 내 실수 였다,,
(이제 난이도 골고루 풀어야지)
마지막 문제는 플로이드 워셜 알고리즘을 적용해야 했던 문제였다.
플로이드 워셜은 어제 포스팅에서 말했듯이
n<100 일때 닿지 않는 a - b - c 간의 거리를 중간요소 b로 이어주는 솔루션을 제공하는 알고리즘이다.
그래서 플로이드 워셜을 마치 쓰라는 것처럼 n<99의 범위를 제공한 문제였다.
문제를 해결하기 위해서는 각 구슬별로 나보다 큰 요소가 과반수 이상인지, 나보다 작은 요소가 과반수 이상인지를 체크해야 했다.
근데 이 문제를 풀기위해 고민하다 든 생각은
이게 왜 플로이드 워셜 알고리즘을 써야되지?
무지성 풀이 방법을 좋아하므로, 내가 떠오르는 방식대로 일단 구현해봤다.
from collections import deque
from itertools import permutations
import sys
import heapq
sys.setrecursionlimit(10**6)
n , m = map(int,sys.stdin.readline().strip().split())
min_to_max = {}
max_to_min = {}
world = [0 for _ in range(n+1)]
back_world = [0 for _ in range(n+1)]
for _ in range(m):
marble1 , marble2 = map(int,sys.stdin.readline().strip().split())
if not marble1 in max_to_min:
max_to_min[marble1] = [marble2]
else :
max_to_min[marble1].append(marble2)
if not marble2 in min_to_max:
min_to_max[marble2] = [marble1]
else :
min_to_max[marble2].append(marble1)
world[marble2] += 1 ##bigger than me count
back_world[marble1] += 1 ##smaller than me count
def dfs1(now,smaller_than_me_mem):
if now in min_to_max:
for next_bigger in min_to_max[now]:
back_world[next_bigger] += smaller_than_me_mem
dfs1(next_bigger,back_world[next_bigger])
def dfs2(now,bigger_than_me_mem):
if now in max_to_min:
for next_smaller in max_to_min[now]:
world[next_smaller] += bigger_than_me_mem
dfs2(next_smaller,back_world[next_smaller])
for i in range(1,n+1):
if back_world[i] == 0 :
dfs1(i,back_world[i])
if world[i] == 0 :
dfs2(i,world[i])
count = 0
for i in range(1,n+1):
if back_world[i] >= (n+1)//2:
count += 1
if world[i] >= (n+1)//2:
count += 1
print(count)이틀 전부터 위상 정렬에 갈려온 나는 방향성 그래프(대소관계)에 바로 위상정렬 식 풀이법이 떠올랐다.
1. 그래서 작은 무게의 구슬이 큰 무게의 구슬을 가리키는 그래프와,
큰 무게의 구슬이 작은 구슬을 가리키는 그래프.
총 2개를 저장하고
2. 각 구슬을 인덱스로 할당하여 리스트에 진입차선과 진출차선을 저장한 뒤
3. 진입차선이 0인 노드부터 쭉 dfs로 올라가면서 지나온 노드들을 하나씩 더해서 위상이 높은 구슬에게 갯수를 더해주고
4. 진출차선이 0인(가장 무거운 구슬) 노드부터 쭉 dfs로 내려오면서 지나온 노드들을 하나씩 더해 위상이 낮은(가벼운) 구슬에 갯수를 더해줬다.
이렇게 하면 구슬들이 자기보다 가벼운 요소가 몇개인지, 무거운 요소가 몇개인지 기억할 수 있기 때문.
예제, 테스트케이스는 전부 맞았지만,,,
n이 100과 거의 근사인 이 문제는
플로이드 워셜로 풀지않으면 절대.
시간 초과가 날 수밖에 없게 문제를 만들어 놓았음.
아무튼 그래서 플로이드 워셜을 다시 생각해 보았다. 내가 쓴 포스팅이 기억이 안나서 다시 봄
A 와 C의 대소를 비교할 수 없는 상황에서
B가 낀다면 비교가 가능하다는 것을 이용
최종으로 이용한 코드를 보자
from collections import deque
from itertools import permutations
import sys
import heapq
sys.setrecursionlimit(10**6)
n , m = map(int,sys.stdin.readline().strip().split())
graph = [[0 for _ in range(n)]for _ in range(n)]
graph_bigger = [0 for _ in range(n)]
graph_smaller = [0 for _ in range(n)]
for _ in range(m):
big , small = map(int,sys.stdin.readline().strip().split())
if graph[big-1][small-1] == 0:
graph[big-1][small-1] = -1
graph[small-1][big-1] = 1
graph_smaller[big-1] += 1
graph_bigger[small-1] += 1
###플로이드 워셜 n^3 for 문 ###
for k in range(n):
for i in range(n):
for j in range(n):
if i == j or i == k or j == k:
continue
elif graph[j][k] == 1 and graph[k][i] == 1 and graph[j][i] == 0:
graph_bigger[j] += 1
graph[j][i] = 1
elif graph[j][k] == -1 and graph[k][i] == -1 and graph[j][i] == 0:
graph_smaller[j] += 1
graph[j][i] = -1
result = 0
for i in range(n):
if abs(graph_smaller[i]) > n//2 :
result += 1
elif abs(graph_bigger[i]) > n//2 :
result += 1
print(result)중간에 있는 3중 for문이 플로이드 워셜 알고리즘을 활용한 로직이다.
나는 나보다 큰 놈이 몇개인지, 나보다 작은 놈이 몇개인지를 저장해주는 graph_bigger / graph_smaller 을 만들었다.
그리고 플로이드 워셜을 거치며 각 구슬별로 인덱스로 매칭하여 값을 넣었다.
결과는 성공~ 앙 기마리
백준 문제 풀이 시 배운 PyThon 문법
무한대의 수 사용법
양의 무한대와 음의 무한대를 사용하여 초기값을 설정해야 할 때가 있다.
이때는
`INF = float("inf")` 로 설정하고
INF를 무한대가 담긴 변수 값으로 사용하면 됩니다 !
순열 방식의 경우 리스트로 뽑아내기
>>> from itertools import permutations
>>> permutations([1,2,3,4])
<itertools.permutations object at 0x100cc7db0>
>>> list(permutations([1,2,3,4]))
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2),
(2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1),
(3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1),
(4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
>>>터미널에 찍어본 거라 >>>는 무시하삼
'Jungle' 카테고리의 다른 글
| [TIL][Krafton Jungle] 3주차 - (1) : 컴퓨터 시스템 정리 + DP (6) | 2023.10.26 |
|---|---|
| [TIL][Krafton Jungle] 2주차 - (7) : 누적 합과 스위핑 (1) | 2023.10.25 |
| [TIL][Krafton Jungle] 2주차 - (5) : 위상정렬 문제 풀이 연장 / 그 외의 공부 (1) | 2023.10.23 |
| [TIL][Krafton Jungle] 2주차 - (4) : 위상정렬 알고리즘 (4) | 2023.10.22 |
| [TIL][Krafton Jungle] 2주차 - (3) : DFS 알고리즘 공부 (5) | 2023.10.21 |