백준 6 문제. 1. BOJ 22251 : 빌런 호석 - G5 Implementation + Bruteforcing 문제. 두 숫자간에 7개의 표시등 중에서 몇 개나 차이가 나는지를 미리 계산을 해둔다. 이후에 1 ~ N까지 숫자에 대해서 X와 표시등의 차이가 1개 이상 P개 이하인 숫자들을 모두 찾아보면 된다. 표시등 개수의 차이는 각각 자리 별로 비교를 해보면 되니, 총 시간복잡도는 O(NK)가 된다. 2. BOJ 16876 : 재미있는 숫자 게임 - G2 Game Theory + DP 문제. M번째 턴이 끝난 순간에 결과가 0~N이라면 cubelover, N+1 ~ 9999 이면 koosaga가 이긴게 된다. 그렇다면 M번째 턴이 짝수면 cubelover, 홀수면 koosaga의 턴일텐데, cube..

백준 3 문제. 1. BOJ 16953 : A → B - S2 BFS 문제. 각 숫자를 노드로 치환해서 BFS로 풀어줄 수 있다. 숨바꼭질 시리즈와 비슷한 문제. 다만, 숫자 범위가 매우 커질 수 있으므로 map은 필수인 것 같다. 다른 방법으로는 그냥 그리디로 B에서 A로 줄여나가는 방법도 있다 한다. (아마 2의 배수면 2로 계속 나눠주고, 끝이 1이면 1 빼고 10으로 나눠주고를 반복하는게 아닐까...?) 2. BOJ 31738 : 매우 어려운 문제 - ? Math 문제. N이 M이상이면 N!은 N * (N-1) * ... * M * ... 이렇게 계산이 되니 M의 배수가 된다. 따라서, N >= M이면 답은 항상 0이 된다. N < M이면 그냥 실제 팩토리얼을 계산하면 된다. (M의 범위가 10^..

백준 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] ..