No. 4963
1. Problem
2. My Solution
- DFS 알고리즘을 이용해서 문제 해결
- setrecursionlimit(100000) 설정
import sys
sys.setrecursionlimit(100000)
def dfs(x,y):
if 0 <= x < h and 0 <= y < w and land_sea[x][y] == 1:
land_sea[x][y] = 0
for dx,dy in d:
nx = x + dx
ny = y + dy
dfs(nx,ny)
while(True):
w,h = map(int,sys.stdin.readline().rstrip().split())
if w == 0 and h == 0:
break
land_sea = []
count = 0
d = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
for i in range(h):
land_sea.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(h):
for j in range(w):
if land_sea[i][j] == 1:
dfs(i,j)
count += 1
print(count)- BFS 알고리즘을 이용해서 문제 해결
import sys
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
land_sea[x][y] = 0
while(queue):
x,y = queue.popleft()
for dx,dy in d:
nx = x + dx
ny = y + dy
if 0 <= nx < h and 0 <= ny < w and land_sea[nx][ny] == 1:
queue.append((nx,ny))
land_sea[nx][ny] = 0
while(True):
w,h = map(int,sys.stdin.readline().rstrip().split())
if w == 0 and h == 0:
break
land_sea = []
count = 0
d = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
for i in range(h):
land_sea.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(h):
for j in range(w):
if land_sea[i][j] == 1:
bfs(i,j)
count += 1
print(count)No. 11724
1. Problem
- 무방향 연결 요소 (Connected Component) 개수 구하는 문제
2. My Solution
- 각 정점마다 인접한 정점의 정보를 저장 (graph)
- DFS 알고리즘을 이용하여 문제 해결
import sys
sys.setrecursionlimit(1000000)
def dfs(v):
visited[v] = True # 방문 표시
for u in graph[v]: # 정점 v와 인접한 정점들을 하나씩 살펴보면서
if visited[u] == False: # 만약 방문하지 않았다면 dfs로 방문
dfs(u)
n, m = map(int,sys.stdin.readline().rstrip().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
count = 0
for i in range(m): # 해당 정점과 인접한 정점들을 저장
u, v = map(int,sys.stdin.readline().rstrip().split())
graph[u].append(v)
graph[v].append(u)
for i in range(1,n+1):
if visited[i] == False:
dfs(i)
count += 1
print(count)- BFS 알고리즘을 이용하여 문제 해결
import sys
from collections import deque
def bfs(v):
queue = deque()
queue.append(v)
visited[v] = True
while(queue):
v = queue.popleft()
for u in graph[v]:
if visited[u] == False:
queue.append(u)
visited[u] = True
n, m = map(int,sys.stdin.readline().rstrip().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
count = 0
for i in range(m): # 해당 정점과 인접한 정점들을 저장
u, v = map(int,sys.stdin.readline().rstrip().split())
graph[u].append(v)
graph[v].append(u)
for i in range(1,n+1):
if visited[i] == False:
bfs(i)
count += 1
print(count)
4. Learned
- 그래프에서 사용되는 탐색 기법인 DFS & BFS 알고리즘은 모든 정점끼리 연결되었다고 볼 수 있는 좌표(x,y) 문제에 자주 쓰임
No. 15661
1. Problem
2. My Solution
- Python3 로 제출하면 시간초과
- PyPy3 로 제출하면 성공
- 구성가능한 모든 팀의 조합을 구하기 위해서 combinations 함수 이용
- 팀원의 수는 2 ~ n/2 까지 구해보면 됨
(만약 6명이 있을 때 한 팀을 2명으로 구성하면 다른팀은 4명이고 굳이 4명팀을 다시 구성할 필요 X)
import sys
import math
from itertools import combinations
n = int(sys.stdin.readline())
player = set([i for i in range(1,n+1)])
s = []
res = math.inf
for _ in range(n):
s.append(list(map(int,sys.stdin.readline().rstrip().split())))
# 팀 나누기
for i in range(2, (n//2)+1):
possible_team = list(combinations(player,i))
# 중복되는 경우를 피하기 위함
if n % i == 0:
possible_team = possible_team[:len(possible_team)//2]
for start_team in possible_team:
start_s = 0
link_s = 0
link_team = player - set(start_team)
start_player = list(combinations(start_team,2))
link_player = list(combinations(link_team,2))
for p1, p2 in start_player:
start_s += (s[p1-1][p2-1] +s[p2-1][p1-1])
for p1, p2 in link_player:
link_s += (s[p1-1][p2-1] +s[p2-1][p1-1])
diff = abs(start_s - link_s)
res = min(res, diff)
print(res)- 리팩토링 및 시간단축
- start 팀과 link 팀의 능력치 구하는 기능이 똑같으므로 함수로 구현 (시간 단축 효과도 있었음)
- 두팀의 멤버의 수가 동일한 경우 중복된 조합이 나오므로 조건을 걸어줌
- 능력치합을 미리 구해서 s[link[p1]][link[p2]] 이런식으로 여러번 접근하지 않도록 함 (시간단축)
1 2 3 4 멤버가 있을 때
1 2 vs 3 4
1 3 vs 2 4
1 4 vs 2 3
2 3 vs 1 4 // 여기서부터 겹침
2 4 vs 3 4
3 4 vs 1 2import sys
import math
from itertools import combinations
def sum(team):
temp = 0
for i in range(len(team)-1):
for j in range(i + 1, len(team)):
temp += stat[team[i]][team[j]]
return temp
n = int(sys.stdin.readline())
player = [i for i in range(n)]
stat = [[0] * n for _ in range(n)]
S = []
res = math.inf
for _ in range(n):
S.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(n):
for j in range(n):
if not stat[i][j] or not stat[j][i]:
stat[i][j] = stat[j][i] = S[i][j] + S[j][i]
for i in range(2, (n//2)+1):
possible_team = list(combinations(player,i))
if n % i == 0:
possible_team = possible_team[:len(possible_team)//2]
for start in possible_team:
link = list(set(player) - set(start))
diff = abs(sum(start) - sum(link))
res = min(res, diff)
print(res)
4. Learned
- Python3 보다는 PyPy3 가 연산속도가 훨씬 빠름, 하지만 메모리 공간은 PyPy3 가 훨씬 많이 차지하기 때문에 문제의 조건에 맞춰서 제출
No. 1157
1. Problem
2. My Solution
- 계수 정렬 원리 이용
- 오히려 저번보다 시간이 더 걸림
import sys
word = sys.stdin.readline().rstrip().upper()
alphabet_cnt = [0] * 26
for i in word:
alphabet_cnt[ord(i) - 65] += 1
max_cnt = max(alphabet_cnt)
if alphabet_cnt.count(max_cnt) > 1:
print("?")
else:
print(chr(alphabet_cnt.index(max_cnt)+65))
3. Learned
- 파이썬은 내장 기능(내장 함수)으로 구현된 것과 파이썬 스크립트로 구현된 코드의 실행 속도에 엄청난 차이가 존재함. count와 같은 내장 기능은 C에 가까운 속도를 낼 수 있지만 스크립트 실행은 시간이 오래걸림
