본문 바로가기

전체 글

 (140)
[TIL] 99클럽 코테 스터디 32일차 TIL + 백준 11054 가장 긴 바이토닉 부분 수열 문제 풀이  문제 탐색하기바이토닉 수열이란 수열이 값이 증가했다가 감소하는 수열을 뜻합니다. 예제를 통해서 확인해 보자면 아래와 같습니다.{1, 5, 2, 1, 4, 3, 4, 5, 2, 1}--> 가장 긴 바이토닉 수열 {1, 2, 3, 4, 5, 2, 1} 이렇게 증가했다가 감소하는 최장 길이의 수열을 구해야합니다.바이토닉 수열을 구하기 위해서는 LIS (최장 증가 수열) 과 LDS (최장 감소 수열)을 조합해서 구할 수 있습니다.  최장 증가 수열과 최장 감소 수열의 dp 배열을 구한 뒤 해당 배열의 값을 합치면 오름차순과 내림차순이 합쳐진 수열이 완성되는데 여기서 단순히 두 수열을 합치면 원소가 1개씩 중복되기 때문에 최종 값은 -1을 해줘야합니다.  {1, 5, 2, 1, 4, 3, 4, 5, ..
[TIL] 99클럽 코테 스터디 31일차 TIL + 백준 2631 줄세우기 문제 풀이 문제 탐색하기이 문제는 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 문제이고 DP알고리즘을 활용하여 풀 수 있습니다.N명의 아이들이 임의의 순서대로 줄 서 있을 때 최장 증가 수열을 제외한 나머지 아이들을 이동시켜 주면 최소로 이동하면서 번호 순으로 아이들을 줄 세울 수 있습니다. 따라서 최장 증가 수열은 DP 배열의 최대값을 구하게 되면 최장 증가 수열의 수를 카운트 할 수 있고 그 값을 N에서 빼주게 되면 이 값이 바로 아이들을 최소로 이동시키는 수가 될 것 입니다. DP 배열의 값을 구하는 과정은 현재의 수열의 값을 기준으로 그 전 수열의 값들을 탐색하면서 자신보다 작은 값이 있을 경우 그 때의 DP 배열의 값 + 1 과 자신의 DP 배열의 값을..
[TIL] 99클럽 코테 스터디 30일차 TIL + 백준 1965 상자 넣기 문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 활용하여 풀 수 있는 문제입니다.문제 유형은 백준의 '11722 가장 긴 감소하는 부분 수열' 문제와 비슷하므로 아래의 링크에 해당 문제에 대해 정리한 게시글을 남겨두겠습니다.https://coding-babo.tistory.com/173 [TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 활용해서 풀 수 있습니다.DP 알고리즘이란 간단하게는 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘 입니다. DP 알고리즘: 이미 계산coding-babo.tistory.com DP 알고리즘을 통해 문제 풀이를 구현해 보자면 아래와 같습니다.int 배열을 선언해서 상자의..
[TIL] 99클럽 코테 스터디 29일차 TIL + 백준 9461 파도반 수열 문제 풀이 문제 탐색하기수열의 규칙을 살펴보면 첫번째, 두번째, 세번째는 다 1이고 그 뒤로부터는 자신보다 3번째 앞에 있는 수와 2번째 앞에 있는 수를 더한 값임을 알 수 있습니다.  따라서 DP 알고리즘을 활용하여 재귀함수로 이 문제를 풀 수 있습니다.DP 알고리즘에 대해서는 아래 게시글에 작성해두었습니다.https://coding-babo.tistory.com/173 [TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 활용해서 풀 수 있습니다.DP 알고리즘이란 간단하게는 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘 입니다. DP 알고리즘: 이미 계산coding-babo.tistory.com  우선 ..
[TIL] 99클럽 코테 스터디 28일차 TIL + 백준 11055 가장 큰 증가하는 부분 수열 문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 통해서 풀 수 있습니다.비슷한 유형의 문제(백준 11722 가장 긴 감소하는 부분 수열)를 앞 게시글에서 풀 수 있었습니다.  따라서 DP알고리즘의 개념에 대해서는 아래 게시글에 작성해두었습니다.https://coding-babo.tistory.com/173 [TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 활용해서 풀 수 있습니다.DP 알고리즘이란 간단하게는 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘 입니다. DP 알고리즘: 이미 계산coding-babo.tistory.com DP 알고리즘을 통해 문제 풀이를 구현해 보자면 아래와 같습니다.수열을 저..
[TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열 문제 풀이 문제 탐색하기이 문제는 DP 알고리즘을 활용해서 풀 수 있습니다.DP 알고리즘이란 간단하게는 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘 입니다. DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법이며,  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성됩니다. 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나눠서 해결작은 것부터 해결해서 점차 빌드업메모제이션 (memoization)타뷸레이션 (tabulation)일부만 계산해도 답이 나올 때모두 계산해야 답이 나올 때재귀반복문시간 복잡도 O(n)시간 복잡도 O(n) DP 알고리즘을 통해 문제 풀이를 ..
[TIL] 99클럽 코테 스터디 26일차 TIL + 백준 9655 돌 게임 문제 풀이 문제 탐색하기수가 주어지면 그 수가 3보다 클 경우 그 턴에는 돌을 3개를 가져가고 3보다 작을 경우에는 1개를 가져갑니다. 따라서 돌이 다 없어질때까지 while문을 돌면서 돌을 가져가고 그때의 차례를 계속해서 구하다보면 마지막 돌을 가져가는 사람을 구할 수 있습니다.문제 풀이import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String[] member = {"SK", "CY"}; int turn = 1; while(N..
[TIL] 99클럽 코테 스터디 25일차 TIL + 백준 2116 주사위 쌓기 문제 풀이 문제 탐색하기주사위를 쌓아올리는 데에는 아래 주사위의 윗면과 그 윗 주사위의 아랫면의 숫자가 같다는 규칙이 있습니다. 첫번째 주사위의 윗면을 정하면 규칙에 맞게 주사위를 쌓아올리고 옆면의 최대합을 구하면 되는 문제입니다.첫번째 주사위의 6개의 면의 숫자를 모두 돌면서 어떤 수가 윗면으로 위치했을 때 최대합을 구할 수 있는지 반복 탐색해야합니다.여기서 각 주사위의 맞은편의 인덱스를 저장한 op 배열을 선언해서 활용합니다. 첫번째 주사위의 윗면을 정합니다.윗면과 윗면의 맞은 편인 아랫면을 제외한 수 중에서 최대값을 구해서 따로 변수에 저장합니다.첫번째 주사위의 윗면은 두번째 주사위의 아랫면이므로 이를 통해서 옆면 중 최대값을 구할 수 있습니다.이렇게 반복하여 재귀호출을 진행하면서 첫번째 주사위의 ..

티스토리툴바