빵똥

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 1. 접근 문제에 앞서 이진 탐색 트리에 대해 간략히 설명하자면 이진 탐색처럼 특정 값을 찾는데 빠른 속도와 특정 값의 삽입과 삭제에 강한 링크드 리스트의 장점을 합친 자료 구조이다. 구현 방법으로는 크게 두 가지로 나눌 수 있다. 1. 트리 Class를 만들어 현재 노드의 값과 다음 값을 비교하며 트리를 만든 후 재귀적으로 후위 출력하는 방법 2. Class를 별도 생성하지 않고 트..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 트리의 개념을 코드로 구현해내는 가장 기본적인 문제가 아닐까 싶다. 자료구조 2번에 트리에 대해서 간단히 정리해두었으니 모르는 분은 한 번 보고 오셔도 될 것 같다! https://dhbang.tistory.com/14?category=905670 자료구조 - 2 트리 1. 트리의 개념 트리는 데이터 간의 관계를 나타내는 비선형 자료구조로 특정 조직의 조직도를 대표적인 예로 ..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 접근 문제를 풀기 전 시간 복잡도를 구하자! V + E를 T만큼 반복하는데 T는 제시되어 있지 않다! n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자! 문제의 조건을 살펴보면 트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 이 형식에 맞춰서 출력해주면 된다. 조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 접근 문제를 풀기 전 항상 시간 복잡도를 생각하자! 그래프 탐색에서의 시간 복잡도는 인접 행렬 = V², 인접 리스트 = V + E 이며 이번 문제 포함해 대부분의 문제는 인접 리스트로 접근하니 100,000 + 99,999 = 199,999로 시간 여유는 충분하다! 문제의 조건은 루트를 제외한 각 노드의 부모를 출력하는 것이다. 문제의 예제를 그림으로 그려서 접근해보자. 글로만은 이해가 어려우니 그림을 보며 이해해보자! 탐색을 진행하며 각 정점의 부모가..

1. 정렬 알고리즘 컴퓨터 과학에서 가장 많이 사용되는 연산 중 하나일 만큼 데이터를 활용함에 있어 정렬은 매우 중요하다. 예를 들자면, 당장 이 글을 쓰고 있는 티스토리에서도 글이 수백 개가 넘어간다면 카테고리별 혹은 날짜별 같은 특정한 정렬 기준에 따라 나열되어 있지 않다면 사람이 찾을 때도, 컴퓨터가 찾을 때도 많은 시간을 요구한다. 정렬 방법은 정렬이 수행될 때 데이터가 저장되어 있는 위치에 따라 내부 정렬, 외부 정렬로 구분한다. 내부 정렬은 데이터의 용량이 주기억장치(RAM) 저장 공간보다 작을 때 수행하는 정렬 방법이며 다양한 알고리즘에서 흔하게 사용되고 있는 정렬 방법이다. 외부 정렬은 내부 정렬의 반대의 케이스로 데이터를 보조 기억장치(HDD, SSD)에 저장하고 일부 데이터만 주기억장치..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 최대 입력값에 따른 시간 복잡도는 다음과 같다. 칸의 갯수 = H * N * M = 1,000,000로 시간제한안에 여유있게 풀 수있다! 문제의 조건을 살펴보자 익은 토마토 기준으로 상,하,위,아래,좌,우 총 여섯 방향으로 토마토는 익어가며 토마토가 비어있는 칸도 있다. 첫 번째 입력 예제를 그림으로 보면 토마토가 잘 익어가다가 비어있는 칸으로 인해 모두 익지 못..

1. 알고리즘이란? 이론적으로 컴퓨터를 사용한 문제 해결의 가능성이라는 측면에서 0개 이상의 입력과 1개 이상의 출력이 있어야 한다, 각 명령은 단순 명확해야 한다, 한정된 수의 단계를 거친 후 종료되어야만 한다, 모든 명령은 컴퓨터에서 실행 가능해야 한다.로 총 네 가지의 조건을 만족해야 한다. 하나의 문장으로 종합하자면 주어진 문제의 대한 해답으로 모호함 없이 간단하며 컴퓨터가 수행 가능한 유한개의 명령을 순서에 따라 구성한 것이다. 다만 컴퓨터로 해결할 수 있어도 처리 과정이 너무 오래 걸려 현실적으로 해결할 수 없는 문제도 있기에 효율성 또한 충분히 고려되어야 할 조건이다. 2. 자료구조와의 연관성 효율적인 프로그램을 위해서는 효율적인 알고리즘이 필요하며 효율적인 알고리즘을 위해 적합한 자료구조를..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 접근 배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다! 문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며 물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다. 다음과 같은 배치가 있다고 가정했을 때 최단 거리는 ..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 1. 접근 상근이의 위치, 즉 1번 정점에서의 거리가 2 이하인 정점의 수만 카운트하면 끝이다! 즉, BFS의 시간복잡도인 O(V + E) = 500 + 10000 이면 풀 수 있다! 자신의 친구, 친구의 친구를 정점과 간선에 비유하면 1과 인접한 정점, 1과 인접한 정점과 인접한 정점(??)까지의 수 이며 2번, 3번, 4번 친구가 초대 대상이 된다. 2. 풀이 변수 세팅 stat..

트리 1. 트리의 개념 트리는 데이터 간의 관계를 나타내는 비선형 자료구조로 특정 조직의 조직도를 대표적인 예로 들 수 있다. 트리는 데이터가 저장되는 노드와 다른 노드를 연결하는 가지로 구성되며 여러 가지들을 이용하여 계층적인 관계를 갖는다. 각 노드의 정보 항목과 뻗어져 나가는 가지를 합쳐 트리라고 부르는데 아래 그림에는 10개의 노드와 9개의 가지가 존재한다. 내부가 모두 비어있는 트리인 빈트리가 아닐 경우 최상위 노드를 루트라 부르며 사장실이 루트가 된다. 각 노드에서 하단으로 향하는 가지의 수를 차수라고 부르며 사장실의 차수는 3개, 그 외의 노드의 차수는 1개로 볼 수 있고(최 하단 팀 제외) 해당 트리의 차수를 얘기할 때는 제일 큰 차수인 3이 된다.트리에는 단말 노드 또는 잎 노드가 있는데..