<목표>
1. 백준 문제집 그래프 클리어
2. 그래프 탐색 아이디어
3. 실리콘밸리의 해적들 보기
"히히 꿀잼"
장소 /시간 : 궁동 카페, 12.30수, 1:20 - 4:20 (비대면으로 진행)
1. 백준 문제집 그래프 클리어
종강 후 모각코 전까지 틈틈히 공부를 했다. 죽고리즘을 하면서 그래프 문제집에 있는 문제들을 다 풀어버렸다.
오늘은 문제들을 훑어보면서 복습하는 시간을 가지겠다.
2. 그래프 탐색 아이디어
(1). DFS, BFS
| DFS(Depth First Search) | BFS(Breadth First Search) |
 |
 |
그래프를 탐색은 두 가지로 나뉠 수 있다.(DFS, BFS) 위 방법을 이용하여 문제를 해결한다. 문제의 조건에 따라 선택하여 사용하지만 나는 보통 BFS을 응용하여 문제를 해결했다.
파이썬 코드 구현을 하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
field = {} # 그래프를 정리할 딕셔너리(key:노드, value:인접리스트)
visited = [False for _ in range(n + 1)] # 이걸로 방문 여부 확인
def DFS(start): # start 시작할 노드
visited[start] = True
for next_node in field[start]:
if not visited[next_node]:
DFS(next_node)
def BFS(start):
visited[start] = True
queue = deque([start]) # 단순히 pop, append 해주는 것보다 시간 절약됨
while queue:
q = queue.popleft()
for p in field[q]:
if not visited[p]:
visited[p] = True
queue.append(p)
|
(2). 인접 리스트로 풀기
1. 노드의 개수
2. 간선의 개수
3. 각 간선의 양끝 노드/ 노드의 길이
위에 있는 것이 주어지면 인접 리스트를 이용했다. 파이썬 딕셔너리를 이용하여 그래프를 처리했다.
인접 리스트는 다양한 방식으로 응용될 수 있었다. 연결요소의 개수부터 사이클까지 복잡한 문제로 나를 괴롭혔다. 나에게는 예제를 그래프로 그려보는 것이 도움이 되었다. 확실히 시각화하니까 문제를 이해하고 코드를 짜기에 쉬웠다.
특히 노드 코드를 짤 때 양방향인지 아니면 일방향인지 확인하는 것이 중요하다.
정점의 개수, 간선의 개수가 주어지고 그에 맞춰 간선이 주어질 때 딕셔너리로 정리하는 코드다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
n, m = map(int, input().split()) # 노드의 개수 n, 간선의 개수 m
field = {} # 그래프를 정리할 딕셔너리(key:노드, value:인접리스트)
for _ in range(m):
a, b = map(int, input().split()) # 간선이 연결된 노드 두 개가 주어짐
if a not in field: # 딕셔너리에 노드가 없다면 추가
field[a] = [b]
elif b not in field[a]: # 노드에 인접리스트의 요소가 없다면 추가
field[a].append(b)
if b not in field: # 양방향일때
field[b] = [a]
elif a not in field[b]:
field[b].append(a)
|
간선 입력이 노드 노드 길이면 value값에 ( 인접리스트 요소, 간선 길이)로 입력해준다.
[기본] 순열 사이클 
10451번: 순열 사이클
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3
www.acmicpc.net
리스트의 인덱스가 노드가 된다.
[응용1] 트리의 지름 
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지
www.acmicpc.net
트리의 지름을 구하기 위해서
1. 노드 하나를 선택한다.
2. 선택한 노드부터 가장 멀리 떨어진 노드를 찾는다.
3. 가장 먼 노드부터 먼 노드를 구한다.
[응용2] 이분 그래프 
https://www.acmicpc.net/problem/1707
1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수
www.acmicpc.net
레드블랙트리를 이용한다.
(3). 인접 행렬로 풀기
1. 인접 행렬의 크기
2. 인접 행렬
위에 있는 것들이 주어지면 인접 행렬을 이용하여 풀었다.
인접 행렬을 문제 풀이에 맞게 변형하는 것이 중요했다. 조건을 고민해 보고 코드를 작성한다.
[기본] 단지번호 붙이기
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
조건을 잘 생각해서 작성한다.
[응용1] 토마토
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
시작점 부터 범위 까지 1식 더해준다.
[응용2] 다리 만들기
https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
단지번호 붙이기와 토마토 풀이를 사용했다.
섬 마다 번호를 붙인다.
범위로 늘어난 다음에 다리가 만들어졌는지 확인한다.
3. 실리콘밸리의 해적들
<실리콘 밸리의 해적들>을 시청했다. 스티브잡스와 빌 게이츠를 주로 다룬 영화였다.
컴퓨터 출시부터 소프트웨어 프로그램 체계가 구성되는 시점까지의 시대를 축약해서 봤다.
다른 매체로 접할 때는 그저 모든 회사 정체성을 대표와 처음 창립 멤버의 머릿속에서 시작된 줄 알고 있었다. 하지만 영화를 보면서 애플과 마이크로소프트 회사는 많은 기업의 아이디어를 도적질했다는 것을 깨달았다. 작은 발명이 중요한 게 아님을 느꼈다. 오히려 주인공들의 넓은 안목과 비전이 역사를 만든다는 것을 깨달았다.
'2020활동-1학년 > 2020 동계 모각코' 카테고리의 다른 글
| [모각코 5회 회고록] 코드포스 대회/ 빅데이터 강의 듣기 (0) | 2021.01.27 |
|---|---|
| [모각코 4회 회고록] 코드포스 대회/ 빅데이터 강의 (0) | 2021.01.20 |
| [모각코 3회 회고록] 파이썬 빅데이터 교육듣기 (0) | 2021.01.13 |
| [모각코 2회 회고록] (0) | 2021.01.13 |
| 동계모각코 brute-force 활동 계획 (0) | 2020.12.19 |
