전체 글137 이진 검색 트리 이진 검색 트리 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. 후위-표기식 후위 표기식 백준 1918번 문제https://www.acmicpc.net/problem/1918 1. 문제 2. 문제 풀이2.1 아이디어중위 표기식을 후위 표기식으로 변경하기 위해서는 먼저 연산에 따라 괄호를 묶어주어야 한다.예를 들어 다음과 같은 수식이 있다고 하자. A+Bx(C-D)/E 이 수식을 연산의 우선순위에 따라 괄호로 묶어주면 다음과 같은 형태가 된다. (A+((Bx(C-D))/E)) 왼쪽부터 시작해서 연산의 우선순위를 기준으로 괄호로 묶어주었다.이제 이 식을 괄호에 따라서 후위표기식으로 변경하면 다음과 같다. ABCD-xE/+ 중위 표기식을 후위 표기식으로 바꾸는 과정에는 규칙이 있다. 1. 피연산자는 왼쪽부터 순차적으로 출력된다. - 피연산자의 순서는 바뀌지 않는다 연산자의 위치만.. 2024. 7. 30. 이전 1 2 3 4 ··· 35 다음
