👾

문제 링크: programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 설명 DFS를 이용해 모든 티켓을 사용하는 경로를 탐색합니다. 이때 DFS의 순서를 스택에 저장했다가 스택 top에서 갈 수 있는 경로가 없을 경우에 answer에 추가합니다. 갈 수 있는 경로가 없다는 것은 그 공항이 제일 마지막 방문지라는 의미입니다. 즉, answer에는 공항을 방문하는 순서가 거꾸로 저장되게 됩니다. ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 각 단어가 한 글자씩만 차이 나는 경우(ex. hot과 hit) 단어 변환이 가능합니다. 단어들을 정점들로, 변환이 가능한 경우를 간선으로 표시해서 BFS를 이용해 문제를 해결했습니다. begin을 포함해서 그래프를 만들기 위해 words에 begin 단어를 삽입 그래프를 표현하는 인접 리스트 초기화 이때 두 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설명 BFS를 이용해 연결된 모든 컴퓨터를 탐색하는 방법으로 문제를 해결했습니다. 방문하지 않은 컴퓨터 중 작은 번호부터 BFS 수행 BFS가 끝나면 네트워크 개수 1 증가 (answer++) 방문하지 않은 컴퓨터가 없을 때까지 1~2번을 반복 수행 소스코드 from collections import deque def solution(n, compute..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설명 모든 경우의 수를 DFS(깊이 우선 탐색)으로 확인해서 타겟 넘버를 만드는 경우를 셌습니다. 소스코드 answer = 0 def dfs(idx, numbers, total_sum, target): global answer n = len(numbers) # 마지막 원소까지 계산했다면 return if ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 풀이 이분 탐색으로 풀 아이디어가 도저히 안 떠올라서 다른 사람의 풀이를 참조해서 풀었다. (hyeon930님 풀이) 이분탐색으로 바위를 제거하는 것이 아니라, 이분 탐색을 이용해 각 지점 사이의 거리의 최댓값을 구해야 되는 문제였다. 문제를 다시 생각해보면, "각 지점 사이의 거리의 최솟값이 x가 될 수 있는가?"를 만족하는 x들 중에 최댓값을 찾는..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 나는 처음에 차량을 진입 시점이 빠른 순서대로 정렬해서 문제를 풀었는데, 다른 사람들의 풀이를 보니 진출 시점이 빠른 순서대로 정렬 후 문제를 푸는게 더 간단했다. 진출 시점이 빠른 순서대로 차량을 정렬한다. 1) 차량의 진입 시점이 camera보다 앞에 있다면(작거나 같다면) => 차량 경로가 camera 위치에 포함되므로 추가 카메라 설치 필요 없음 2) 차량의 진입 시점이 camera보다 뒤에 있다면(크다면) => 현재 차량의 진출 시점에 다른 카메라를 설치..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 Kruskal(크루스칼) 알고리즘을 이용해서 문제를 해결했다. 섬 사이에 다리 연결에 드는 비용이 적은 순서대로 costs를 정렬한다. set[i]를 초기화해준다. set[i]는 i번째 노드의 부모 노드를 저장하는 배열이다. 부모노드란 i번째 노드와 연결된 모든 노드 중에서 인덱스가 가장 작은 노드이다. 예를 들어 노드0과 노드1이 연결되면 set[0] = 0, set[1] = 0이 저장된다. 정렬된 costs를 모두 탐색할 때까지 다음을 반복한다. - 연..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 unordered_map에 장르 이름을 key로, (장르별 재생 횟수, (노래의 고유 번호, 노래의 재생 횟수) 배열)을 value로 저장했다. 다음과 같이 문제가 주어졌을 때 genres plays return [classic, pop, classic, classic, pop] [500, 600, 150, 800, 2500] [4, 1, 3, 0] [cl..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 풀이 상의의 종류가 A, B, C 3가지일 경우 1. A를 입는다. 2. B를 입는다. 3. C를 입는다. 4. 상의를 입지 않는다. 위와 같이 4가지 경우가 있을 수 있다. 따라서 옷의 종류에 따라 (해당 종류의 옷 개수 + 1) 가지 경우의 수가 생긴다. 하지만 하루에 한 가지 이상의 옷을 꼭 착용해야 하므로 "모든 옷을 입지 않는다"라는 경우의 수를 빼줘야 한다. (answer - 1을 하는 이유) [ 의상의 종류: 해당 종류 의상의 개수 ]는 unordered_map을 이용해 저장했다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 phone_book은 string 벡터이기 때문에 {"119", "223", "11938"}을 정렬하면 {"119", "11938", "223"}이 된다. 즉, 사전 순으로 정렬된다. 따라서 phone_book을 정렬한 다음, 길이가 짧은 것부터 접두어가 가능한지 확인한다. 사전 순으로 정렬되어 있기 때문에 바로 다음 번호의 접두어가 되지 못하면, 그 뒤..