from collections import deque
def qualify(now, word):
no = list(now)[:]
wor = list(word)[:]
for x in now:
if x in word:
if (x in no) and (x in wor):
no.remove(x)
wor.remove(x)
if (len(no)==1) and (len(wor)==1):
return True
else:
return False
def solution(begin, target, words):
words.append(begin)
queue = deque()
queue.append(begin)
visited = [0]*len(words)
for x in words:
if x == begin:
visited[words.index(x)] = 1
if target not in words:
return 0
while queue:
now = queue.popleft()
for idx, word in enumerate(words):
if qualify(now, word) and (visited[idx]==0):
queue.append(word)
visited[idx] = visited[words.index(now)] + 1
answer = visited[words.index(target)]
if answer != 0:
return answer-1
if answer == 0:
return 0
게임맵 최단거리 로직과 비슷했다
BFS + Depth
가능한 다음 단어 찾는 qualify 함수 추가
begin의 단어가 words 리스트에 포함될 경우에 대한 별도 처리 필요!!! (처음 에러 이유)
*각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리 *캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동 *게임 맵을 벗어난 길& 검은 부분은 갈 수 없습니다 *상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다
input maps: 게임 맵의 상태 *n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열 *n, m 모두 1이상 100이하 자연수 *n, m모두 1인 경우는 없음. *0은 벽이 있는 자리, 1은 벽이 없는 자리
내 캐릭터 위치 초깃값: (1,1) == 게임맵 좌측 상단 상대 캐릭터 초깃값: (n,m) == 게임맵 우측 하단
output 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값 상대 팀 진영에 도착할 수 없을 때는 -1
1) BFS로 구현 + 효율성 최하
from collections import deque
def solution(maps):
n = len(maps[0]) #가로
m = len(maps) #세로
answer = []
queue = deque()
queue.append(((1,1), [(1,1)]))
while queue:
(a,b), route = queue.popleft()
neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
for (x,y) in neighbor:
if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
temp = route + [(x,y)]
if (x==n) and (y==m):
answer.append(len(temp))
else:
queue.append(((x,y), temp))
if not answer:
return -1
else:
return min(answer)
가능한 neighbor을 추려내어 queue에 저장
각 노드마다 자신에게 도달하기까지 거쳐야 하는 visited를 temp를 활용하여 모두 저장
노드가 도착지점이 되었을 때 answer에 visited의 length를 저장 후 그 가운데 min을 구함 → 아예 불필요한 절차. (무조건 첫번째 값이 answer가 되기 때문에 바로 return하면 됨)
2) BFS로 구현 + 효율성 하
from collections import deque
def solution(maps):
n = len(maps[0]) #가로
m = len(maps) #세로
answer = 0
queue = deque()
queue.append(((1,1), [(1,1)]))
while queue:
(a,b), route = queue.popleft()
neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
for (x,y) in neighbor:
if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
if (x==n) and (y==m):
answer = len(route)+1
return answer
else:
temp = route + [(x,y)]
queue.append(((x,y), temp))
if not answer:
return -1
min 절차 제외하고 answer 나오자마자 바로 return.
그렇다고 answer를 visited의 length로 구할 수 없음. answer에서 원하는 '방문 노드'와 BFS에서의 'visited'의 기능이 다르기 때문. → 각 경로의 vistied가 아니라, 큐 생성 시 제외할 노드를 가리기 위함.
여전히 효율성 0점인 이유는? 1. 각 노드마다 visited를 별도로 구해서 저장하는 게 최악의 비효율. 2. '노드가 도착지점이 되자마자' 그것이 거쳐 온 노드 개수가 바로 answer가 됨. 이 지점을 활용해야 하는데! 3. 경로마다 거쳐 온 노드 개수가 다른데 이건 BFS의 Depth를 활용하면 된다!
→ visited 기능을 구현하면서 + BFS의 Depth를 구하는 방법은?
3) BFS로 구현 + Depth 활용 + 효율성 최상 ⭐⭐⭐
from collections import deque
def solution(maps):
n = len(maps[0]) #가로
m = len(maps) #세로
answer = 0
queue = deque()
queue.append((1,1))
while queue:
a,b = queue.popleft()
neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
for (x,y) in neighbor:
if (1<=x<=n) and (1<=y<=m) and (maps[y-1][x-1] == 1):
queue.append((x,y))
maps[y-1][x-1] = maps[b-1][a-1] + 1
if maps[m-1][n-1] == 1:
return -1
else:
return maps[m-1][n-1]
명시적인 visited 리스트는 없지만 그 기능을 하는 것이 if maps[y-1][x-1] == 1 조건 원래 0이면(막혀 있으면) 로직 상 0 초과의 값을 가질 수 없음 1이면 '뚫려 있지만' '아직 방문된 적 없다'를 의미함 1 초과 값이면 '방문된 적 있다' & 해당 값은 '나를 방문하기까지 거쳐야 하는 노드 개수'를 의미함.
- 혹시 본인의 코드가 방문체크를큐에서 꺼낼 때하고있는건 아닌지 확인해보세요. 방문체크를큐에 넣을 때해야 효율성이 통과됩니다. 그 이유는 만약 꺼낼 때 방문체크를 하게되면, 하나의 블럭을 꺼내서 통로를 탐색할 때, 이미 큐에 들어있는 블럭을 또 큐에 넣을 수도 있기 때문입니다.
input k: 현재 피로도 (1이상 5000이하 자연수) 2차원 배열 dungeons: [["최소 필요 피로도", "소모 피로도"], [],...] *"최소 필요 피로도" >= "소모 피로도" *각 값은 1이상 1000이하 자연수 *dungeons 내 원소 중복 가능. ex) [[80,20],[50,40],[30,10]]
시작정점을 default((k, []))로 고정하고 BFS 기반으로 - for문 통해 그다음 노드를 선택(단, 조건 충족하는 것만 queue에 인큐)
graph는 주어진 2차원 배열 dungeons 사용
node(첫 시작)을 (k, [])로 지정함.
k: (현재 업데이트된) k값
[] : visited 역할을 하는 'route'. 어떤 노드를 거쳤는지 노드 인덱스 남기는 리스트. default는 빈 리스트.
queue 생성 필수: queue = deque()
while queue
중심 축(매번 업데이트되는 시작 정점)은 queue에서 popleft한 것. (k, route)
그 안에서 for문으로 처리
그다음 탐색할 노드(두 가지 조건 충족 )를 queue에 저장하거나
조건 충족 안 할 경우, max 활용하여 answer 업데이트
from collections import deque
def solution(k, dungeons):
answer = -1
queue = deque()
queue.append((k, []))
while queue:
k, route = queue.popleft()
for i in range(len(dungeons)):
a, b = dungeons[i]
if (k>=a) and (i not in route):
temp = route + [i]
queue.append(((k-b),temp))
else:
answer = max(answer, len(route))
return answer
-> 두 점을 연결하는 길이 있는가? 이를 확인하기 위해 하나씩 방문. (특정 도시에서 다른 도시로 갈 수 있는가? 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는가?)
너비 우선 탐색(BFS, Breath-First Search)
루트 노드(or 임의의 노드)에서 시작해서 '인접한' 노드를 먼저 탐색하는 방법
1. 의미
가까운 것부터.
깊게(deep) 탐색하기 전에 넓게(wide) 탐색.
(가중치가 동일할 때) 두 노드 사이의 최단 경로를 찾거나, 혹은 임의의 경로가 있는지 확인하고 싶을 때
지구상 모든 친구 관계를 '그래프'로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
BFS: A와 가장 가까운 관계부터 탐색 <-> DFS: 모든 친구 관계를 다 살펴봐야 할지도...
그러나 BFS가 DFS보다 좀 더 복잡한 경향 O
2. 특징
복잡해,, 좀 어렵지?
재귀적으로 동작하지 않음
어떤 노드를 방문했었는지 여부를 반드시 check해야 함. (그렇지 않으면 무한루프 가능 O)
BFS 방문 노드를 큐(Queue)에 차례로 저장, 하나씩 다시 꺼낼 수 있도록.
큐는 선입선출(FIFO): 먼저 들어간 게 먼저 나온다.
Prim, Dijkstra 알고리즘과 유사.
3. 과정
1) 시작 정점에서 깊이가 1인 모든 노드 방문
방문할 때마다 해당 원소가 enqueue
시작 정점은 dequeue
2) 깊이가 2인 모든 노드 방문
어떻게 보면, 시작 정점이 Queue의 첫번째 원소로 바뀐 셈.
이때 Queue에서 해당 원소가 dequeue됨.
바뀐 원소에서 깊이가 1인 걸 탐색하고, 만약 Queue에 이미 저장되어 있는 원소라면 pass.
3) 깊이가 3인....
4) 더 이상 방문할 곳이 없으면(큐가 소진될 때) 탐색 종료
4. 구현
deque 라이브러리를 활용, 큐.
시간 복잡도는O(N) (대체로 DFS보다 BFS가 우수)
1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고*방문 처리합니다. 2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다. 3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것입니다. 즉,큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이죠.
from collections import deque
def bfs(graph, node, visited):
# 그래프 탐색
# node는 시작 정점의 default
# visited는 graph의 node 개수만큼 False로 채워진 리스트
queue = deque([node])
visited[node] = True #방문 node에 방문 처리
while queue:
# queue가 완전히 빌 때까지 반복
v = queue.popleft() #선입선출
print(v, end = '')
for i in graph[v]:
if not (visited[i]):
queue.append(i)
visited[i] = True
2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고..
주어진 수의 제곱근까지만 확인해보면 끝난다.
1. python itertools-permutations 활용
from itertools import permutations
def solution(numbers):
nums = []
for i in range(len(numbers)):
nums += [int(''.join(x)) for x in list(permutations(numbers, i+1))]
answers = []
answers += [x for x in nums if (x in [2,3])]
for x in nums:
sqrt = int(x**(1/2))
for i in range(1,sqrt):
if x % (i+1) != 0:
if i+1 == sqrt:
answers.append(x)
continue
else:
break
nums = len(set(answers))
return nums
2. 재귀 알골 이용
def solution(numbers):
answers = []
def permutation(numbers, r):
used = [0 for _ in numbers]
def generate(chosen, used):
if len(chosen) == r:
chosen = int(''.join(chosen))
if (chosen in [2,3]) and (chosen not in answers): #2,3은 sqrt값이 1이므로 이하 for문이 실행되지 않음
answers.append(chosen)
sqrt = int(chosen**(1/2))
for i in range(1, sqrt):
if chosen % (i+1) != 0:
if (i+1 == sqrt) and (chosen not in answers):
answers.append(chosen)
break
continue
else:
break
return
for i in range(len(numbers)):
if not used[i]:
chosen.append(numbers[i])
used[i] = 1
generate(chosen, used)
used[i] = 0
chosen.pop()
generate([], used)
for i in range(len(numbers)):
permutation(numbers, i+1)
answer = len(answers)
return answer
append 하기 전, 중복 제거 필요
'구분자'.join(리스트)
map(''.join, 리스트)로 처리하면 빠름
순열 알고리즘 내에서, 모든 단어를 리스트에 저장하는 것이 아니라, 소수인 것만 filter 해서 저장 ←이때 에라토스테네스의 체
def gen_permutations(arr, n):
result = []
if n == 0:
return [[]]
for i, elem in enumerate(arr):
for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
result += [[elem]+P]
return result
2.2
def permutation(arr,r):
arr = sorted(arr)
used = [0 for _ in arr]
def generate(chosen, used):
if len(chosen) == r:
print(chosen)
return #used[i] = 0로 돌아가는데, 다시 for문 거치는 게 아니라, 바로 이어져서 i값이 유지됨.
for i in range(len(arr)): #arr은 함수 외부에 정해져 있음(상수수)
if not used[i]:
chosen.append(arr[i])
used[i] = 1
generate(chosen, used)
used[i] = 0 #순열 하나 만들고 나서, 다시 0으로 initialize
chosen.pop() #return이 없으므로 for문이 끝난 후에도 if문 다시 돌고, if문 만족 못하므로 for문 새로 시작됨
generate([], used)
좋은 코드라고는 하나 개인적으로 이해하는 데 시간이 걸렸음.
arr: 리스트 r: 리스트 중 뽑을 개수
[for문 안에서] chosen: 순열 구성하는 원소 리스트 used: chosen에 들어간 원소 index 위치에 해당 원소의 사용 여부를 0/1로 알려주는 리스트(즉 arr와 연동됨) (*디폴트는 0으로 채워짐)
함수 정의문에는 return의 위치가 중요함. for문이 모두 종료되었대도 return이 다른 곳에 있다면 다시 iteration 거침.
여기도 for문의 상단 if문을 거쳐야 return되는데, for문이 종료되고 if문으로 돌아갔을 때 if문 조건이 성립되지 않으므로 return이 실행되지 않음. 즉, 다시 for문으로 돌아가 처음부터 실행됨. (물론 이 상황에서 used와 chosen은 이전 로그가 반영된 상태이므로 i값이 슉슉 점프하게 됨.
generate 함수 정의문 내부에 generate가 사용된 재귀형식임.
내부 generate이 실행될 때 if문 만족되면 바로 return 일어나므로, 내부 generate 실행 직전 i값이 그대로 보존된 상태로 used[i]=0 코드로 넘어감.
만약 내부 generate 실행될 때 if문 만족 못 하면 for문으로 넘어가고, 결국 내부 generate가 종료되려면 내부 if문이 만족될 때까지 iter iter iter..
input answers: 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 ex. [1,2,3,4,5]
return 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아서 ex. [1] *가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬.
나의 코드
def solution(answers):
n = len(answers)
fir = [1,2,3,4,5]*(n//5)+[1,2,3,4,5][:(n%5)]
sec = [2,1,2,3,2,4,2,5]*(n//8)+[2,1,2,3,2,4,2,5][:(n%8)]
thir = [3,3,1,1,2,2,4,4,5,5]*(n//10)+[3,3,1,1,2,2,4,4,5,5][:(n%10)]
def compare(data):
cnt = 0
for idx, i in list(enumerate(data)):
if i == answers[idx]:
cnt +=1
return cnt
fir_val = compare(fir)
sec_val = compare(sec)
thir_val = compare(thir)
lst = sorted([(1,fir_val), (2, sec_val), (3, thir_val)], key=lambda x: x[1], reverse=True)
answer = [lst[0][0]]
for (idx, val) in lst[1:]:
if val == lst[0][1]:
answer.append(idx)
return answer
모범 코드
def solution(answers):
pattern1 = [1,2,3,4,5]
pattern2 = [2,1,2,3,2,4,2,5]
pattern3 = [3,3,1,1,2,2,4,4,5,5]
score = [0, 0, 0]
result = []
for idx, answer in enumerate(answers):
if answer == pattern1[idx%len(pattern1)]:
score[0] += 1
if answer == pattern2[idx%len(pattern2)]:
score[1] += 1
if answer == pattern3[idx%len(pattern3)]:
score[2] += 1
for idx, s in enumerate(score):
if s == max(score):
result.append(idx+1)
return result
[idea] 리스트 내 원소에 특정 패턴이 반복되는 경우
pattern 변수 통해 반복되는 부분만 따오기
[idx % (패턴의 길이)] 인덱스 처리.
for문 순환하여 세 명의 score 병렬 계산 (어차피 answers와 세 명의 대답 length가 동일함)
score = [0,0,0] 처리 후 한꺼번에 score[x] +=1
마지막 출력 처리하는 건.... 나 왜 저렇게 짰지?🫢 모범코드대로 하는 게 당연할 따름. idx 순서대로 처리되니 더더욱?!
input sizes: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 (ex. [[60, 50], [30, 70], [60, 30], [80, 40]]) *원소 개수 최소 1 *명함 가로, 세로는 최소 1, 최대 100
return 지갑의 크기 (ex. 4000)
나의 코드
def solution(sizes):
big = []
small = []
for [x,y] in sizes:
if x >= y:
big.append(x)
small.append(y)
else:
big.append(y)
small.append(x)
answer = max(big)*max(small)
return answer
