매일매일 알고리즘 공부

백준 문제 스택으로 어렵게 풀었다. 실버5 문제인데...ㅎ 다들 for 로 풀었더라 🥲 이전에 비슷한 문제를 stack 자료구조 이용해서 풀었던 기억이 있어서 stack 이 딱 떠올랐는데... stack 2개 만들어서 풀었는데 문제를 너무 어렵게 생각했나봄... (결론 이렇게 풀면 틀림) 내 코드 (틀렸다고 뜸) Max 용 stack 을 만들어서 Max 스택에 값이 더 크면 stack 에 저장하고 size 체크하고 그렇게 풀어봄. stack push, pop, peek 하면서 더 번거롭게 풀었다. for 문에 20개 숫자 모두 집어넣고, 첫번째 숫자부터 본인보다 큰 수가 있는지 count 로 체크해서 풀자. package baekjoon; import java.io.BufferedReader; impor..

백준 문제 규칙 찾아서 바로 풀 수 있다! 쉬웠다. 정답 코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 돌 n 개 * 1개 또는 3개 가져감 * 마지막 돌 가져가면 이김 * a ,b * 게임은 a먼저 a ->b -> a -> b 순서로 이어짐. (홀/짝) * * @author Back * */ public class _9655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRead..

백준 문제 비트마스킹 문제 처음에 set 자료구조로 풀었는데, 시간 초과 오류가 나서 찾아보니 비트마스킹 유형의 문제였다. 🪄 비트마스킹은 2진수를 자료구조로 사용하는 기법이다. 🎁 비트마스킹의 장점 빠르다. 코드가 더 간결하다. 더 적은 메모리를 사용할 수 있다. int 자료형은, 4byte 를 할당받는다. 1byte = 8bit , 즉 4byte = 32bit 이다. a를 할당한다고 했을 때, a = 00000000 00000000 00000000 00000000(2) ⇒ 이를 활용해 0~31까지의 비트를 가지고 자료 구조로 사용할 수 있다! [1,2,3,4,5] → 11111 [2,3,4,5] → 11110 [1,2,5] → 10011 [2] → 00010 숫자 num 이 주어졌을 때, 1. 삽입 ..

다시 백준 시작!!!! 🥺 무려 4개월 동안 쉬었으니까 차근차근, 꾸준히 풀자 🥲🪄 규칙 찾는 건 어렵지 않았다 ! (N + 1) 과 (M + 1) 해서 구한 행과 열의 자릿수를 곱하는 것까지는 생각.... 하지만 코드로 2줄만에 구현하는 것은 생각을 못했다..... (while 을 두 번 쓸 생각함....ㅎ 주석이 내가 짠 코드...) 굳이 while 이 아닌 나눗셈으로 구해도 되는걸 왜 생각 못했을까..! 다음에 비슷한 문제는 꼭 맞춰야지 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 거리두기 수칙 * 테이블 = w 개씩 * 행 = h 행에..

