복's

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제를 처음 접했을 때 바로 생각나는 풀이는 나는 구간합을 만들어서 푸는 것이였다!!! 내가 이런 생각을 하다니.... 첫 풀이는 구간 합 + 투 포인터 알고리즘을 이용해서 풀었는데 메모리 초과가 났고, 그 이유는 주어진 메모리 사용량이 고작 32MB로 다른 문제들에 비해서 매우 적었다. 그래서 구간 합 배열을 만들어서 푸는 문제가 아니라고 방향성을 변경했다. 투 포인터의 개..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP문제가 풀고 싶어서 DP문제로 골랐다. DP 알고리즘 분류로 들어가서 DP로 풀어야 하는걸 알고 문제를 시작한건 아쉬운 점인거 같다. 이 문제를 DP로 풀어야 하는 이유는 N으로 주어지는 값이 작아 보일 수 있지만 중복되는 연산이 엄청나게 발생한다. 따라서 난 DP 테이블을 구성하고 재귀함수로 Top - Down 방식을 채택했다. [ 📌 코드 흐름 ] 1. 파라미터로 들어오는 값이 조건에 부합하는지 확인한다. N % 3 == 0 N % 2 == 0 N - 1 (조건 없음) 2. 조건에 부합 or 이미 DP ..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 30분 잡고 풀었는데, 시간내에 풀지 못했던 문제로 정글 코치님이 주신 힌트를 기반으로 기숙사로 돌아가서 다시 풀었다...... 사실 힌트 받고, 다시 푸니까 5분정도 걸렸던 것 같다. 힌트의 키워드는 '이분 탐색'인데 트럭이 적재 가능한 중량이 '1,000,000,000' 이라는걸 보고, 생각하지 못한것이 안타깝고, 이게 경험의 z차이인..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net DP와 DFS를 이용해서 풀었던 문제다. DP를 이용한 이유는 특정 지역을 여러번 지날 때 이미 목적지 까지 도착한 적 있는 지역이라면 다시 계산할 필요가 없어서 였고, DFS를 통해서 해당하는 경로가 유효하진 확인이 필요했다. (사실 방문 체크는 하지 않고, 그냥 재귀함수라고 생각해도 될거 같다...) 코드는 간단한데, 코드의 흐름은 상, 하, 좌, 우 이동 가능한 좌표를 구하고, 이동이 가능..

https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 그래프 위상정렬을 공부하게 되면서 풀게된 문제로 두 가지 방법으로 접근할 수 있다. 1. 정방향 접근 [ 접근 순서 ] 주어진 input을 이용해서 그래프를 구성하면서 진입 차수도 같이 계산한다. 단방향 그래프로 구성한다. 도착 노드 번호에 진입 차수를 + 1 해준다. [0, 0, 0, 0, 0, 2, 3, 3]: 1 ~ 4번 노드 진입 차수 0 / 5번 노드 진입차수 ..