-내 생각 LIS알고리즘에 이은 LCS알고리즘이다. 전혀 처음 보는 유형의 문제였기 때문에 혼자 힘으로 풀지는 못했다. -해법 LCS의 경우 주의해야 할 경우가 Longest Common Subsequence인 최장 공통부분 순열이 있고, Logest Common Substring인 최장 공통부분 문자열인 경우가 있다고 한다. 순열의 경우는 현재 문제처럼 연속되는 문자는 고려하지 않고 단순히 두 문자열을 비교해서 겹치는 경우의 수를 구하는 것이다. 예를 들어 ACAYKP는 CAPCAK와 비교했을 때, A, C, P, K가 순서에 고려되지 않고 겹치게 된다. 그러나 문자열의 경우는 CA만이 순서와 내용이 일치한다는 차이점이 있다. LCS의 경우에는 2차원 배열을 이용해서 구하게 되는데 https://you..

-내 생각 이 문제를 이해할 때 주의해야 할 점이 하나 있는데, 바이 토닉 부분 수열과 바이 토닉 수열의 구분을 확실히 해야 한다. 이 문제에서 묻는 대상은 바이 토닉 부분 수열이기 때문에 문제에서 예로 든 {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이 토닉 수열이 아니라는 것이다. 처음 구현하기에 앞서 바이 토닉 부분 수열의 경우 가장 큰 값을 기준으로 왼쪽으로는 작은 값을 갖고, 오른쪽으로는 큰 값을 가지는 것을 보고 우선 가장 큰 값을 찾은 후 왼쪽부터 증가하다가 큰 값을 만나면 그 이후부터는 작은 값을 처리해 주려고 했지만, 구현에 실패해서 다른 분들의 글을 통해 도움을 받았다. -해법 우선 이 문제를 풀기 위해서는 LIS라는 개념이 완벽..

-내 생각 우선 이 문제는 LIS알고리즘이라고 하여서 무언가 알고리즘에 대한 기본적인 개념 같은 것이 있을 줄 알고 검색해봤는데, 그렇지 않고 그냥 알고리즘 문제들 중 대표적인 문제의 유형 중 하나인 것 같다. 그래서 의도치 않게 문제 해설을 봐버리게 되어서 분석해보았는데, 크게 어려운 부분은 없었다. 그러나 여기서 사용한 2중 for문의 경우는 수열의 길이가 10 이상이 돼버리면 1초에 완료할 수가 없다고 한다. 왜냐하면 2중 for문은 O(N^2)의 시간 복잡도를 가지기 때문이라고 한다. LIS를 푸는 O(NlogN) 방법이 있다고 하는데, 여기엔 이진 탐색을 사용한다고 하니 후에 글로 남겨야겠다. -해법 우선 가장 긴 증가하는 부분 수열이라는 문제에서 핵심은 일정한 숫자들이 주어질 때 첫 번째 숫자..

-내 생각 포도주 시식 문제의 경우 계단 오르기 문제와 유사한 점이 많다고 생각한다. 계단 오르기와의 공통점은 3개의 원소를 연속해서 선택할 수 없다는 점이며, 큰 차이점은 마지막 잔을 반드시 마실 필요가 없다는 것이다. 계단 오르기를 분석하고 이러한 유형의 문제를 풀 때 약간의 요령이 생기긴 했던 건지, 점화식을 첫 번째것은 잘 세웠는데, 두 번째 점화식을 고려하지 못해 오답처리를 받았다가 다른 분들의 도움으로 해결할 수 있었다. -해법 우선 점화식을 세우기 위해서 적당히 4개 정도의 포도주 잔이 있다고 가정하고 생각해 보았다. 아래가 그 표이다. 우선 특정 포도주를 먹기 위한 경우의 수를 생각해보면, N번 째 포도주를 먹거나 먹지 않거나 이므로 2가지 경우가 발생한다. 이후 만약 먹었을 경우 이전 포..

-내 생각 이번 문제 이전에 풀었던 RGB거리 문제 덕에 이러한 비용 문제, 또는 숫자의 누적 문제는 문제에서 주어진 입력과 동일하게 배열을 하나 만들어 해당하는 지점까지의 결과를 저장해 나가면서 풀면 된다는 것을 알 수 있었다. 이 문제에서 약간 혼동될 수 있는 부분이 있다고 생각하는데, 문제 부분의 글과 그림을 보면 정삼각형의 형태로 입력이 주어지는 것처럼 보이지만, 예제 입력 1을 보면 알 수 있듯이 열이 +1씩 되면서 입력이 되는 것을 알 수 있다. 그렇기 때문에 문제에서 말하는 왼쪽 대각선과 오른쪽 대각선의 의미는 사실상 배열의 개념에서 생각해 볼 때, 자신이 속한 열과 그다음 열을 의미한다는 것이다. 예를 들어, 삼각형의 2층에서 8이 선택할 수 있는 숫자는 자신이 속한 행인 1과, 그다음 열..

-내 생각 우선 피보나치수열의 개념의 이해는 쉽다. 처음에는 동적 프로그래밍 알고리즘을 사용하는 과정에서 각 결괏값을 저장하는 배열을 int형으로 선언했는데, 수 들이 기하급수적으로 커지기 때문에 long타입으로 다시 선언해 주었다. -해법 코드는 간결하다. import java.util.*; public class Main { static int n; static long check[] = new long[91]; // long형 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n= sc.nextInt(); check[0]= 0; // 0번, 1번 숫자는 미리 저장해둔다. check[1] =1; for(in..

-내 생각 단계별 풀어보기 백트래킹 분류에 있는 마지막 문제로 이 문제 역시 삼성 기출문제라고 한다. 문제 자체의 이해는 어렵지 않지만, 주의해야 할 부분이 하나 있는데, 예제 입력 2번의 경우 사람의 수는 6명이므로 3:3으로 나누어 게임을 진행한다. 이때 예를 들어 3명으로 이루어진 팀 중 한 팀의 구성원을 1번, 2번 3번을 선택했을 때 팀의 능력치는 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)의 합이 된다는 점이다. 처음에 풀 때는 예제 입력 1을 기준으로 생각하여서 고려하지 못했던 부분이다. 또한 이 문제를 풀기 위해서 어떻게 풀어야 할지 고민하는 과정에서 DFS를 어떤 방식으로 수행해야 할 지 고민이었는데, 처음 시도한 방법은 2중 반복문으로 한 명의 사람을 고정 ..

-내 생각 단계별로 풀어보기를 통해서 접한 첫 번째 기출문제였다. 스도쿠와 N-Queen 문제 때문인지 문제의 난이도는 그렇게 높다고 느껴지지 않았다. 그러나 문제를 푸는 동안 시행착오가 한 번 있었는데, 최댓값과 최솟값을 비교하기 위해서는 모든 연산자를 경우의 수에 따라 전부 대입해보아야 했는데, 처음에는 하나의 연산자를 넣어 비교하는 방식을 이용해보려 했다. 예를 들어 예제 입력 3번의 경우에서 1과 2를 각 연산자로 한 번만 계산 후 대소 비교를 생각했었는데, 힌트를 보고 틀린 생각이란 것을 알 수 있었다. 최댓값의 경우가 1과 2 사이의 연산자가 -인데, 앞선 방식으로 풀면 x일 때가 최댓값의 경우라고 가정하게 되는 것이다. 즉, 결과적으로는 모든 연산자를 각 경우의 수에 따라 대입해 최종 값을 ..

-내 생각 여태 푼 백 트래킹 알고리즘을 이용하는 문제들 중 N-QUEEN문제만큼 고민 한 문제이다. 그래도 N-Queen문제를 한 번 풀어봤던 탓인지, 어떻게 풀어야 할지 감을 잡는데 오랜 시간이 걸리지는 않았다. 이 문제까지 풀어보고 느낀 건 백 트래킹 알고리즘의 경우 별도의 체크 메서드가 반드시 필요하다는 점이다. 글에서만 봤지만 무슨 소리인지 몰랐던 '유망한 노드'를 식별하는데 필요하다고 생각한다. 즉, 조건에 해당하는 사항만 DFS로 재귀호출을 해주면 된다. 우선 스도쿠 문제의 경우 대다수의 사람들이 조건을 알 거라고 생각한다. 물론 문제에도 쓰여있다. 즉 가로, 세로, 3X3크기의 박스에 1부터 9까지의 숫자가 겹치지 않고 들어가야 한다. 여기까지만 읽으면 백 트래킹을 위한 조건을 어떻게 세워..

글을 쓰기에 앞서 블로그 개설 후 방문자 수가 늘었다. ㅎㅎㅎ 그냥 개인 기록용 블로그로 쓰고 있는 거여서 방문자 수는 별로 신경 안 쓰고 있는데, 사람들이 찾아와 준다는 게 신기했다. 물론 글이 유익했는지는 모르겠지만.. 그래도 그중에는 도움을 받아가는 분이 있다고 믿고 싶다. ㅎㅎ 문제를 보자! -내 생각 백 트래킹 알고리즘 중 가장 유명한 문제라는데 확실히 검색해보면 다른 많은 분들이 관련해서 글들을 많이 올리신 것 같다. 하지만 문제 자체는 쉽지 않다고 생각한다.. 실제로 이 문제를 풀기 위해서 3일을 소요했으니..(여러 개인 사정으로 자세히 고민해보지는 못했지만 ㅎㅎ) 우선 문제 자체는 어렵지 않다. 체스의 퀸을 활용한 문제인데, 체스의 룰에 대해서는 이전부터 알고 있었기 때문에 퀸이 상하 대각..