생각의 방향 이전에 풀었던 1,2,3 더하기 문제에서 힌트를 얻었다. 카드를 1개 구매하는 상황부터 최대값을 구할 수 있는 경우의 수를 카운트 했다. p[1]=1 p[2]=5 p[3]=6 p[4]=7 - dp[1] : 카드가 1일 때의 최대값은 p[1] 만 가능하다. dp[1] = p[1] = 1 - dp[2] : 카드가 2일 때의 최대값을 구하는 경우의 수는 (1 * 2) , (2) 이다. dp[2] = p[2] + dp[0] = 5 + 0 = 5 (1 * 2)의 경우, dp[1] 에서 p[1] 카드 하나를 더 사면 된다. dp[2] = dp[1] + p[1] = 1 + 1 = 2 dp[2] 의 최대값은 5이다. - dp[3] : 카드가 3일 때의 최대값을 구하는 경우의 수는 (1 * 3), (2 * ..

생각의 방향 11 미만의 자연수를 1,2,3의 조합을 더해서 만들 수 있는 경우의 수를 구해야한다. 점화식을 찾는게 참 어려웠다... DP 문제를 여러개 풀면 익숙해질까! 문제를 더 작은 문제로 쪼개기 주어진 문제를 더 작은 문제로 쪼개는 것이 DP 문제를 푸는 시작이다. 해당 문제에 먼저 주어진 1, 2, 3 의 경우의 수를 찾는다. dp[0] = 0 dp[1] = (1) dp[2] = (1+1) , (2) dp[3] = (1+1+1) , (1+2) , (2+1) , (3) 위에 알고 있는 0,1,2,3의 경우의 수를 가지고 dp 문제를 풀어야한다. dp[4] 의 경우의 수를 가져와서 살펴보면, 1 + 1 + 1 +1 2 + 1 + 1 1 + 2 + 1 3 + 1 1 + 1 + 2 2 + 2 1 + 3..

생각의 방향 dp 문제라는 것을 알고 문제에 숨겨진 규칙을 찾아내려 애썼다. 이전에 (2xn 타일링) 문제는 그리지 않고 직접 경우의 수를 적어서 문제를 풀었다. 이번에는 직접 도형을 그려서 점화식을 찾으려고 했다. 그런데, 그려도 모르겠는거다... dp 문제의 핵심은 이전에 계산한 값을 저장해뒀다가 사용하는 것이 핵심인데, 이전의 값이 어떻게 쓰이는건지 잘 보이지 않았다. 계속 시도해보고 다시 생각해서 결국 아래와 같은 점화식을 도출했다. //n이 짝수인 경우 dp[i] = dp[i-1] * 2 + 1 //n이 홀수인 경우 dp[i] = dp[i-1] * 2 - 1 n이 짝수인 경우와 홀수인 경우, 이전 수열 값의 x2 + 1 값으로 원하는 답이 나오는 것을 알았다. 해당 점화식을 적용한 코드를 제출하..

생각의 방향 DP 알고리즘 개념을 처음 공부하고 스스로 푼 문제! 바텀업(Bottom-up) 방법으로 푸는데 성공했다. 가장 까다로운 점은 '점화식 찾기' 였다. 어떻게 풀어야할지 고민하다가, 일단 경우의 수를 직접 적어가며(머릿속으로 상상하고 그리며) 점화식을 도출해냈다. 🔻 메모장에 적어가며 알아낸 점화식 더보기 n=2 -> 2개 n=3 [가로] [가로] [가로] -> 1 [세로] [세로] [가로] [가로] [세로] [세로] -> 3개 (1(=dp[1])+2(=dp[2])) n=4 [][][][] [][][][] -> [가로][가로][가로][가로] (all 가로) -> 1 -> [세로][세로][세로][세로] (all 세로) -> 짝수일 때 가능 1 => 2값 dp[2] 랑 동일. (거의 /2) -> ..

DP(Dynamic Programming) 💡 DP Dynamic Programming : 동적계획법 (동적 프로그래밍) 복잡한 문제를 재귀적인 방법으로 해결하는 알고리즘 설계 기법이다. 주로 ⭐최적화 문제에 많이 사용되며, 부분 문제의 해답을 저장해서 같은 계산의 반복을 피해 계산 시간을 줄여준다. 핵심 : 이전에 계산한 값을 다음 단계에서 써 먹는다는 사실! 핵심 : 문제의 재귀적인 구조를 찾아라! DP 알고리즘은 중복된 계산을 줄인다는 점에서 굉장히 효율적인 알고리즘이다. DP의 주요 방법 탑다운(Top-down) 접근법 (메모이제이션) : 재귀를 사용하여 큰 문제에서 작은 문제로 나아가며, 각 단계의 결과를 캐시(메모리)에 저장한다. 바텀업(Bottom-Up) 접근법 (타뷸레이션) : 반복문을 사..

package quiz; import java.util.Scanner; /** * 숨바꼭질 6 * 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. * * 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. * * 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. * */ public class _17087 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.next..