문제A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.물건을 훔칠 때 조건은 아래와 같습니다.물건 i를 훔칠 때,A도둑이 훔치면 info\[i\]\[0\]개의 A에 대한 흔적을 남깁니다.B도둑이 훔치면 info\[i\]\[1\]개의 B에 대한 흔적을 남깁니다.각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.경찰에 붙잡히는 조건은 아래와 같습니다.A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.각 물건을 훔칠 때 생기는 흔..

문제카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다.1. 하나의 노드는 하나의 시험장을 나타냅니다.2. 검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다.2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다.3. 노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.3-1. 위의 그림에서, 9번 시험장에는 10명, 4번 시험장에는 8명, 6번 시험장에는 20명의 응시자가 시험을 볼 예정입니다.4. 노드 사이의 간선은 해당 시험장이 연결되어 있음을 의미합니다.4-1. 위의 그림에서, 9번 시험장은 7번 시험장과, 7번 시험장은 6번 시험장과 연결되어 있습니다.코딩..

문제n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.예시Example 1.입력9[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]출력3Example 2.입력4출력[[1,2],[2,3],[3,4]]Example 3.입력..

문제당신은 공룡이 살아 숨쉬는, N개의 섬으로 이루어진 섬나라를 여행하게 되었다. 각 섬은 1번부터 N번까지 번호가 매겨져 있으며, 당신은 이 모든 섬을 빠짐없이 방문하려고 한다. 섬들 중 어떤 M개의 쌍에는 선후 관계가 존재한다. 섬 a에서 섬 b로 선후 관계가 존재한다면 반드시 a번 섬을 먼저 방문한 뒤에 섬 b를 방문해야 한다. 각 섬에는 0, 1로 표시되는 두 종류 중 하나의 자외선 위험이 있다. 자외선으로부터 몸을 보호하기 위해 당신은 방호복을 입어야 한다. 같은 종류의 자외선 위험이 있는 섬을 연속으로 방문하는 경우에는 방호복을 갈아 입을 필요가 없지만, 한 종류의 자외선 위험이 있는 섬을 방문한 직후에 다른 종류의 자외선 위험이 있는 섬을 방문하려면 방호복을 갈아 입어야 한다. 처음 방호복을..

문제N개의 항을 가진 수열 A가 있다. 각 항에 11을 더하거나 빼는 연산을 수행할 수 있다. 단, 이 연산은 항 하나에 최대 한 번만 적용 가능하다. 즉, A의 i번째 항의 값이 초기에 x로 주어졌다면, 최종적으로 i번째 항의 값은 연산을 수행하지 않은 경우에는 x, 연산을 수행한 경우에는 x+1 혹은 x−1중 하나가 가능하다. 최소한의 연산으로 수열 A가 공차 1인 등차수열이 되도록 만드는 프로그램을 작성하라. 여기서 공차 1인 등차수열이라 함은, 1 ≤ i N인 모든 정수 i에 대해, i+1번째 항 A_{i+1​}에서 i번째 항 A_i​를 뺀 값이 A_{i+1}−A_i=1임을 뜻한다.예시Example 1.입력5 1 3 4 5 5출력2조건첫 줄에 수열의 길이를 나타내는 정수 N이 주어진다. (1≤N≤..

문제Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.Implement the MinStack class:MinStack() initializes the stack object.void push(int val) pushes the element val onto the stack.void pop() removes the element on the top of the stack.int top() gets the top element of the stack.int getMin() retrieves the minimum element in the stack.You must implement..

문제Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.Implement the LRUCache class:LRUCache(int capacity) Initialize the LRU cache with positive size capacity.int get(int key) Return the value of the key if the key exists, otherwise return -1.void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the ..

정규표현식은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어입니다. 가령, 'E'로 시작하는 단어를 찾거나, 숫자를 제외한 모든 문자열을 찾아내는 등의 경우에 사용됩니다. 아래는 정규표현식을 작성하는 문법에 대해 정리한 표입니다.POSIX 표준기호뜻예시표현가능한 문자열.임의의 한 문자a.baab, abb, acb, ...*임의의 문자열a*bab, aab, aaab, abcb, ...^처음^abc.abca, abcb, abcc, ...$끝.abc$aabc, babc, cabc, ...( )하위식a(bb|cc)dabbd, accd{ }좌측의 문자가 반복a{3}baaab{m,}좌측의 문자가 m회 이상 반복a{3,}baaab, aaaab, ...{m, n}좌측의 문자가 m회 이상, n회 이하..