본문 바로가기

Algorithm Problem

[백준] 10942 - 팰린드롬? 1. 문제 이해 수열과, 그 수열 내에서 특정 범위가 주어진다. 주어진 특정 범위의 수열이 팰린드롬인지 아닌지 확인하는 문제이다. 2. 문제 풀이 주어지는 범위는 왼쪽과 오른쪽 인덱스 총 2개이다. 이 인덱스를 이용해 DP 배열을 만든다. 팰린드롬인 범위가 있다면, 왼쪽 인덱스 + 1. 오른쪽 인덱스 -1 한 범위도 팰린드롬이 된다. 만약 팰린드롬이 아니라면, 그 안쪽 범위는 팰린드롬 일 수 있다. 즉, 범위가 주어진다면, 왼쪽 인덱스 + 1. 오른쪽 인덱스 -1 했을 때의 팰린드롬 결과가 결국 정답이 된다.. DP를 만드는 시간복잡도는 2000 * 2000 ( 왼쪽 인덱스 가능한 값, 오른쪽 인덱스 가능한 값 ) 이 되어 0.5 초 이내에 수행이 된다. 예를 들어. 수열이 1 2 3 4 5 4 3 2 .. Algorithm Problem/백준 2022. 6. 23.
[백준] 6198번 - 옥상 정원 꾸미기 1. 문제 이해 N개의 빌딩 높이가 주어졌을 때, 각 빌딩에서 볼 수 있는 다른 빌딩의 옥상의 수를 구하는 문제이다. 다른 빌딩의 옥상을 보기 위해서는, 현재 빌딩의 높이보다 낮아야 한다. 그리고, 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 옥상은 보지 못한다. 이 때, 보는 방향은 오른쪽이다. 2. 문제 풀이 주어진 N의 범위가 (1 ≤ N ≤ 80,000) 이므로, O(N^2) 만큼 걸리는 완전탐색은 시간초과이다. 그러므로, 최대한 선형시간 내에 알고리즘이 동작하도록 만들어야 한다. 보는 방향이 오른쪽이므로, 가장 오른쪽에 있는 빌딩부터 진행한다. 오른쪽에서 왼쪽으로 탐색하다 보면, 다시 오른쪽으로 갈 일은 없기 때문에 선형시간이 보장된다. 6 10 3 7 4 12 2 예제 입력을 가.. Algorithm Problem/백준 2022. 6. 21.
[백준] 1253번 - 좋다 1. 문제 이해 N개의 수 중에서 다른 수 2개의 합으로 나타낼 수 있는 수의 개수를 세야 한다. 즉, A = B + C 를 만족하는 A의 개수를 구한다. ( 단, A != B && B != C && B != C ) 2. 문제 풀이 주어진 N의 범위는 (1 ≤ N ≤ 2,000) 주어지는 수의 범위는 절댓값 10억 이하이므로, INT32 범위를 벗어나지 않는다. A = B + C 인 A를 구하기 위해, 서로 다른 B와 C를 구해야 한다. B와 C는 투포인터로 구할 수 있다. 이 때, 선행으로 정렬을 해야 한다. 그래야, Left, Right 어느 쪽을 줄이고 늘릴지 판단할 수 있다. A = B + C 일 때 B를 Left 인덱스의 수, C를 Right 인덱스의 수로 정하면 A가 표현가능한 지 구할 수 있.. Algorithm Problem/백준 2022. 6. 20.
[백준] 5582번 - 공통 부분 문자열 1. 문제 이해 입력으로 두 문자열의 주어지면, 해당 문자열의 공통된 부분 문자열의 길이를 구하는 문제이다. 2. 문제 풀이 하나의 문자열을 기준으로, 나머지 문자열을 짧게 보면서 문자열의길이를 구한다. DP로 풀기위해 문자열의 길이를 쪼개가며 계산한다. 연속된 문자열 이므로, 경우의 수는 각 문자열 길이의 곱이다. 최대 길이만 구하면 되지만, 길이가 달라지면서, 길이가 같은 일치하는 부분문자열이 여러개 생길 수 있으므로 길이를 계속 저장한다. 예제 입력 1 ABRACADABRA ECADADABRBCRDARA ABRACADABRA E 길이0 = E까지 봤을 때, 가장 긴 부분 문자열 길이 ABRACADABRA EC 길이 1 = C까지 봤을 때, 가장 긴 부분 문자열 길이 ABRACADABRA ECA 길이.. Algorithm Problem/백준 2022. 4. 2.
[백준] 1600번 - 말이 되고픈 원숭이 1. 문제 이해 2차원 배열 위에서 원숭이가 이동하는 문제이다. 원숭이는 말 처럼 이동할 수 있는데 체스의 나이트처럼 이동할 수 있다. 단, 말 처럼 이동할 수 있는 횟수는 K번이다. 그 외에는 상하좌우 로만 이동가능하다. 원숭이가 (0,0) 좌표에서 (h-1, w-1) 좌표로 이동할 떄, 최소한의 이동횟수를 구하는 문제이다. 2. 문제 풀이 말의 이동횟수를 제외하고 생각한다면 간단한 BFS 문제이다. 간단한 BFS 문제에서 한 번 방문했던 곳을 다시 방문하는 문제를 해결하기 위해, 방문 여부를 체크하는 방법을 사용한다. 특정 좌표를 이미 방문한 적이 있다면 같은 결과를 도출해 내기 때문에 다시 방문할 필요가 없다. 이 문제에서도 똑같이 방문 여부를 체크해야 한다. 그러나, 같은 결과를 도출해내는 방문만.. Algorithm Problem/백준 2022. 3. 30.
[백준] 12685번 - 평범한 배낭 https://jukyyoon.tistory.com/13 0/1 Knapsack Problem 1. Knapsack Problem, 배낭문제란? 많은 예제에서 이야기하듯이, 무게와 가치로 설명을 해본다. 어떠한 아이템이 있을 때, 그 아이템은 무게와 가치라는 두 개의 값을 갖는다. 이 때, 무게는 제약조건 jukyyoon.tistory.com 0/1 Knapsack 알고리즘과 동일한 문제이다. Algorithm Problem/백준 2022. 2. 7.
[백준] 11052번 - 카드 구매하기 1. 문제 이해 입력으로 N과 Pi가 P1부터 PN 까지 순서대로 주어진다. P의 인덱스를 i라고 하면, i의 합이 N이 되는 Pi들의 최댓값을 구하는 문제이다. 즉, 집합 P에 대한 중복조합이다. 부분집합의 합으로 정답을 구할 수 있지만 N의 최댓값이 10000이기 때문에 시간초과에 걸린다. 그래서 DP를 이용해서 풀어야 한다. 2. 문제 풀이 카드팩(N)은 N개의 카드가 들어있다. 카드팩(i)의 가격은 P(i)이다. N=4이고, Pi 가 순서대로 1 1 2 3 이 주어졌다면, 다음과 같이 풀 수 있다. N = 4 , P = { 1, 1 ,2 ,3} 카드팩 1개 구매 카드팩 1개를 구매하는 경우는 1가지이므로 P1, 즉 1이다. 카드팩 2개 구매 이 경우는 2가지 이다. P1 2개 혹은 P2 1개이다... Algorithm Problem/백준 2022. 1. 26.

티스토리툴바