트리

이번 포스팅에서는 킥스타트 2020 Round D에 대한 문제 풀이를 공유하고자 한다. 1. Record Breaker 배열을 반복하면서 조건문을 통해 카운팅을 하면 쉽게 풀 수 있는 문제이다. 시간복잡도는 O(N) 2. Alien Piano 이 문제는 Greedy 알고리즘을 사용해서 풀었다. 먼저 배열을 통해 각각의 note의 pitch를 받아서 채워준다. 이 때 연속해서 같은 값이 나오게 되면 같은 alien piano key를 사용하게 되므로 배열에 넣어주지 않아도 된다. 이렇게 배열을 넣어 주었을 때 만약 다음과 같이 배열이 생겼다고 가정해 보자. 이 때는 연속해서 두 숫자가 같은 경우는 존재하지 않을 것이다. [1, 8, 9, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 3, 5, 7]..

이번에 살펴볼 문제는 프로그래머스의 문제이다. https://programmers.co.kr/learn/courses/30/lessons/62049 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 종이를 계속 반으로 접어서 안으로 파인 부분(∨)은 0, 밖으로 볼록 튀어나온 부분(∧)은 1로 순서대로 출력하면 되는 문제이다. 이 문제는 규칙성을 찾고 적절한 자료구조를 찾아서 탐색하면 그렇게 어렵지 않게 풀 수 있는 문제이다. 다만, 개인적으로 처음에 생각하기가 조금 쉽지 않았던 것 같다. 한 번 ..

오늘 살펴볼 문제는 백준 3176번 '도로 네트워크' 라는 문제이다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이 문제는 꽤 어렵다. https://solved.ac/ 라는 알고리즘 문제 난이도 측정 사이트에서는 이 문제를 플레티넘 4 레벨로 분류했다. 플레티넘 레벨은 상당수가 쉽게 해결책을 찾기 어려운 고난이도 문제이다.(나에게는) 이 문제도 그래서 사실 풀다가 다른 사람의 소스를 어느 정도 참고하였고, 천천히 상세하게 풀이를 정리..

오늘은 트리와 힙 자료구조에 대해서 알아보려고 한다. 트리 트리(Tree)는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 계층적(Hierarchical) 자료구조라고 표현하기도 한다. 유닉스/윈도우의 디렉터리(폴더) 구조가 대표적인 트리 구조의 예시이다. 트리와 관련된 용어들은 다음과 같다. 노드(Node) : 트리를 구성하는 기본 원소 간선(Edge) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(Siblings Node) : 같은 부모 노드를 갖는..