1. 타겟 넘버
dfs로 구현하면 된다.
내 코드
def solution(numbers, target):
global answer
answer = 0
def check(nums, depth, target):
global answer
if depth == len(nums):
# 계산 후 타겟과 비교
if sum(nums) == target:
answer += 1
# 카운트
return
else:
check(nums, depth+1, target)
nums[depth] = -nums[depth]
check(nums, depth+1, target)
check(numbers, 0, target)
return answer
베스트 코드
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
이런 코드도 있지만.. 사실 일반적으로 떠올리기 어렵기 때문에 선호하지 않는다.
그렇지만 아름답다.
2. 네트워크
노드 탐색이다. 다만 입력되는 데이터의 형태가 다소 생소했다.
2차원 리스트가 주어지는데 0번 인덱스의 리스트는 0번 노드와 연결여부를 1/0으로 나타낸다.
[[1, 1, 0], [1, 1, 0], [0,0,1] 이렇게 주어진다면
0번노드는 0번노드, 1번노드와 연결되어있다.
1번노드는 0번노드, 1번노드와 연결되어있다.
2번노드는 2번노드와 연결되어있다.
-> 자기자신은 연결되어있다고 표시한다. node[i][i] 는 항상 1이다.
이런 식으로 입력되는 그래프 데이터를 탐색하고, 총 몇 개로 연결되는지를 카운트하면 된다.
bfs로 풀이했다.
내 코드
from collections import deque
def solution(n, computers):
answer = 0
visited = [False]*n
def bfs(start):
que = deque([start])
visited[start] = True
# print("start",start)
while que:
x = que.popleft()
nx = computers[x]
for i in range(len(nx)):
if nx[i]==1 and not visited[i]:
visited[i] = True
print(i)
que.append(i)
return 1
for node in range(n):
if not visited[node]:
answer += bfs(node)
return answer
visited라는 이름의 플래그 리스트를 만들고 노드 방문 여부를 기록한다.
이를 기준으로 노드 루프를 돌면서 방문하지 않은 노드만 다시 bfs형태로 진행하도록 한다.
bfs의 호출 횟수를 기록하면 된다.
플래그 : 컴퓨팅에서 플래그는 무언가를 기억하거나 약속된 신호를 남기기 위해 사용되는 미리 정의된 비트.
그래프 문제를 풀 때마다 사용하는 visitied 리스트가 이런 역할을 수행했다.
https://ko.wikipedia.org/wiki/%EB%B9%84%ED%8A%B8_%ED%95%84%EB%93%9C
비트 필드 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org
공식적인 이름은 비트 필드인 듯 하다.
베스트 풀이
: 사실 베스트 풀이는 내 풀이와 비슷했다. 하지만 신기한 코드가 있어서 가져와봤다.
def solution(n, computers):
temp = []
for i in range(n):
temp.append(i)
for i in range(n):
for j in range(n):
if computers[i][j]:
for k in range(n):
if temp[k] == temp[i]:
temp[k] = temp[j]
return len(set(temp))
댓글에 적힌 바로는 플루이드-워셜 알고리즘을 사용했다고 한다.
검색해보니 다익스트라 알고리즘과 함께 최단경로를 탐색하는데 사용하는 알고리즘이라고 한다.
그래프 탐색을 조금 더 깊이있게 공부하게 된다면 알아보면 좋을 듯 하다.
3. 단어 변환
단어를 한 자리씩 변환하면서 목표 단어에 도달해야한다. 하지만 변환 후의 단어는 리스트 내에 존재하는 단어여야한다.
dfs로 풀이했다.
내 코드
def check(s1, s2):
cnt = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
cnt += 1
if cnt > 1:
return False
return True if cnt == 1 else False
def solution(begin, target, words):
answer = [len(words)+1]
# dfs?
visited = [False]*len(words)
def solve(s, depth,target):
if s == target:
answer[0] = min(answer[0], depth)
return
for i in range(len(words)):
w = words[i]
if not visited[i] and check(w, s):
visited[i] = True
solve(w, depth+1, target)
visited[i] = False
solve(begin,0, target)
return answer[0] if answer[0] <= len(words) else 0
단어를 변경할 때 리스트에 저장되어있는 단어를 그대로 사용했다. 대신에 이 전에 단어와 한 자리만 차이나는 단어인지를 검사하는 함수를 추가로 사용했다.
생각보다 깔끔하게 풀려서 기뻤다.
베스트 코드
from collections import deque
def get_adjacent(current, words):
for word in words:
if len(current) != len(word):
continue
count = 0
for c, w in zip(current, word):
if c != w:
count += 1
if count == 1:
yield word
def solution(begin, target, words):
dist = {begin: 0}
queue = deque([begin])
while queue:
current = queue.popleft()
for next_word in get_adjacent(current, words):
if next_word not in dist:
dist[next_word] = dist[current] + 1
queue.append(next_word)
return dist.get(target, 0)
yield는 제네레이터라는 존재인데... 나중에 더 알아보자. (술 마신 채 쓰는 블로그라 머리아픔)
4. 여행경로
내 코드 (50점 맞은 코드..)
def solution(tickets):
ways = dict()
for t in tickets:
prev, dest = t
try:
ways[prev].append(dest)
except:
ways[prev] = [dest]
for r in ways.keys():
ways[r].sort(reverse=True)
start = "ICN"
answer = []
while start in ways and ways[start]:
answer.append(start)
start = ways[start].pop()
answer.append(start)
return answer
정답 코드
def solution(tickets):
ways = dict()
for t in tickets:
prev, dest = t
try:
ways[prev].append(dest)
except:
ways[prev] = [dest]
for r in ways.keys():
ways[r].sort(reverse=True)
start = ["ICN"]
answer = []
while start:
last = start[-1]
if last not in ways or len(ways[last]) == 0:
answer.append(start.pop())
else:
start.append(ways[last].pop())
return answer[::-1]
문제의 핵심은 리스트 형태로 주어지는 노드들의 관계를 딕셔너리 형태로 변경할 수 있는지, 또 그 딕셔너리를 기반으로 그래프 탐색을 진행할 수 있는지 여부라고 생각하면 된다.
정답코드의 형태는 스택을 활용한 DFS라고 할 수 있다.
재귀를 사용하는게 불편한 경우 사용하면 좋다.
내가 실수한 점이라면, while 부분을 작성할 때 설정한 조건이라고 할 수 있겠다.
스택을 사용해야 한다는 점과, 리스트에서 값을 추출하는 작업을 원활히 진행하기 위해 역정렬하지 못한게
흠인 것 같다.
list.pop(0)보단 list.pop()이 훨씬 빠를테니까.
너무 아쉽게 틀렸지만 dfs를 사용하는 새로운 방법을 알게된 것 같아 기쁘다.
'Algorithm > programmers.co.kr' 카테고리의 다른 글
프로그래머스 연습문제 : 정수 제곱근 판별 (0) | 2024.10.24 |
---|---|
프로그래머스 고득점 kit #DP : N으로 표현 (3) | 2024.10.23 |
프로그래머스 고득점 kit 풀기 #정렬 (0) | 2022.03.13 |
프로그래머스 고득점 kit 풀기 #스택/큐 (0) | 2022.03.12 |
프로그래머스 고득점 kit 풀기 #해시 (0) | 2022.03.12 |