Algorithm
[프로그래머스(파이썬/Python)] 가장 긴 팰린드롬
https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 아래 코드에서 설명한 두 개의 주석이 핵심입니다. 1. 팰린드롬 문자열인지 확인할 때는 포인터 두 개를 두고(투 포인터) 왼쪽 끝과 오른쪽 끝이 일치하는지 확인하면 됩니다. left < right까지 문자열이 일치한다면 팰린드롬이죠(스터디를 하다가 str == str[::-1]로 팰린드롬을 확인할 수 있다는 ..
Algorithm
[백준(파이썬/Python)] 1967_트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 백준 1167번 트리의 지름 문제와 완벽하게 동일해서 해당 문제에 대한 풀이를 참고하면 될 것 같습니다. [백준(파이썬/Python)] 1167_트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개..
Algorithm
[백준(파이썬/Python)] 1256_사전
https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net - 고민을 정말 많이 한 문제입니다. 이틀정도 고민을 하다가 카테고리를 봤고 DP 카테고리인 것을 알았지만 이 문제에서 DP를 어떻게 적용하나싶었고... 결국 원래 생각하던 방식으로 문제를 해결했습니다. - 문제를 푸는 아이디어는 아래와 같습니다. 1) 0과 1이 각각 3개씩 존재한다고 생각해보면, 사전에서 가장 앞에 오는 경우는 000111입니다. 그리고 사전에 가장 마지막에 오는 문자는 111000입니다. 2) 만약 맨 앞에 0을 배치한다고..
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형태가 되어버..
