05. BFS/DFS
음료수 얼려먹기
풀이시간: 25분, 시간복잡도 : O(N^2)
- 내코드
"""
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
4 5
00110
00011
11111
00000
"""
def DFS(x, y, ice, n, m):
ice[x][y]=1
for k in range(4):
nx = x+ dx[k]
ny = y+ dy[k]
if nx>=0 and ny>=0 and nx<n and ny<m and ice[nx][ny]==0:
DFS(nx, ny, ice, n, m)
n, m = map(int, input().split())
ice = []
answer=0
for _ in range(n):
ice.append(list(map(int, input())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for i in range(n):
for j in range(m):
if ice[i][j]==0:
answer+=1
DFS(i, j, ice, n, m)
print(answer)백준 포맷이 익숙하지 않아 값을 받아올때
ice.append(list(map(int, input().split()))을 사용했을때 0의 값이 읽히지 않아 막혔었음. 공백이 없으니 공백기준이 아니라 바로input()만 사용해도 괜찮았다.
- 책코드
n, m = map(int, input().split())
ice = []
for _ in range(n):
ice.append(list(map(int, input())))
def DFS(x, y):
# 범위가 벗어나는 경우
if x<=-1 or y<=-1 or x>=n or y>=m:
return False
# 해당 위치를 방문하지 않았으면
if ice[x][y]==0:
ice[x][y]=1
#상, 하, 좌, 우 위치 호출
DFS(x-1, y)
DFS(x, y -1)
DFS(x+1, y)
DFS(x, y+1)
return True
return False
answer = 0
for i in range(n):
for j in range(m):
if DFS(i, j) == True:
answer +=1
print(answer)boolean을 이용한 방법이 특이했음
내코드는 대개 시물레이션같은 문제에서 조건을 줄때 방문할수 있는 경우를 조건문으로 넣는데 책 코드는 방문할 수 없는 위치를 조건을 둔 부분이 새로웠다.
미로탈출
풀이시간 : 1시간10분 , 시간복잡도 : O(N^2)
- 내코드
# 0,0 기준이 문제 상에는 1,1임.
def DFS(x, y, n, m):
# graph[x][y] += 1 #계속 1+=1이기 때문에 2가됨... 으으으으음
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx>=0 and ny>=0 and nx<n and ny<m and graph[nx][ny]==1:
graph[nx][ny]= graph[x][y]+1 #상하좌우값 = 이전값+1
DFS(nx, ny, n, m)
elif nx == n-1 and ny==m-1:
break
n, m = map(int, input().split())
graph=[]
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 1발견 까지는 좋은데 최단거리 or 막혀있는 경우는 어떻게 배제시킬 것인가 => 1씩 증가값을 매기자
for i in range(n):
for j in range(m):
if graph[i][j]==1:
DFS(i, j, n, m)
print(graph[i][j])처음에는 어떤식으로 최단거리를 구할지 막혔다가 30분 이후 책으로 아이디어 얻음. 정답은 나왔는데 테케가 많이 없다보니 제대로된 코드가 맞는지 의문이 듬.
+) 원래는 DFS(x좌표, y좌표,cnt(증가값), n크기, m크기)를 사용해서 cnt에 증가값들을 저장하려고 했으나 구현에서 에러가 뜸....
- 책풀이 BFS
from collections import deque
n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def BFS(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 ny<0 or nx >=n or ny >=m:
continue
# 벽인 경우 무시
if graph[nx][ny]==0:
continue
# 노드를 처음 방문하는 경우 최단 거리 기록
if graph[nx][ny]==1:
graph[nx][ny] = graph[x][y]+1
queue.append((nx, ny))
# 최종값 반환
return graph[n-1][m-1]
print(BFS(0,0))미로탈출 테케 2,4 에러
- 백준 미로검색 : https://www.acmicpc.net/problem/2178 문제에서
테케 2,4번 정답이 다르다.dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def DFS(x, y, n, m, graph): for k in range(4): nx = x + dx[k] ny = y + dy[k] if nx>=0 and ny>=0 and nx<n and ny<m and graph[nx][ny]==1: graph[nx][ny]= graph[x][y]+1 DFS(nx, ny, n, m, graph) elif nx == n-1 and ny==m-1: break def solution(n, m, graph): for i in range(n): for j in range(m): if graph[i][j] == 1: DFS(i, j, n, m, graph) return graph[i][j] print(solution(4,6,[[1,1,0,1,1,0],[1,1,0,1,1,0],[1,1,1,1,1,1],[1,1,1,1,0,1]])) #ex2 print(solution(4,6,[[1,0,1,1,1,1],[1,0,1,0,1,0],[1,0,1,0,1,1],[1,1,1,0,1,1]])) #ex1DFS를 사용했기 때문에 먼저 발견한 1을 기준으로 깊이탐색을 먼저 진행함.
그러다보니까 값이 달라졌다... ㅎ
06. 정렬
선택 정렬 - O(N^2)
가장 작은 데이터를 선택해 만 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]삽입정렬 - O(N^2)
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다
삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 정렬되어 있을때 효율적
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j]<array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]퀵정렬 - O(NlogN)
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array, start, end):
if start >= end :
return
pivot = start
left = start +1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left +=1
while right > start and array[right] >= array[pivot]:
right -=1
if left > right:
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
quick_sort(array, start, right -1)
quick_sort(array, right +1, end)
quick_sort(array, 0, len(array)-1)
print(array)계수정렬 - O(N+K)
특정한 조건이 부합 할 때만 사용할 수 있ㅈ미ㅏㄴ 매우 빠른 정렬 알고리즘
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
cnt = [0] * (max(array)+1)
for i in range(len(array)):
cnt [array[i]] += 1
for i in range(len(cnt)):
for j in range(cnt[i]):
print(i, end=' ')코딩테스트의 정렬 알고리즘 사용 경우
1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
선택정렬, 삽입정렬, 퀵 정렬등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제
퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고맂므의 구조적인 개선을 거쳐야 풀 수 있다.
위에서 아래로
- 내코드
3분.. 시간복잡도 : NlogN
n = int(input())
arr = []
for _ in range(n):
a = int(input())
arr.append(a)
# arr.sort(reverse=True)
print(sorted(arr, reverse=True))성적이 낮은 순서로 학생 출력하기
- 내코드
10분 시간복잡도: NlogN
n = int(input())
arr = []
for _ in range(n):
name ,score = map(str, input().split())
arr.append((name,int(score)))
s = sorted(arr, key=lambda v: v[1]) #오름차순 정렬 // 내림차순 정렬: (arr, key=lambda v: -v[1])
for x in s:
print(x[0], end=' ')값 입력시 튜플로 받을때 위치를 인덱스로 지정하는 방법도 있다.
- 책코드
for i in range(n): input_data = input().split() array.append(input_data[0], int(input_data[1]))
두 배열의 원소 교체
- 내코드
시간: 11분 , 시간복잡도: NlogN
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
a = deque(a)
b = deque(b)
while k>0:
k-=1
a.popleft()
a.append(b.popleft())
print(sum(a))
개발기록