27924번 : 윤이는 엄청난 것을 훔쳐갔습니다.
Tree Problem - G3
트리 구조를 이용하여 문제세어 제시 되어있는 가능 여부를 판별하여 출력하는 문제이다.
🤔 풀이 과정
- 가능 여부를 판별할 때 3명을 동시에 하나의 큐로 담는 방법으로 접근, 위의 방식으로 구하게 되면 시간 복잡도가 O(N ^ 3) 소요되어 시간초과가 발생한다.
- 따라서 우선 노드마다 두 명이 도달할 수 있는 최소 간선을 구한 뒤 나머지 한 명의 간선의 갯수를 구하면서 위에서 구한 값과 비교하는 방식으로 해결
- BFS & queue 이용
- 단, 움직일 때만 각 노드를 비교하는 것 뿐만 아니라 노드가 움직이기 전도 고려하여 풀이를 작성해야한다.
13140번 : Hello World!
Math Problem - G5
주어진 숫자를 지정할 때 각기 다른 숫자를 이용하여 합이 지정한 숫자가 나오는지 확인하는 문제이다.
🤔 풀이과정
- 숫자를 고를 때 각기 다른 숫자를 골라야함을 유의하야한다. 또한 계산시 1000 / 100로 나뉘어서 각 자리수 별로 문자를 정한 다음 계산한다
- 숫자 간 중복 점검 같은 경우 오브젝트 키 내 갯수를 활용하여 중복을 확인하였다. (각 상수 시간 복잡도 소요)
3958번 : 롤러코스터 타기
Math \ DP Problem - G2 (NS)
주어진 각 시간 내 롤러코스터를 타면서 최대로 얻을 수 있는 만족도를 출력하는 문제이다. 단, 중복으로 롤러코스터를 탑승할 경우 만족도가 떨어질 수 있음을 유의해야한다.
🤔 풀이과정
-
다이나믹 프로그래밍을 이용하여 해당 롤러코스터의 소요 시간과 만족도를 계산하는 방식으로 접근하였다.
- 점화식 : 현 시간 = max(현 시간, 현 시간 - 롤러코스터의 소요 시간 + 만족도)
- 소요 시간 : 최대 25000 * 100 횟수가 발생한다.
-
그러나 해당 방식으로 접근하였음에도 처음부터 오답으로 나왔기 때문에 추후 개선하여 문제를 풀어보아야겠다.
16725번 : 다항 계수
Math / DP Problem - P5 (NS)
위의 다항계수가 주어질 때 해당 차수의 계수를 구하는 문제이다.
꽤나 다양한 방법으로 문제 풀이를 시도하였었다.
🤔 풀이과정
-
누적 합과 슬라이딩을 이용하여 m번 동안 반복 후 해당 계수를 구하는 방식으로 시도하였다. 또한 해당 계수를 구한 뒤 다이나믹 프로그래밍을 이용하여 m번까지 곱한 수를 각각 저장한다.
- 점화식소요 시간 : 최대 25000 * 500 번
- 그러나 위와 같은 방식으로 시도할 경우 메모리 초과가 발생한다.
- 파이썬 같은 경우 다이나믹 프로그래밍에 필요한 최대 메모리는 다음과 같다.
- 28 * 12,500,000 byte = 350mb (256mb가 주어졌으므로 메모리 초과)
- 메모리를 고려하여 정적으로 지정하는 대신 동적으로 배열을 지정하였음에 불구하고 메모리 초과가 발생하였다.
-
메모리 초과를 해결하기 위해 모든 배열을 지정하는 대신 두 개의 배열만 저징하고 값을 구하는 동안 깊은 복사를 이용하여 값을 구하는 방식으로 접근
- 깊은 복사 같은 경우 각 연산마다 최대 25000번의 연산을 추가로 수행하기 떄문에 시간 초과가 발생 했을 것 같다.
-
시간 초과 및 메모리 초과를 해결하기 위해서 자료객체 큐를 이용하여 접근하였다.
- 위의 에러는 해결 하였지만 제출 시 오답으로 처리되어졌다.
-
확인결과 Generating Function를 이용하여 문제를 해결하는 방법이 있어서 위와 같은 방법을 조사한 뒤 다시 도전할 예정
23040번 : 누텔라 트리 (Easy)
Tree Problem - G3
트리가 주어질 때 조건에 맞는 경우의 수를 출력하는 문제이다.
🤔 풀이과정
- 그래프 순회를 이용하여 경우의 수를 구하면 되는 방식으로 풀었다.
- 방문하지 않은 검은 노드 : 빨간 노드의 수 * 검은 노드의 수
- 그러나 위와 같은 방법으로 풀이시 시간초과가 발생하였다.
- 따라서 접근 방식으로 바꾸어 검은 노드를 찾아서 순회하는 방법 대신 순회하지 않는 빨간 노드를 순회하여 경우의 수를 구하는 방식으로 풀었다.
- 위 문제 같은 경우 각기 다른 언어로 풀어보았기 때문에 언어마다 사용되는 시간이랑 메모리 차이를 알 수 있었다.
- 시간 같은 경우 Python 언어가 빨랐던 반면, 메모리 사용량 같은 경우 node.js가 적게 메모리를 사용하였다.
6087번 : 레이저 통신
Dijkstra Problem - G3
그래프 순환을 이용하여 해당 값의 최소 거리를 구하는 문제이다.
🤔 풀이과정
- 다익스트라를 이용한다.
- 우선 시작 점과 종료 점의 위치를 정한 뒤 시작점을 기점으로 그래프 순회를 진행하는 방식으로 구현하였다.
- 점화식 : Min( 기존 최소 횟수, 현재 횟수 + 1 )
- 모든 그래프를 순회 후 도착점의 최소 횟수를 출력한다.
1234번 : 크리스마스 트리
DFS / Math Problem - G2
DFS와 조합을 이용하여 경우의 수를 구하는 문제이다.
🤔 풀이과정
- 먼저 2차원 배열을 이용하여 문제 풀이에 접근하였다.
- 배열를 이용하여 각 색깔을 선택하였을 때 경우의 수를 구한 뒤 남은 색깔의 공을 구하는 방식을 생각하였다.
- 단, 2차원 배열로 어떠한 방식으로 최적화된 공을 저장해야하는지 알 수가 없었다.
- 재귀함수를 활용하여 DFS방식으로 문제를 다시 접근하였다.
- 트리의 깊이가 최대 10이기 때문에 재귀를 이용해도 메모리 초과가 발생하지 않는다.
- 남은 색깔의 갯수에 맞게 다음 깊이에 선택할 경우의 수를 정한다.
- 1개의 색깔, 2개의 색깔, 3개의 색깔
- 2개와 3개 같은 경우 각각 갯수가 같아야 하므로 나머지를 이용한다.
- 경우의 수 같은 경우 조합을 이용하였다.
14428번 : 수열과 쿼리 16
Segment Tree Problem - G1
세그먼트 트리를 활용해야하는 문제이다.
🤔 풀이과정
-
먼저 문제 조건만 보았을 때 힙 정렬로 구현이 가능하지 않을까 생각이 들었었다.
- 값을 변경할 때에는 구현이 가능하지만 값을 출력할 때 부분 값을 구해야하기 때문에 시간복잡도 측면에서 문제가 발생한다.
- 상수로 걸리기 때문에 시간초과 발생
- 값을 변경할 때에는 구현이 가능하지만 값을 출력할 때 부분 값을 구해야하기 때문에 시간복잡도 측면에서 문제가 발생한다.
-
세그먼트 트리를 이용한다.
- 처음 제출 시 '틀렸습니다'가 발생하였는데, 확인 결과 값 출력 함수 내 분할 파라미터 입력과 리턴값 조건이 잘못 되었다.
- 분할 → 찾으려는 부분은 그대로, 범위만 반 토막 시킨다.
- 범위가 완전히 같지 않아도 범위 내에 들어가 있으면 그 자리에서 값을 리턴한다.
- 처음 제출 시 '틀렸습니다'가 발생하였는데, 확인 결과 값 출력 함수 내 분할 파라미터 입력과 리턴값 조건이 잘못 되었다.
11689번 : GCD(n, k) = 1
Math Problem - G1
시간복잡도가 낮은 공배수 알고리즘을 활용해야하는 문제이다.
🤔 풀이과정
-
처음에는 단순 반복문을 이용하여 공배수 알고리즘을 구현하였는데 시간초과가 발생하였다. 상수로 시간이 소요되지만 주어진 값이 매우 크기 때문에 시간초과가 발생
-
따라서 서로소의 제곱이 주어진 값보다 높지 않도록 범위를 한정시켜서 공배수 알고리즘을 구현하는 방식으로 변경하였다.
1019번 : 책 페이지
Math Problem - G1
수학적 규칙을 찾아 식으로 일반화 시켜 풀어야하는 문제이다.
🤔 풀이과정
- 일의 자리수를 시작으로 각 자리 수 마다 나오는 숫자를 더하는 방식으로 풀이하였다.
- 범위 : 자릿 수 시작 ~ (해당 숫자의 자릿수 - 1)
- 예시
12345의 3의 범위 : 12000 ~ 12299
12345의 1의 범위 : 0 ~ 9999
- 각 자리 수별로 얻을 수 있는 최대 갯수는 다음과 같다.
- (전 자리수에 구했던 최대 갯수) + 10 ^ n
- 0의 갯수를 계산할 경우 앞자리에 0이 나오는 경우를 고려하여 계산해야한다.
- (10 ^ n) + (10 ^ (n - 1)) + ... + 1
