여름 언덕에서 배운 것

탐색 알고리즘이란 수많은 데이터 중에서 원하는 데이터/값을 찾아내는 알고리즘이다. 검색 방법에 따라 두가지로 분류할 수 있다. 비교 검색 방식 : 검색 대상의 키를 비교하여 검색하는 방법 (ex. 트리 검색, 순차 검색, 이진 검색) 계산 검색 방식 : 계수적인 성질을 이용한 계산으로 검색하는 방법 (ex.해싱) 이진 검색 트리 검색 트리는 한 노드에서 최대 몇 개의 자식 노드로 분기를 할 수 있느냐에 따라 이진 검색 트리와 다진 검색 트리로 나뉨 (이진 검색 트리는 최대 두 개의 자식 노드를 가질 수 있다.) 이진 검색 트리는 다음과 같은 특징을 가진다. 각 노드는 키 값을 하나씩 갖는다. 각 노드의 키 값은 모두 달라야 한다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖..

📚 문제 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하시오. 고정점은 최대 1개만 존재한다. 만약 고정점이 없다면 -1을 출력한다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다. 입력 예시 출력 예시 5 -15 -6 1 3 7 3 7 -15 -4 2 8 9 13 15 2 7 -15 -4 3 8 9 13 15 -1 📝 문제 해결 이미 배열이 ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📚 문제 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 📚 문제 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 첫째 ..