[2019 카카오 개발자 겨울 인턴십] 불량 사용자

💣 문제 이해 이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해야 한다. 💭 풀이 과정 먼저 banned_id 와 길이가 동일한 user_id 를 찾고, * 문자를 제외한 모든 문자가 동일하다면 같은 아이디라고 가정하고, 그 아이디의 인덱스를 저장한다. 각 banned_id 별로 가능한 user_id 후보가 한 개 이상이므로, 모든 조합의 수를 구하는 것이다. 동일한 조합의 중복이 가능하다면 곱하면 되지만, 중복을 허락하지 않으므로 체크해줘야 한다. 방법을 고민하다, 다른 풀이를 찾아보며 비트마스..

→2020.05.01

[2019 카카오 개발자 겨울 인턴십] 튜플

💣 문제 이해 특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해야 한다. 입출력 예 s result "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{20,111},{111}}" [111, 20] "{{123}}" [123] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] 💭 풀이 과정 문자열 파싱을 물어보는 문제였다. C++로 풀어보려하니 난이도에 비해 소스 길이가 짧은 편은 아니었다. 구글링하면서 파이썬으로 작성한 다른 소스코드들을 보니 그저 빛..🤘🏼..

→2020.05.01

[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임

💣 문제 이해 인형을 집어 올릴 위치에서 0이 아닌 숫자가 나올 때까지 아래 방향으로 탐색한다. 바닥에 도착하기 전에 인형을 발견하면 해당 위치를 0으로 만들고 바구니에 담는다. 만약, 이전에 바구니에 넣은 인형과 같다면, answer를 2 증가하고, 바구니의 그 인형을 제거한다. 💭 풀이 과정 작성 언어: Python3 def solution(board, moves): answer = 0 stack = [] length = len(board[0]) for j in moves: for i in range(length): if board[i][j - 1] != 0: if len(stack) != 0 and stack[-1] == board[i][j - 1]: answer += 2 stack.pop() el..

→2020.05.01

[BOJ] 백준 11055 가장 큰 증가 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 앞의 문제 11053번 가장 긴 증가하는 부분 수열 과 거의 유사하다. 동적 계획법 풀이 작성 언어: C++ #include int biggestIncreasingSeq (int arr[][1010], int size) { int sumMax = 0, l_result = 0; for (int i = 0; i < size; ++i) { for (int j = 0; j < i; ++j) { if (arr[..

→2020.04.27

[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {10, 20, 10, 30, 20, 50}인 경우 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 생각보다 풀이과정은 간단했다. 계속해서 DP 문제를 풀이하며 풀이 접근 방식 감을 잘 잡는 게 중요한 것 같다. 동적 계획법 풀이 작성 언어: C++ #include using namespace std; int longestSeqLength(int (*dpArr)[1010], int arrSize) { int max = 0, longest = 0; for (int i = 0; i < arrSize; ++i) { for (int j = 0; j..

→2020.04.24

[BOJ] 백준 9251 LCS / 동적 계획법(Dynamic-Programming)

💣 문제 이해 많이 알려진 Longest Common Sequence(LCS) 문제이다. 두 문자열이 입력으로 주어질 때, 이 두 문자열의 공통되는 부분 중 가장 긴 문자열의 길이를 출력하는 문제이다. 이 외국 유튜버의 풀이 를 참고하며 3가지 풀이로 접근해보았다. 1. 재귀 (Recursion) 2. 메모이제이션 (Memoization) 3. 동적 계획법 (Dynamic Programming) 💭 풀이 과정 1. 재귀 방식의 풀이 작성 언어: C++ #include // c 표준 입출력 #include // std::max char str1[1001], str2[1001]; int LCS_recurs(int index1, int index2){ if (str1[index1] == '\0' || str2..

→2020.03.14

[BOJ] 백준 12865 평범한 배낭 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 0-1 Knapsack Problem 과 동일한 문제이다. N 개의 물건이 입력으로 주어진다. 각 무게 W , 가치 V 를 가진다. 최대 K 무게를 가방에 넣을 수 있다고 할 때, 포함한 물건의 가치 V 합의 최대를 구해야한다. 3학년 학기 중에 풀어보았지만 가물가물해서 이 외국 유튜버의 풀이 가 상당히 유익했기에 다시 한 번 참고했다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 dp[i][j] = max(dp[i-1][j] , dp[i][j-index] + value) 의 점화식을 가진다. 1. 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 클 때는 포함하지 못하므로 이를 제외한 무게로 대체한다. 2. 가방 공간보다 이 물건의 무게..

→2020.03.12

[BOJ] 백준 11051 이항 계수 2 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 10,007로 나눈 나머지를 구하는 문제이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 nCr = n-1Cr + n-1Cr-1 식 이 성립하게 된다. 사탕 4개 중에 2개를 선택할 때 (4C2) , 어떤 한 사탕을 제외한 3개 중에 2개를 뽑는 경우 (3C2) 와 그 한 사탕을 무조건 뽑고 남은 3개 중에 1개를 더 뽑는 경우 (3C1) 를 합한 것과 같기 때문이다. 이를 그림으로 나타낸 것이 파스칼의 삼각형이다. 점화식은 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 이다. 작성 언어: C++ #include int dp[1001][1001] = {1, }; const ..

→2020.03.11

[BOJ] 백준 11057 오르막 수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 2234와 3678, 11119 와 같이 인접한 수가 같거나 오름차순을 이루는 수를 오르막 수 라고 정의한다. 2. 수는 0 으로 시작할 수 있다. 3. 입력으로 주어지는 N 자리 수에서 오르막 수의 갯수를 출력한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 로 총 10 가지이다. N = 2 인 경우 00~09, 11~19, 22~29, .... , 88~89, 99 로 총 55 가지이다. 여기서 규칙을 찾아보면 2자리 수 (ab) 에서 일의 자리 수 (b) 는 십의 자리 수 (a) 와 같거나 크다는 것을 발견할 수 있다. 즉,, 0b 의 경우 b 는 0보다 크거나 같은 경..

→2020.03.09

왜 정답을 나눈 나머지를 출력하라고 할까? - 나머지 연산

요즘 dp 문제를 풀면서 정답을 특정 값으로 나눈 나머지를 출력하라는 조건을 많이 발견했다. 다른 사람들의 풀이를 보고 블로그들을 찾아보면서 다음과 같은 성질을 활용한다는 것을 알 수 있었다. (A + B) % M = (A % M + B % M) % M 최종적으로 구한 dp 배열에 특정 값들을 합한 결과를 출력하고는 한다. 그런데 dp 배열을 구하는 과정에서 매번 그 값들의 나머지를 구해줘도 동일한 결과값이 나온다는 말이다. 실제로 그러한지 간단한 소스코드로 구현해보았다. #include #include // INT_MAX 상수 using namespace std; int mod = 1e+7;// 10^7 int main(){ long a = INT_MAX, b = INT_MAX; cout

→2020.03.06