Algorithm
[백준(파이썬/Python)] 1167_트리의 지름
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net - 트리의 지름을 구하는 방법에 대한 약간의 사전지식(?)이 있어야 쉽게 풀 수 있는 문제입니다. - 트리의 지름을 구하는 공식은 아래 주석에서 설명한 것처럼 크게 세 단계를 거칩니다. 1. 트리에서 임의의 정점 x를 찾는다. 2. 정점 x에서 가장 먼 정점 y를 찾는다. 3. 정점 y에서 가장 먼 정점 z를 찾는다. --> 트리의 지름은 정점 y와 정점 z를 연결하는 경로다. 이..
Algorithm
[백준(파이썬/Python)] 1477_휴게소 세우기
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 우선순위 큐를 이용해 휴게소 사이 거리가 최대인 구간을 찾고, 해당 구간을 쪼개나가면서 최적해를 찾을 수 있는 문제입니다. 주의해야 할 부분은 해당 구간을 쪼갤 때 그 시점의 거리에서 절반씩 쪼개는게 아니라, 맨 처음 거리에서 N번 쪼개야 한다는 것입니다. 예를 들어, A와 B사이 거리가 맨 처음에 24였다면 이 구간을 3번 쪼갤 때, 24->12->6->3이 아니라 2..
Algorithm
[백준(파이썬/Python)] 16198_에너지 모으기
https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 문제에서 N값이 10이하로 매우 작기 때문에, 재귀 함수를 통해 모든 경우의 수에 대한 완전 탐색을 해주면 됩니다. 완전 탐색을 하기 위해서는 현재 구슬 중에서 i번째 구슬을 선택했을 때 그 구슬을 제외한 리스트에서 다시 임의의 i번째를 선택하는 식으로 진행해야 합니다. 이를 위해 반복문 안에서 재귀함수를 호출하는 형식으로 구현했습니다. 문제에서는 copy 라이브러리를 이용하였는데, pop(..
Algorithm
[프로그래머스(파이썬/Python)] 멀리 뛰기
https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 프로그래머스 Level3 문제치고 정말 쉬운 DP문제입니다. DP 문제인 정당성은 N칸을 점프하는 경우의 수가 그 이전 칸(N-1, N-2)의 경우의 수에서 더해지는 방식이기 때문에 전체 문제의 최적해가 부분 문제의 최적해를 보장한다는 점에 있죠. N번째 칸에 도착하기 위해서는 N-1번째 칸에서 1칸 점프..
Algorithm
[프로그래머스(파이썬/Python)] 배달
https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 전형적인 다익스트라 알고리즘 문제입니다. 먼저, 문제에서 임의의 두 지점 사이 가는 경로가 여러 개 주어질 수 있다고 했으므로 가장 짧은 거리만 배열에 저장하도록 처리를 해줘야 합니다. 이는 기존에 저장된 cost값과 현재 input으로 주어진 cost값을 비교하면 되겠죠? 다익스트라를 구현할 때는 우선순위 큐(Priority Queue..
Algorithm
[프로그래머스(파이썬/Python)] 순위
https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 이 문제를 해석할 때 가장 중요한 포인트는 "어떤 상황에서 순위가 결정되는가?"에 대한 이해입니다. 순위가 결정되려면 자신이 결투를 해서 이기는 사람, 지는 사람을 카운트할 때 자신을 제외한 n-1명의 정보가 모두 있어야 합니다. 따라서 results 배열로 주어진 승패 정보를 통해 먼저 각 사람이 이길 수 있는 사람 리스트를 DFS 탐색으로 만들 수 있고, 이 리스트를 바탕으로 역으로 생각해볼 때 이긴 사람의 리스트에 포함된 사람은 해당 사람에게 진 사람이 되기 때문..
Algorithm
[프로그래머스 / 파이썬(Python)] 110 옮기기
https://programmers.co.kr/learn/courses/30/lessons/77886 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 사전 순으로 앞에 오기 위해서는 "110이 무조건 111보다 앞에 있어야 한다"는 아이디어를 떠올려야 하는 문제입니다. 스택을 이용해 문자열을 순회하면서 110을 따로 추출해주고 나면, 110이 모두 제거된 후에 문자열은 연속된 1이 나타나는 지점이 없거나, 한 곳밖에 존재할 수 없습니다. 1이 연속되다가 0이 나타나면 110형태가 되어버..
Algorithm
[프로그래머스/파이썬(Python)] 모두 0으로 만들기
https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 트리구조와 DFS를 사용하는 문제입니다. 최근에 기업 코딩테스트에서 트리 문제가 자주 나오기 때문에 잘 알아두면 좋을 것 같습니다. 이 문제의 특징은 1) 어떤 정점을 잡아도 해당 정점이 루트 노드가 될 수 있다는 점, 2) 따라서 아무 정점이나 잡은 다음에 DFS를 통해 Leaf 노드까지 내려갈 수 있고, 3) Leaf 노드부터 가중치를 부모..
Algorithm
[프로그래머스/파이썬(Python] 이진 변환 반복하기
코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr - 문제에서 요구한 조건 그대로를 재귀적으로 반복해서 수행하면 되는 문제입니다. [코드] def binaryTranslate(x, tanslateCount, zeroCount): # 종료조건 x == 1 if x == '1': return tanslateCount, zeroCount # 모든 0을 제거 numOfZeroes = x.count('0') x = '1' * (len(x) -numOfZeroes) zeroCount += numOfZeroes # x는 x의 길이 c를 이진법으로 표현한 문자열 x = bin(len(x))[2:] return binaryTranslate(x, tanslateCount+1, zeroCount) de..
Algorithm
[프로그래머스] 2개 이하로 다른 비트
코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 한 개 혹은 두 개의 비트만 바꿔서 현재 숫자보다 큰 값중 최솟값을 찾는 문제입니다. 현재 숫자의 모든 비트가 1인 경우와 0이 한 개라도 존재하는 경우로 나눠서 생각하면 됩니다. 그 이유는 아래와 같습니다. 1) 모든 비트가 1이라면 이보다 큰 수를 만들기 위해서는 무조건 앞에 1비트를 붙이고, 그 다음에 1비트를 0으로 바꿔주는게 최선이겠죠. 2) 비트 중에 하나라도 0이 있다면 그 비트를 1로 바꾸는 순간 현재 숫자보다는 커지는 값이 됩니다. 따라서 되도록 작은 주소값에 있는 0비트를 1비트로 바꾸고, 만약 그 뒤로 1비트가 나타난다면 그 비트도 0으로 바꾸면 총 2개의 비트를 바꾸고 최적값을 찾을 수 있습니다. 이를 코드로..
