EQ1의 짱무말 갓잔치 EQ1의 짱무말 갓잔치

스마일게이트 온라인 게임잼이 4월 17일부터 4월 19일까지 진행됐다. 대상은 개발 멤버십을 참여했던 사람들 대상으로 나는 SGM 개발 멤버십 9기에 [Epic Monad]로 참여했었기 때문에 자격이 주어졌다. 원래 이맘때쯤 한 번 씩 스마게에서 게임잼을 한다는 것을 알고 있었고 회사가 사당 근처에 있었을 때도 한 번 게임잼에 참여했었다. 하지만 이번 게임잼이 특별했던 이유는 온라인 게임잼이었기 때문이다. 유튜브 라이브 스트리밍으로 진행하고 디스코드로 방을 파서 대화하고 비캔버스로 서로의 기획을 확인하는 완벽히 사회적 거리두기를 실천한 게임잼이라고 할 수 있다! 온라인 게임잼을 해본 장단점을 간단하게 집고 넘어가면 장점 단점 침대에서 꿀잠 가능 원활하지 못한 의사소통 익숙한 공간에서 익숙한 기기로 작업 ..

LCS를 한 번이라도 풀어봤다면 어려운 문제는 아니다. 단지 3차원 배열을 사용해야 하기 때문에 시각적으로 표현하기가 어려울 뿐..! 더 자세한 풀이는 아쉽게도 내 블로그에 적어놓은 글 중에는 LCS 관련 풀이가 없어서 그나마 비슷한 공통부분문자열(https://stillchobo.tistory.com/92)을 참고하면 좋을 것 같다. 아래 풀이는 공통부분문자열의 풀이에서 발전된 형태다. 복잡할 것 없이 dp의 값이 증가하는 경우는 단 하나 밖에 없다. 문자가 같을 때! 이때 dp의 값은 1 증가하게 된다. 다시 한 번 말하지만 dp의 값이 변화하는 때는 이 때 뿐이다. dp[i][j][k] = dp[i-1][j-1][k-1] + 1 이제 그 외의 경우(문자가 같지 않을 때)를 처리해주면 된다. 공통부분..

dp문제로 분류되어있긴 하지만 dp가 메인이 아니고 수열의 갯수를 구하기 위해서 사용되는 곁가지 느낌이었다. 이문제를 위한 기본적인 수학적 지식은 고등학교 경우의 수에서 배우는 '같은 것이 포함된 순열(Permutation)'이다. a라는 문자 m개와 z라는 문자 n개로 만들 수 있는 문자열의 경우의 수 각 문자는 최대 100개까지 존재할 수 있으니 dp는 이때 이 경우의 수를 저장하고 계산하는데 사용된다. 직접 팩토리얼을 재귀로 구현해서 구하면 당연하지만 시간초과가 발생한다. 메인 로직은 하나하나 세나가는 것이 아니라 앞에서부터 문자를 확정시키면서 건너뛰어야 한다. a가 3개, z가 3개인 상황에서 예를 들어보면 다음과 같다. n=3, m=3인 상황에서 k=6이라고 해보자. 첫번째 문자열이 a로 시작하..

중고등학교 때 엄청나게 많이 공부했던 잘 알고 있는 수학적 지식이였기에 쉽게 풀었다. 파스칼의 삼각형을 이용하면 된다. bico는 binomial coefficient(이항 계수)의 약자이다. 일반적인 파스칼의 삼각형 모양에 따르면 이항계수는 자신의 왼쪽 위와 오른쪽 위의 항을 합하면 된다. 또한 제일 가장자리의 값, 즉 j가 0이거나 j와 i가 같을 경우는 항상 1이다. 따라서 3가지 경우로 나눠서 bico[i][j]를 계산하면 된다. j == 0 일 경우 bico[i][j] = 1 j == i 일 경우 bico[i][j] = 1 그 외의 경우 bico[i][j] = bico[i-1][j-1] + bico[i-1][j] #include using namespace std; int n, k; int bi..

뭔가 DP는 풀어도 풀어도 매번 어려운 느낌이다. 분명 풀이 방식은 거의 정해져 있고 대부분 비슷한데 왜 '아 쉽네~'하면서 풀리지를 않는지... 이번 문제도 역시 정석적인 DP 풀이다. 다만 원래라면 i번째 앱까지 봤을 때 j만큼의 메모리를 확보했을 때 최소 cost를 저장하는 2차원 배열을 만들었어야 할 것 같지만 문제는 확보해야 할 메모리의 범위가 천만일 수도 있다는 점이다! 앱의 최대 개수가 100이니까 이대로 이차원 배열을 만들면 10억 크기의 배열을 만들어야 한다..! 이건 아니다... 싶어서 어떻게 할까 고민을 열심히 하다가 찾아낸 방법이 최대 코스트가 1만이라는 사실을 알았다. 앱의 최대 개수가 100이고 앱 하나의 최대 코스트가 100이니까 최악의 경우라도 코스트는 100 * 100을 넘..

생각보다 그냥 간단하게 생각하면 풀리는 DP였다. dp[i][j]란 첫번째 string의 i번째 글자까지와 두번째 string의 j번째 글자까지 비교했을 때 마지막 글자가 포함된 제일 긴 공통 부분 문자열의 길이다. 좀 더 구체적인 예를 들어보자면 다음과 같다. 첫번째 문자열이 ABRACA이고 두번째 문자열이 ECADADABR이라면 dp[2][3]이란 AB와 ECA를 비교했을 때 각 문자열의 마지막 문자인 B와 A가 포함된 최장 공통 부분 문자열의 길이란 뜻이다. 하지만 이 경우 B와 A가 동일하지 않으니 0이다. dp[3][9]의 경우 ABR과 ECADADABR를 비교했을 때 각 문자열의 마지막 문자인 R과 R이 포함된 최장 공통 부분 문자열의 길이란 뜻이다. 이 경우 최장 공통 부분 문자열은 ABR로..

정말 오랜만에 써보는 queue다. 맨날 DP문제 할 때 DFS밖에 안썼는데 갑자기 queue를 쓰려고 하니까 q.pop()이 queue에서 빼내면서 return해주는 건줄 알고 있었다.... 아마 제일 최근에 queue를 썼을 때가 파이썬이여서 그렇게 기억하고 있었나보다...ㅋㅋ 인터넷에 있는 풀이는 몇가지가 있는데 나는 brute force는 괜히 복잡하고 맘에 안들어서 queue를 사용하는 방식을 택했다. 그래도 코드가 좀 더러워서 맘에 안들긴 하지만...ㅋㅋㅋ 기본 개념은 이거다. 85는 감소하는 수다. 85뒤에 5보다 작은 수를 붙이면 그 수 역시 감소하는 수다. 854, 853, 852, 851, 850과 같이 말이다. 그래서 queue에 한자리수짜리 감소하는 수를 모두 넣어둔다. (사실 한자..

비트마스크를 공부해볼까 하고 풀어본 문제인데 비트마스크가 뭔지는 모르고 결국 DFS로 푼 문제다... 흠... 풀이 방법은 보통 DFS랑 동일하다. s[i][j] i번째 선수가 j라는 포지션에서의 점수 visited[j] j번째 포지션이 이미 점유되었는지 dfs(index, score) 현재 index 번호의 선수를 탐색하려 하고 있고 그 전까지 저장된 점수는 score이다. dfs 종료 조건 index == 11 선수 번호가 0번부터 10번까지이므로 11번이면 점수를 저장하고 종료 pos자리에 현재 탐색하고 있는 index번의 선수를 채용할 수도 있고 아닐수도 있으므로 두 경우를 모두 탐색해주어야 한다. visited[pos] = true;와 dfs(index + 1, score + s[index][p..