Node 선언 class Node(object) : def __init__(self,data): self.data = data self.count = 0 self.child = {} Node 선언 클래스를 만들어준다. Node는 각각 data, count, child를 가지고 있다. data : 현재 노드가 어떤 문자를 가지는지를 보여준다. Node('a')라고 선언할 경우, 자동으로 초기화하는데 이 때 data에는 'a'가 들어가게 된다. count : 현재 노드를 지나간 문자열이 몇개인지 알려주는 변수. 해당 노드를 지나가는 문자열이 하나씩 생길 때 마다, count를 증가시킨다. child : 현재 노드의 자식노드를 나타낸다. 딕셔너리 형태로 선언하고, 딕셔너리의 key는 data명이, value에..
세그먼트 트리는 무엇인가? 세그먼트 트리는 완전이진트리를 기반으로 주워진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조입니다. 제가 이 자료구조를 사용해서 문제를 풀었을 때는 대부분 어떤 범위 내에서 어떤 값을 찾아야 할 때 사용을 했는데, 완전탐색을 할 경우 시간초과가 발생하여, O(N^2)에서 O(logn)수준으로 시간복잡도를 줄여야 할 때 주로 사용하게 되었습니다. 세그먼트 트리는 기본적으로 각 노드가 특정 구간에 대한 정보를 가지고 있는 자료구조입니다. 정보는 '특정 구간'내의 어떤 것이든 될 수 있으며, 최소값, 최대값, 구간합, 혹은 최소값의 위치 정보, 정렬 상태 등이 될 수 있습니다. 아래 그림은 세그먼트 트리를 직접 그려본 그림입니다. 노드 위에 있는 N은 'Node'를 뜻하는 알파벳이며..
문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다. 상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모..
문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이..
문제 설명 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝..