👾

문제 링크: 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을 정렬한 다음, 길이가 짧은 것부터 접두어가 가능한지 확인한다. 사전 순으로 정렬되어 있기 때문에 바로 다음 번호의 접두어가 되지 못하면, 그 뒤..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 풀이 간단히 participant와 completion 벡터를 정렬한 뒤 비교해서 완주 목록에 이름이 없는 선수를 반환하도록 했다. 정렬해서 마지막에 있는 선수가 완주하지 못한 선수일 경우 for문을 그냥 빠져나오게 되므로 answer를 participant.back()으로 초기화해줬다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12..

문제링크: programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 people을 가벼운 사람 -> 무거운 사람 순서대로 정렬한 뒤, 보트에 탈 수 있는 (가장 가벼운 사람, 가장 무거운 사람)의 조합을 찾았다. 남아있는 사람들 중 가장 가벼운 사람과도 함께 보트에 타지 못하면 그 사람은 무조건 혼자 보트에 타야 된다. light: 남아있는 사람들 중 가장 가벼운 사람 heavy: 남아있는 사람들 중..