문제 설명라이언은 카카오 프렌즈와 함께 이진트리 탐색 게임을 구상했다. 주어진 2차원 좌표를 기반으로 특정 규칙에 따라 이진트리를 구성하고, 전위 순회(preorder)와 후위 순회(postorder) 결과를 반환하는 문제이다.트리 구성 규칙모든 노드는 서로 다른 x 값을 가진다.같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.부모 노드의 y 값은 자식 노드보다 크다.왼쪽 서브트리의 모든 노드의 x 값은 부모보다 작고, 오른쪽 서브트리의 모든 노드의 x 값은 부모보다 크다.제한 사항nodeinfo의 길이는 1 ≤ N ≤ 10,000nodeinfo[i] = [x, y] (각 노드의 좌표)모든 좌표 값은 0 ≤ x, y ≤ 100,000트리의 깊이는 1,000 이하해결 방법알고리즘: 이진트리 구..

문제 설명각 사람의 몸무게가 담긴 배열 people과 보트의 무게 제한 limit이 주어질 때, 모든 사람을 구출하기 위한 최소한의 보트 수를 구하는 문제입니다. 보트는 한 번에 최대 2명까지 태울 수 있으며, 그들의 몸무게 합이 limit을 초과하면 안 됩니다.제한 사항1 ≤ people.length ≤ 50,00040 ≤ people[i] ≤ 24040 ≤ limit ≤ 240구할 값: 최소한의 보트 수해결 방법알고리즘: 그리디 + 투 포인터정렬: 사람들을 몸무게 기준으로 오름차순 정렬합니다.투 포인터 활용: 가장 가벼운 사람(left)과 가장 무거운 사람(right)을 비교하며 보트에 태울 수 있는지 판단합니다.두 사람의 합이 limit 이하라면 함께 태우고 left를 증가시킵니다.limit을 초과..

문제 설명주어진 단어 begin을 target으로 변환하는 가장 짧은 과정을 찾는 문제입니다. 변환 규칙은 다음과 같습니다.한 번에 한 개의 알파벳만 변경할 수 있습니다.변경 후의 단어는 words 리스트에 포함되어 있어야 합니다.변환할 수 없는 경우에는 0을 반환합니다.제한 사항각 단어는 알파벳 소문자로만 이루어져 있습니다.모든 단어의 길이는 3 이상 10 이하이며 동일합니다.words 리스트에는 3개 이상 50개 이하의 단어가 있으며 중복이 없습니다.begin과 target은 같지 않습니다.해결 방법알고리즘: BFS (너비 우선 탐색)풀이 방법:Queue를 사용하여 BFS 탐색을 수행합니다.begin 단어를 시작점으로 큐에 추가하고, 방문 여부를 체크합니다.큐에서 단어를 꺼내며, 한 글자만 차이나는 ..

문제 설명알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 사전에 정렬되어 있습니다. 예를 들어, 첫 번째 단어는 "A", 두 번째 단어는 "AA", 마지막 단어는 "UUUUU"입니다. 주어진 단어 word가 사전에서 몇 번째 단어인지 찾는 함수를 구현해야 합니다.제한 사항word의 길이는 1 이상 5 이하입니다.word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.해결 방법알고리즘: DFS(깊이 우선 탐색)사전에 나올 수 있는 단어를 DFS를 이용해 순차적으로 생성하면서 탐색합니다.DFS를 수행하며 단어를 만들고, 카운트를 증가시킵니다.생성한 단어가 word와 일치하면 현재 카운트 값을 반환합니다.단어의 길..

문제 설명공원의 시소는 중심으로부터 2m, 3m, 4m 떨어진 좌석이 있습니다. 두 사람이 마주 보고 탔을 때, 시소가 평형을 이루려면 두 사람이 시소에 가하는 토크가 같아야 합니다. 주어진 몸무게 목록 weights에서 가능한 모든 시소 짝꿍의 쌍의 개수를 구하는 문제입니다.제한 사항2 ≤ weights의 길이 ≤ 100,000100 ≤ weights[i] ≤ 1,000몸무게는 정수해결 방법알고리즘: 해시 맵을 활용한 조합 계산몸무게 개수 저장weights 배열을 순회하며 각 몸무게의 개수를 카운트합니다.짝꿍 계산같은 몸무게를 가진 사람들끼리 짝을 이루는 경우: 조합 공식 nC2 = n * (n-1) / 2 적용서로 다른 몸무게를 가진 경우:w1:w2 = 2:3, 3:4, 2:4(=1:2) 비율이 맞는..

문제 설명자연수 x를 y로 변환하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.x에 n을 더하기x에 2를 곱하기x에 3을 곱하기최소한의 연산으로 x를 y로 만들 수 있는 횟수를 구해야 하며, 변환이 불가능한 경우 -1을 반환해야 합니다.제한 사항1 ≤ x ≤ y ≤ 1,000,0001 ≤ n 해결 방법알고리즘: BFS (너비 우선 탐색)BFS를 사용하여 x에서 y로 변환하는 최소 연산 횟수를 찾습니다.큐를 이용해 가능한 연산 결과를 탐색하며, 방문한 숫자를 기록하여 중복 탐색을 방지합니다.목표값 y를 찾으면 해당 연산 횟수를 반환하고, 모든 경우를 탐색한 후에도 찾지 못하면 -1을 반환합니다.시간 복잡도BFS는 한 노드를 한 번씩 탐색하므로 O(N)의 시간 복잡도를 가집니다.최악의 경우 y까지 ..

문제 설명고대 문명의 유물에서 발견된 덧셈과 뺄셈 수식을 분석하여, 해당 문명이 사용한 진법을 찾아야 합니다. 주어진 수식 중 일부는 결과 값이 지워져 있으며, 해당 수식들의 결괏값을 복원해야 합니다.진법은 2진법부터 9진법 사이이며, 수식들에서 사용된 숫자를 통해 사용된 진법을 유추할 수 있습니다. 결괏값이 확정적으로 결정되지 않는 경우에는 ?로 표시해야 합니다.제한 사항2 ≤ expressions의 길이 ≤ 100수식은 "A + B = C" 혹은 "A - B = C" 형태의 문자열입니다.A, B는 두 자릿수 이하의 정수이며, C는 세 자릿수 이하의 정수 또는 X(지워진 값)입니다.진법 내에서 수식이 성립하도록 보장됩니다.해결 방법알고리즘: 비트마스킹, 진법 변환가능한 진법 유추수식에 등장하는 모든 숫..

문제 설명주어진 숫자로 이루어진 문자열 t에서 p와 길이가 같은 부분 문자열을 추출하여, 이 부분 문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 경우의 개수를 구하는 문제입니다.제한 사항1 ≤ p의 길이 ≤ 18p의 길이 ≤ t의 길이 ≤ 10,000t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.해결 방법알고리즘: 브루트포스(완전 탐색)p의 길이를 변수 size로 저장합니다.t의 모든 가능한 부분 문자열(길이 size)을 순회하면서, 해당 부분 문자열이 p보다 작거나 같은 경우를 확인합니다.조건을 만족하는 경우 answer 값을 증가시키고, 최종적으로 answer를 반환합니다.구현 방법:문자열 t에서 길이 size만큼의 부분 문자열을 slice를 사용하여 추출합니다.비교 연..