본문 바로가기
728x90

알고리즘118

[JAVA]백준 14567번: 선수과목 (Prerequisite) www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 1. 문제 설명 과목들의 선수과목 조건들이 주어질 때 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 구하는 문제. 2. 풀이 위상 정렬과 다이내믹 프로그래밍으로 풀 수 있는 문제이다. 1) 다이내믹 프로그래밍 X번 과목이 이수할 수 있는 최소 학기를 dp [X]라 할 때 dp [X]는 X의 선수과목들의 최소 학기의 최댓값 +1이다. dp [X]=MAX(dp [Y]+1) (Y는 X의 선수과목) 점화식과 선수과목 조건 A .. 2021. 2. 22.
[JAVA]백준 9184번: 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1. 문제 설명 재귀 함수 w(a, b, c)가 있는데 이 함수를 구현하는 것은 쉽다! 하지만 그대로 구현하면 값을 구하는데 오래 걸린다. a, b, c가 주어졌을 때 w(a, b, c)를 출력하라. 2. 풀이 w(a,b,c) 함수의 구현과 메모이제이션을 합쳐서 구현하면 쉽게 풀 수 있는 문제이다. a, b, c가 주어졌을 때 그 계산의 결과를 dp [a][b][c]에 저장해 두고 다음 a, b, c가 주어졌을 때.. 2021. 2. 20.
[JAVA]백준 13549번: 숨바꼭질 3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제 설명 수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간을 출력하는 문제이다. 수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1 위치로 이동하고 0초 후에 X*2 위치로 이동할 수 있다. 2. 풀이 kwoncorin.tistory.com/70 [JAVA]백준 1697번: 숨바꼭질 .. 2021. 2. 19.
[JAVA]백준 12851번: 숨바꼭질 2 www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제 설명 수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간과 가장 빠른 시간으로 찾는 방법의 가지 수를 출력하는 문제이다. 수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1, 2*X 위치로 이동할 수 있다. 2. 풀이 kwoncorin.tistory.com/70?category=.. 2021. 2. 18.
728x90

티스토리툴바