도비LOG(跳飛錄)

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 주어지는 트리의 각 노드의 부모를 출력하여라. 풀이 BFS 방식으로 root인 1부터 시작해서 아래로 탐색해 나가면 부모들을 순서대로 만날 수 있다. 이렇게 마주치는 노드들을 parent라는 배열에 저장한다. 그러고 난 뒤 root를 제외한 부모들을 차례대로 출력해준다. # 백준 11725 트리의 부모 찾기 실버2 https://www.acmicpc.net/problem/11725 from collections import defaultdict, d..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 요약 트리를 입력 받아서 해당 트리의 지름을 구하여라. 풀이 트리의 지름은 임의의 정점에서 출발하여 최단거리로 갈 수 있는 노드를 구하고, 그 노드에서 다시 최단 거리로 갈 수 있는 노드까지의 거리가 된다. 양의 가중치가 있는 트리가 입력으로 주어지므로, 양의 가중치 그래프에서 최단거리를 탐색할 때 활용할 수 있는 다익스트라 알고리즘을 활용한다. 처음 출발하는 임의의 노드..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 $_nC_r$을 출력하라. 풀이 $$_nC_r = n! / r!(n-r)!$$ 조합의 수를 구하는 공식을 이용한다. factorial은 함수로 직접 구현해도 되고, 혹은 내장함수 math.factorial()를 사용해도 된다. # 백준 2407 조합 실버3 https://www.acmicpc.net/problem/2407 a, b = map(int, input().split()) def factorial(x): if x == 1: return 1 else: return x * factorial(x-1) de..

https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수 완성. 풀이 파이썬에서 문자열의 팰린드롬 여부는 아래의 코드를 이용해 간단하게 검증할 수 있다. 문자열을 s라고 한다면, s == s[::-1] 이때의 출력이 True라면 팰린드롬이며 그렇지 않으면 팰린드롬이 아니다. 이 코드를 활용하여 다음과 같이 문제를 해..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제 요약 '그룹 단어': 단어에 존재하는 각 문자가 연속해서 나타나는 단어. n개의 단어를 입력 받아 그룹 단어의 개수를 출력해야 함. 풀이 1. 단어가 없어질 때까지 while문을 돈다. 2. 단어의 맨 끝 부분이 뒤에서 두 번째 부분과 일치하지 않으면서, 단어에 안직 남아있다면, 동떨어진 알파벳이 있다는 뜻이다. 따라서 그룹 단어가 될 수 없다. 3. 이러한 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 모든 차량이 카메라를 한번은 만나도록 카메라를 설치한다. 이때 최소 몇 개의 카메라를 설치해야 하는가? 풀이 문제에서 시작점 혹은 도착점에 카메라를 설치해도 된다고 하였으므로, 도착점 혹은 시작점에 카메라를 설치하는 게 카메라가 다른 차도 찍게 될 가능성을 높이는 방법이다. 풀이 과정은 다음과 같다. 1. 계산의 편의를 위해 입력 배열 routes를 도착점을 기준으로 오름차순으로 정렬해..

https://school.programmers.co.kr/learn/courses/30/lessons/17687 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 문제에서 정의하는 게임 규칙에 따라서, 숫자들을 n진법으로 변환한 뒤, 튜브의 차례가 왔을 때 어떤 것을 말해야 하는지를 리턴해야 한다. 풀이 먼저 주어지는 수들을 n진법으로 변환해주는 함수 n_convertor를 선언해준다. 그리고 0부터 t*m-1까지의 수를 n진법으로 변환한 시퀀스를 만들어준다. 마지막으로 튜브가 말해야 하는 숫자만을 선별해준다. # 프로그래머스 N진수 게임 htt..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 요약 그래프가 주어지는데, 도로는 무방향, 웜홀은 방향이 있는 간선이다. 그리고 웜홀의 경우 시간(가중치)이 음수라는 특징이 있다. 그래프 정보를 입력 받아서, 한 지점에서 출발해서 다시 돌아왔을 때, 소요 시간이 음수가 되는지를 체크해서 리턴해야 한다. 풀이 가중치가 음수인 값이 주어지므로 다익스트라 알고리즘은 사용할 수 없다. 다익스트라보다는 느리지만, 이 문제에서 요구하고 ..

풀이 투포인터 방법을 이용한다. left 포인터를 고정시키고 left 포인터 뒤부터 차례대로 훑어가면서 부분합을 누적시키고, 부분합이 k에 도달하였을 때 left와 right 인덱스를 정답 후보군 배열(result)에 추가해준다. 그 뒤 result 배열을 right - left 순으로 정렬해준 뒤, 길이가 가장 짧은 부분 수열을 리턴한다. # 프로그래머스 연속된 부분 수열의 합 LV2 https://school.programmers.co.kr/learn/courses/30/lessons/178870 def solution(sequence, k): result = [] right = 0 summation = 0 for left in range(len(sequence)): while right < len(..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 풀이 다익스트라 알고리즘을 활용하였다. 이때 소요 시간인 distan..