투투

문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는..

문제 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다. 트리의 노드는 1부터 n까지 번호가 매겨져 있다. 입력 파일의 ..

문제 트리의 지름은 임의의 두 정점 사이의 거리 중 가장 긴 것을 말한다. 트리의 정보가 주어졌을 때 트리의 지름을 구하라 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 출력 첫째 줄에 트리의 지름을 출력한다. 접근 자료구조 트리에 대해 공부하기위해 이 문제를 풀었다. 일단 트리는 그래프와 다르게 순환하지 않는 자료구조고 어떤 노드가 루트인가에 따라 모양이 달라진다. 지금까지 ..

문제 다솜이는 고속도로를 가지고 있으며 고속도로에는 현재 N개의 휴게소가 존재한다. 휴게소의 위치는 고속도로의 시작점으로부터 얼만큼 떨어져 있는지로 주어지며 여기서 M개의 휴게소를 세우려고 한다. 이때 휴게소들의 구간별 길이 중 최댓값이 최소가 되기위한 간격을 구하라. 무조건 M개의 휴게소를 세워야하고 기존에 휴게소가 있는 위치와 끝에는 세울 수 없다. 입력 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진..

programmers.co.kr/learn/courses/30/lessons/49191# 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 접근 이 문제를 풀면서 플로이드-와샬 알고리즘을 알게되었다. 플로이드-와샬은 모든 정점에서 모든 정점으로 이동할 때의 최소비용을 구할 때 사용할 수 있다. 예를 들어, i -> j로 이동할 때의 최소비용을 구하기위해 중간노드를 거쳐서 가는 비용으로 비교를 한다. i -> k, k->j 로 이동할 때의 비용을 통해 최솟값 비교를 진행한다. 해당 개념을 이 문제에 어떻게 적용시킬 수 있을까? 5명의 사람들이 있고 2차원 리스트에 승부결과를 넣는다면 빈 공간은 아직 승부결과를 모른다는 ..

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..

programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 접근 딕셔너리를 활용해서 풀 수 있겠지만 단순히 경우의 수를 구해서 풀 수 있을 것 같았다. 하지만 경우의 수를 구할 줄 몰랐고 한번 찾아봤다. 먼저 입어야하는 옷을 카테고리 별로 구분을 했을 때, 카테고리 별 옷의 개수를 각각 곱해준다면 모든 옷을 선택해서 입을 수 있는 경우의 수가 된다. 하지만 문제에서는 하나 이상을 무조건 입어야한다고 했고 이 말은 카테고리 별로 다입지 않고 하나만 입어도 된다는 뜻이다. 이것의 경우의 수를 구한다면 카테고리 별의 옷의 개수에 +1을 해주고 모두 곱해준다. +1을 해주는 것은 옷을 입지 않았을 때의 경우를 추가한 것이다. ..

문제 N개의 집이 수직선 위에 놓여있다. 여기서 C개의 공유기를 설치하려고 한다. 한 집에 공유기를 하나만 설치하여 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하려면 얼만큼의 거리로 C개의 공유기를 놓아야하는지 구하라 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 출력 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. 접근 이분탐색으로 접근을 하였다. 공유기를 설치한 집의 거리를 D라고 할 때 C개를 설치한 집들간의 거리가 D이상이 되어야한다. 예를 들어 ..

programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근 이분탐색이 무엇인지는 알았지만 비슷한 유형의 문제만 풀어서 아직 완벽하게 이해하지 못했다. 이 문제는 고득점kit에 이분 탐색으로 분류되어 있다. 그래서 문제를 읽고 이분탐색으로 접근을 하려고했는데 도대체 어떻게 접근을 해야할지 감이 잡히지 않았다. 감이 잡히지 않은 이유 첫 번째는 이분 탐색을 완벽히 이해하지 못해서다. 왜 left와 right값을 주고 mid값을 통해 ..

programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 접근 문제에서 주어진대로 구현하는데에 중점을 두었다. 구현 먼저 num이라는 변수에 입력된 이진수를 대입한다. 그리고 while문으로 반복을 진행하게 된다. num을 탐색하면서 1이면 copy_num에 넣고 아니라면 answer의 1번 인덱스의 수를 증가시킨다. 탐색이 종료되었다면 copy_num의 길이를 다시 이진수로 변환하여 num에 대입한다. 위의 과정을 num이 1일 될 때까지 반복한다. def solution(s): answer = [0, 0] num = s while True: copy_num = '' for i in range(len(..