백준 13 문제. 1. BOJ 17219 : 비밀번호 찾기 - S4 Hash map 문제. 그냥 Hash map에 주소값을 key로, 비밀번호를 value로 저장한 다음 각 쿼리별로 대답해주면 된다. 2. BOJ 28705 : RLE Inversion Counting - P3 Math(Combinatorics) + Segment Tree + Value Compression 문제. 일단 값의 범위가 매우 크므로 값 압축은 당연히 필요하다. 그리고 지금 K번 이어붙이는 수열이 아닌 전에 이어붙인 수열과에서는 그냥 각 element 별로 inversion counting 결과값이 m_i이라면 m_i * K로 전부 더해주면 된다. 이는 Segment Tree로 가능하다. 그런데 이제 문제는 K번 이어붙이는 같은..

백준 5 문제. 1. BOJ 19587 : 객실 배치 - G1 DP + Exponential by Squaring 문제. DP[n]을 n층 건물을 채우는 방법의 수라고 식을 두면, DP[n] = 2 * DP[n-1] + DP[n-2] 이런 점화식이 나온다. 저 점화식은 사실 DP[1] ... DP[5] 까지 경우의 수를 그리면서 알게 된거긴 하지만, 점화식을 설명해보자면... n층 건물은 n-1층의 건물에서 한 층 더 쌓아올린 거라고 생각해도 된다. 그래서 우리가 생각해야할 경우의 수는... - n-1층까지 쌓아올린 후에 n층에 아무도 살지 않는 경우의 수 = DP[n-1] - n-1층까지 쌓아올린 후, n-1층 오른쪽에 아무도 안 사는 경우의 수 = DP[n-1] - n-1층 오른쪽에 사는 사람이 있는..

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 조건을 읽어봅시다. 1. 음식들의 스코빌 지수가 주어집니다. 2. 스코빌 지수가 제일 낮은 두 음식을 섞어서 스코빌 지수가 더 높은 음식 하나를 만들어 낼 수 있습니다. 3. 문제에서는 모든 음식의 스코빌 지수가 K 이상이 될려면 최소 몇 번 음식을 섞어야 하는지를 물어봅니다. 과거 2021년 7월, 제가 입대하기 전에 풀었던 문제입니다. 그냥 필 받아서 다시 풀어보..

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=cpp 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 조건을 보면 다음과 같습니다. 1. 효진이는 한 번에 한 칸 혹은 두 칸을 갈 수 있습니다. 2. 그렇다면 효진이가 0번째 칸에서 시작해 n번째 칸까지 간다면 몇 가지의 방법으로 갈 수 있는지를 출력해야 합니다. 이 문제를 읽어보자마자 예전에 백준에서 풀었던 숨바꼭질 시리즈, 1로 만들기 문제들이 생각이 났습니다. 사실 이 문제는 DP로 풀 수 있습니다. 일단 DP[k] ..

https://school.programmers.co.kr/learn/courses/30/lessons/60057?language=cpp# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 조건을 해석해보면 다음과 같습니다. 1. 길이가 1000 이내의 문자열이 주어집니다. 2. 우리가 구하고자 하는 건 문자열을 제일 짧게 압축했을 시에 길이를 구하고자 합니다. 문자열을 압축하는 방법은 아래와 같은 절차를 따릅니다. 2-1. 임의의 k를 골라 고정하고, 앞에서부터 k개의 문자씩 자릅니다. k개의 문자 단위를 "구간"이라고 합시다. 2-2. 자른 이후에..

백준 12 문제. 1. BOJ 25416 : 빠른 숫자 탐색 - S2 BFS 문제. 그냥 시작점에서 BFS를 돌려서 모든 칸의 최단거리를 보고, 나중에 모든 칸을 보면서 그 중 1이면 최단거리가 얼마인지를 보면 된다. 크기가 5 * 5 고정이라 최단거리 초기화를 대강 30 정도로만 해도 된다. (최대 25칸이나 지나야 최단거리라서... 사실 25칸도 무리라고 생각한다.) N = 5라고 하면 시간복잡도는 O(N^2)인데... N이 너무 작아서 사실상 O(1) 같은 느낌으로 풀린다. 2. BOJ 2417 : 정수 제곱근 - S4 Binary Search 문제. 그냥 mid * mid >= N 인지로 Binary Search 돌리면 되는 문제. 그런데, N의 범위가 매우 커서 l,r 범위를 잘 설정해야한다. ..