트리 및 그래프 데이터 구조는 모두 데이터를 계층적 방식으로 구성하는 방법이다. 그러나 이들은 다른 유형의 문제에 적합한 몇 가지 주요 차이점을 가지고 있다. 트리(Tree) 트리는 부모-자녀 관계로 배열된 노드로 구성된 계층적 데이터 구조다. 각 노드에는 상위 노드가 없는 루트 노드를 제외하고 단일 상위 노드가 있다. 자식 노드는 방향 에지(Edge)를 통해 부모에 연결된다. 트리 구조는 종종 파일 시스템이나 패밀리 트리와 같은 계층적 관계를 나타내는 데 사용된다. 다음은 파이썬으로 작성한 트리 구조의 예다. class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None root = TreeNode(1)..

이진 검색 및 선형 검색은 요소 목록에서 특정 요소를 검색하는 데 사용되는 두 가지 알고리즘이다. 둘 다 동일한 목적을 수행하지만 서로 다른 상황에 더 적합하게 만드는 몇 가지 주요 차이점이 있다. 이진 검색 (Binary search) 이진 검색은 정렬된 요소 목록에서 특정 요소를 검색하는 데 사용되는 알고리즘이다. 원하는 요소를 찾을 때까지 반복적으로 목록을 반으로 나누는 방식으로 작동한다. 다음은 코드에서 이진 검색을 구현하는 방법의 예다. def binary_search(arr, x): low = 0 high = len(arr) - 1 while low

시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 분석하는 데 사용되는 컴퓨터 과학의 두 가지 중요한 개념이다. 시간 복잡도 시간 복잡도는 알고리즘이 작업을 완료하는 데 걸리는 시간을 나타낸다. 일반적으로 우리는 시간 복잡도가 낮기를 원한다. 이는 알고리즘이 더 빠르고 효율적으로 실행된다는 것을 의미하기 때문이다. 알고리즘의 시간 복잡도를 측정하는 방법에는 여러 가지가 있지만 가장 일반적인 방법은 "big O" 표기법을 사용하는 것이다. 이 표기법은 알고리즘의 시간 복잡도에 대한 최악의 시나리오를 설명한다. 즉, 알고리즘이 작업을 완료하는 데 걸리는 최대 시간을 의미한다. 예를 들어, 시간 복잡도가 O(n)인 알고리즘은 입력 크기(n)가 증가함에 따라 실행하는 데 더 오랜 시간이 걸리는 반면, 시간 복잡도..

문제 설명 다트 게임 카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~ 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다. 옵션으로 스타상(*) ,..

문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4..

문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도..

문제 설명 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다. 명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때..