본문 바로가기

전체 글136

과일 탕후루 과일 탕후루 백준 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.
팬린드롬 파티-션 팬린드롬 파티-션 백준 2705번 문제https://www.acmicpc.net/problem/2705   1. 문제   2. 풀이2.1 아이디어임의의 수 n(n > 0을 만족하는 정수)을  a0 + x0 + a0 의 파티션으로 표현할 수 있다고 하자.a0을 파티션으로 만들었을 때 a0 + x0 + a0가 재귀적 팰린드롬 파티션이 되려면 a0의 파티션이 재귀적 파티션이면 된다. [재귀적 팰린드롬 파티션 예시 그_1] 임의의 수 n의 재귀적 팰린드롬 파티션의 개수를 D(n)이라고 하자.임의의 수 n을 a0 + x0 + a0의 파티션 으로 표현하는 방법은 [n/2] 이다.([]는 가우스 기호를 의미) [재귀적 팰린드롬 파티션 예시 그_2] [재귀적 팰린드롬 파티션 예시 그_3] a0 + x0 + a0의 재귀.. 2024. 7. 22.