문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.출력첫째 줄부..
최단 거리 알고리즘: 다익스트라 알고리즘다익스트라(Dijkstra) 알고리즘은 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. 그리디 알고리즘(탐욕법)에 기반하며, 매 단계마다 가장 비용이 적은 노드를 선택하여 과정을 반복한다. 다익스트라 알고리즘은 최단 거리 정보를 1차원 리스트에 저장하고 계속 갱신하여 최종 결과를 도출한다.다익스트라 알고리즘의 기본 동작 원리출발 노드를 설정한다.최단 거리 테이블을 초기화한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.3, 4 과정을 반복한다.1. 간단한 다익스트라 알고리즘간단한 다익스트라 알고리즘은 매 단계마다 방문하지 않은..
Python의 defaultdict는 기본값을 자동으로 생성하는 딕셔너리로, 단순한 문제 해결뿐만 아니라 코딩 테스트에서도 매우 유용하게 사용된다. 이번 글에서는 defaultdict의 심화된 활용 방법과 코딩 테스트에서 어떤 상황에서 활용하면 좋은지 중점적으로 다룬다.1. 기본 개념 복습defaultdict는 Python의 collections 모듈에서 제공하며, 기본값 생성 함수를 설정하여 키가 존재하지 않을 때 자동으로 기본값을 생성한다. 이는 KeyError를 방지하고 코드의 가독성을 높이는 데 도움을 준다.기본 사용법from collections import defaultdictd = defaultdict(int)d['a'] += 1 # 키 'a'가 없으면 0으로 초기화한 후 1을 더함prin..
문제 설명[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조..
문제1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.1234567891011121314151617181920212223...이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.출력첫째 줄에 새로운 수의 자릿수를 출력한다. 문제풀이본 문제는 수학적으로 해결하는 문제이다.각 숫자의 자릿수를 계산해서 기록하는 문제이며, 시간이 매우 짧기 때문에자릿수를 계산할 수 있는 방법을 기록해야 한다. start 변수를 통해 현재의 자릿수 계산을 시작한다.end 변수로 현재 자릿수 범위의 끝 값을 계산한다.end=min(start×10−1,N) 예를 들어서, 13이 N이라면,처음에는 ..
문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.입력첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다...