🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법phone_book에 있는 한 번호가 다른 번호의 접두어인지 확인하는 문제이다. 따라서 문자열을 기준으로 정렬을 수행한다. 이후 현재 번호가 바로 다음 번호의 접두어에 해당하는지 확인한다.만약 접두어에 해당할 경우 False를 출력하고, 해당하지 않을 경우 다음 번호를 비교한다. 😎 내 코드def solution(phone_book): answer = True ..
Algorithm
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법노드를 최대한으로 방문하면 하나의 네트워크가 형성된다. 해당 네트워크의 개수를 구하는 문제이다.DFS를 통해 한 번 탐색을 시작할 때 최대한으로 탐색한다. 또한 visited 리스트를 사용하여 노드 방문 여부를 체크한다. 😎 내 코드def solution(n, computers): answer = 0 visited = [False] * n def ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법최단거리를 구하기 위해 BFS를 사용한다.이때 상하좌우로 이동하면서 맵을 탐색해야 한다. 따라서 변화량을 나타내는 dx와 dy 리스트를 생성한다. 초기 시작 위치를 (0, 0)으로 지정하고, 시작 위치에서부터 상하좌우로 탐색한다. 탐색하면서 조건문을 통해 맵을 벗어나지 않는지, 벽이 아닌지, 방문한 적이 없는지 확인한다.위 조건을 모두 만족할 경우 방문 처리를 수행하고, 맵..
🗂️ 문제링크: https://www.acmicpc.net/problem/1325 💡 접근법BFS/DFS를 사용하여 각 정점에서 이동할 수 있는 정점들의 최대 개수를 구하는 문제이다."A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다." 즉, 방향이 있는 그래프를 만들어 B → A 단방향 그래프를 정의해야 한다. 또한 시간복잡도 제한때문에 Python3가 아닌 PyPy3로 제출해야 성공할 수 있다. 😎 내 코드import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): a, b = map(int, sys..
🗂️ 문제링크: https://www.acmicpc.net/problem/1753 💡 접근법가중치가 자연수인 방향 그래프이므로 최단 경로를 구하기 위해 다익스트라를 사용해야 한다. 또한 거리가 가장 작은 노드를 자동으로 선택하기 위해 우선순위 큐(heapq)를 사용한다. distance의 요소는 모두 INF로 초기화되어 있다. 만약 if distance[now_node] 조건을 만족할 경우 now_node는 이미 방문된 노드이므로 방문 처리를 위한 visited 리스트가 따로 필요하지 않다.또한 해당 조건을 만족할 경우 이미 dist는 distance[now_node]보다 큰 값이기 때문에 dist 값으로는 now_node와 연결된 다른 노드의 최단 거리를 구할 수 없다. 따라서 continue를 ..
🗂️ 문제링크: https://www.acmicpc.net/problem/18352 💡 접근법인접 리스트를 통해 그래프를 구현하고, BFS를 사용하여 각각의 도시까지의 최단 거리를 distance 리스트에 저장한다. 현재 노드의 거리 값은 이전 노드의 거리 값 + 1이다.이후 K와 거리가 같은 도시를 출력하면 된다. 😎 내 코드import sysfrom collections import dequedef BFS(v): queue = deque() queue.append(v) visited[v] = True while queue: now_node = queue.popleft() for i in graph[now_node]: if not ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법바위 사이의 거리의 최솟값을 기준으로 이진 탐색의 범위를 조절해야 한다. low는 distance의 바위 사이 거리의 최솟값인 1로, high는 바위 사이 거리의 최댓값인 distance로 설정한다. mid를 바위 사이 거리의 최솟값으로 생각하고 탐색을 진행한다. 이때 바위 사이의 거리의 최솟값 중 최댓값을 구하는 것이 목표이다. 따라서 바위 사이의 거리를 구하고, 구한 ..
🗂️ 문제링크: https://www.acmicpc.net/problem/10815 💡 접근법이분탐색 시 탐색 범위를 설정해야 한다. 해당 문제에서는 카드 리스트를 정렬하고, 카드 리스트 인덱스의 최솟값(0)과 최댓값(len(card_list)-1)을 low와 high로 각각 지정한다. mid의 값을 변경하며 탐색한다. 이때 카드 리스트에서 mid 인덱스에 해당하는 값보다 상근이가 가지고 있는 숫자가 작으면 mid 값을 줄여야하므로 high = mid - 1로 설정한다. 반대의 경우엔 mid 값을 키워야하므로 low = mid + 1로 설정한다. 만약 카드 리스트에서 mid 인덱스에 해당하는 값이 상근이가 가지고 있는 숫자와 같다면 1을 저장한다. 😎 내 코드import sysN = int(sys...
