백준 1 문제. 1. BOJ 14450 : Hoof, Paper, Scissors (Gold) - G3 DP 문제. DP 테이블을 dp[몇 번 손을 바뀌었는가][현재 낸 손 상태][몇 번째 소까지 상대 한 상태] 이런식으로 구상하고 테이블에 해당 상태에서 최대 이기는 횟수를 저장하도록 구성했다. 그렇게 DP 테이블을 구상하고 점화식을 세워보면 아래와 같은 경우들이 나온다. dp[k][i][j] = max( dp[k][i][j-1], dp[k-1][0][j-1], dp[k-1][1][j-1], dp[k-1][2][j-1] ) + (현재 낸 손이 j번째 소를 이길 수 있으면 1, 아니면 0) // 각각 대충 설명하자면, 손 상태를 안 바꿀 때, 손 상태를 바꿀 때 이렇게 생각할 수 있다. 까먹고 계속 안 올..

Google I/O가 열리기 전날에 OpenAI에서 Spring Update를 발표한다는 소식을 들었습니다.이에 저도 AI에 대해 관심이 있는지라 라이브 영상을 보고 정리해보았습니다.제가 이해한 내용들은 다음과 같습니다. 1. Desktop version of ChatGPT + WebUI update ChatGPT를 데스크톱 어플리케이션으로도 만들었다고 합니다.또한, 웹에서는 ChatGPT에 대한 경험에 좀 더 몰두할 수 있게 UI 개선이 이루어졌다고 합니다. 2. GPT-4o 라는 새로운 모델을 공개했습니다. 그리고 무료로 열린다고 합니다. 사실상 이번 발표에 핵심 주제입니다. GPT-4o라는 모델을 새로 공개했는데 특징들은 다음과 같습니다. Omnimodel이라는 말에 맞게 Voice + Text +..

너무 뻔한 이야기 일 수도 있지만, 올해 들어서 이해했기에 글로 남겨봅니다. PS를 꾸준히 풀다가 보면, 히스토그램이라는 문제를 한 번쯤은 들어봤을 수 있습니다. 플레 5 기준으로 사실상 제일 많이 풀린 문제이기도 하고 종만북, 바킹독 문제 모음집 등에서도 볼 수 있는 만큼 매우 유명한 문제이며 풀이도 여러 방법이 있습니다.  분할 정복, 세그먼트 트리 등등의 여러 방법도 있지만 그래도 제일 유명한 풀이는 스택 풀이입니다. Monotone Stack 테크닉을 통해서 스택에 필요한 정보들만 남겨서 푸는 방법인데, 이렇게 풀면 O(N)으로 풀 수 있다고 알려져 있습니다. 그런데, 저는 이 문제를 풀면서 왜 이게 O(N)인지가 궁금했습니다. 일단 제 구현 상에서 핵심 아이디어 코드만 따서 보면 이렇게 됩니다...

백준 4 문제. 1. BOJ 1256 : 사전 - G2DP + Combinatorics 문제. 가능한 모든 문자열의 개수는 N+M C M 이 된다. 그러면 현재까지 i개의 a와 j개의 z를 사용했다면 가능한 나머지 문자열들의 개수는 N+M-i-j C M-j가 된다. 이를 활용한다면 현재 자리에 a를 박았을 때 가능한 나머지 문자열들의 개수가 K 미만이라면 z를 꼭 사용하도록 구현해서 풀면 된다. 따라서, 모든 이항 계수를 DP 테이블로써 미리 계산을 해두고 현재까지 i개의 a와 j개의 z를 사용한 상태에서 a를 하나 더 박을 시 즉, N+M-i-j-1 C M-j가 K 미만이라면 z를 사용, 아니라면 a를 사용해서 정답을 채워 나가면 된다. 이렇게 말로만 표현하니깐 뭔가 애매한듯... 그래도 G2 DP를 ..

백준 5문제. 1. BOJ 31713 : Double Up - S4 Math + Ad hoc + Hash map 문제. a가 홀수라면, 2^k * a 형태로 나타낼 수 있는 모든 수들끼리는 같은 수로 만들 수가 있다.이를 활용해서 모든 수를 2로 나눌 수 있을 만큼 나눈다음 같은 수들끼리 묶어보면 가장 많이 등장하는 수의 최대 등장 횟수를 알 수 있다. 2. BOJ 3644 : 그래프 매칭 - G3DP 문제. n = 3, 4, 5, 6일 때의 경우의 수를 보니 C_n = C_n-1 + C_n-2로 피보나치 점화식 형태로 표현됨을 파악했다.그래서 그대로 대입해보니 정답이 나왔다;;; 나중에 알아보니 이렇게 초항이 0,1이 아닌 수에서 피보나치 점화식 형태로 표현되는 수열을 뤼카 수열이라고 한다 하더라. 문..

백준 4 문제. 1. BOJ 20052 : 괄호 문자열 ? - P4 Prefix Sum + Segment Tree 문제. '('를 +1, ')'를 -1로 치환해서 푸는 문제인데, 옳은 문자열이라면 저렇게 치환했을 때의 총합은 0이어야 한다. 또한, 중간에 누적합의 결과가 음수가 나온다면 ')'의 개수가 더 많아지는 경우가 생기므로 옳은 문자열이 될 수 없다. 따라서, Prefix Sum을 미리 구하고 이에 대해서 Segment Tree를 생성하면 Min query로 중간 누적합 결과가 음수가 나오는지 판별도 쉽게 가능하다. Prefix Sum을 이미 구했으니 총합이 0이 되는지의 여부도 쉽게 파악이 가능하다. 오랜만에 풀어본 세그 문제. 2. BOJ 26093 : 고양이 목에 리본 달기 - G3 DP 문..