전체 글138 List of Unique Numbers List of Unique Numbers 1. 문제 2. 문제 풀이2.1 풀이주어진 수열에서 수가 중복되지 않는 모든 연속된 구간을 찾는 방법은 각 원소에서 시작하는 수가 중복되지 않는 가장 긴 구간을 찾는 것이다.문제에서 주어진 예제 2에서 수가 중복되지 않는 모든 연속된 구간을 찾아보자. [첫번째 원소에서 시작하는 수가 중복되지 않는 가장 긴 연속된 수열] 첫 번째 원소 1로 시작하면서 수가 중복되지 않는 가장 긴 연속된 수열(구간)은 위와 같이 1-2-3 이다.구해진 수열은 수가 중복되지 않기 때문에 첫 번째 원소로 시작하는 모든 부분 수열 역시 수가 중복되지 않는 수열이 된다. [첫번째 원소로 시작하는 수가 중복되지 않는 수열의 모든 경우] 위와 같이 1-2-3의 부분 수열인 1과 1-2 역시.. 2025. 8. 15. 이진 검색 트리 이진 검색 트리 1. 문제 2. 문제 풀이2. 1 이진 검색 트리이진 검색 트리는 문제에 나와있는 것과 같이 다음과 같은 조건을 만족하는 트리이다. 1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 이진 검색 트리를 만드는 방법은 다음과 같다. 1. 값을 새롭게 추가할 때 루트 노드부터 시작한다.2. 추가할 값이 노드의 값보다 작을 경우 왼쪽, 클 경우 오른쪽에 배치한다.3. 만약 노드의 왼쪽이나 오른쪽 값이 이미 존재한다면, 해당 노드 부터 2~3번을 반복한다. 이를 코드로 구현하면 다음과 같다. [이진 검색 트리_Node 클래스]public sta.. 2025. 5. 20. 과일 탕후루 과일 탕후루 백준 30804번 문제https://www.acmicpc.net/problem/30804 1. 문제 2. 문제 풀이2.1 조합어떤 과일을 남겨야 가장 긴 탕후루를 만들 수 있을까?아쉽게도 이에 대한 답을 한 번에 내기는 어렵다.다행히 과일의 종류는 총 9개밖에 안되기 때문에 조합을 사용해 모든 경우의 수를 체크하는 방식으로 문제를 풀 수 있다.주어진 과일에서 두개의 과일을 중복 없이 선택하고, 선택된 과일을 남겼을 때 가장 긴 탕후루를 구하면 된다. 조합은 다음과 같이 반복문을 통해 쉽게 구현할 수 있다. [반복문을 통한 조합 구현]for (int i = 0; i maxSize) { maxSize = extractedTanghulu; } }} f.. 2025. 4. 11. 키 순-서 & 플로이드-워셜 알고리즘 키 순-서 백준 2456번 문제https://www.acmicpc.net/problem/2458 1. 문제 2. 문제 풀이2.1 아이디어자신의 키 순서를 알기 위한 조건은 그래프상 모든 학생들과 연결되어 있어야 한다는 것이다. 예를 들어 5번은 3번과 6번에 연결되어 있지 않다.이 때문에 3번과 6번이 자신과 비교해서 어디에 위치해 있는지 알 수 없기 때문에 순서를 매길 수 없다. [순서를 알 수 없는 경우] 따라서 어떤 학생이 정방향과 역방향을 포함해서 모든 학생들과 연결되어 있으면 그 학생의 키 순서를 알 수 있다. 노드가 연결되어 있다는 것은 노드 간에 경로가 존재한다는 것이다.때문에 모든 노드간 가능한 모든 경로를 탐색하는 플로이드-워셜 알고리즘을 사용해서 이 문제를 해결할 수 있다. .. 2024. 8. 2. 이전 1 2 3 4 ··· 35 다음
