CS/Algorithm
[백준(파이썬/Python)] 2638_치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제의 핵심은 내부 치즈인가 아닌가를 어떤 방식으로 판단할 것인가입니다. 처음 문제에 접근했을 때는"모든 지점에 대하여 내부 치즈인가를 BFS 탐색을 하였고, 만약 가장자리에 도착할 수 있으면 내부 치즈가 아니다"라고 생각했습니다. 하지만 그렇게 되면 모든 위치마다 일일이 체크를 해줘야 하기 때문에, 시간복잡도에서 불리할 수밖에 없습니다. 이를 해결하기 위해서는 반대로 "가장 자리..
CS/Algorithm
[백준(파이썬/Python)] 2096_내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 풀이 자체는 어렵지 않은데 문제의 메모리 제한이 상당히 타이트합니다. - 현재 계단에서 점수의 최대, 최소는 그 전 계단까지의 최대 최소에만 영향을 받기 때문에 모든 계단의 점수값을 미리 배열로 만들어두면 메모리 초과가 발생합니다. - 따라서, 계속해서 각 시점에서 인풋값을 읽고 최적해를 갱신해나가는 방향으로 문제를 풀어야합니다. 문제 풀이의 DP 로직은 첫번째, 두번째, 세번째 계단에 있을 때를 따로 생각..
CS/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]로 팰린드롬을 확인할 수 있다는 ..
CS/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개..
CS/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을 배치한다고..
CS/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를 연결하는 경로다. 이..
CS/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..
CS/Algorithm
[백준(파이썬/Python)] 16198_에너지 모으기
https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 문제에서 N값이 10이하로 매우 작기 때문에, 재귀 함수를 통해 모든 경우의 수에 대한 완전 탐색을 해주면 됩니다. 완전 탐색을 하기 위해서는 현재 구슬 중에서 i번째 구슬을 선택했을 때 그 구슬을 제외한 리스트에서 다시 임의의 i번째를 선택하는 식으로 진행해야 합니다. 이를 위해 반복문 안에서 재귀함수를 호출하는 형식으로 구현했습니다. 문제에서는 copy 라이브러리를 이용하였는데, pop(..
CS/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칸 점프..
CS/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..
