Algorithm
BOJ] 2579. 계단오르기
BOJ]2579.계단오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net DP는 고민하고 또 고민해야한다. 점화식(규칙)을 찾아야한다! 문제에서의 아래 규칙을 고려하여 점화식을 구해야한다. 계단은 한 ..
BOJ] 1003. 피보나치 함수
BOJ]1003. 피보나치 함수 https://www.acmicpc.net/problem/1003 DP의 맛보기 문제정도이다. 단순히 피보나치의 결과를 구하는 문제가 아니다. 피보나치 함수가 호출되었을 때, 0과 1이 얼마나 반환(출력)되는지 구하는 문제이다. 규칙을 살펴보자. 예를 들어, fibo(n) : (0의 반환횟수, 1의 반환횟수) 라고 하자. fibo(0) : (1,0) fibo(1) : (0,1) fibo(2) : (1,1) -> fibo(0) + fibo(1) -> (1,0) + (0,1) fibo(3) : (1,2) -> fibo(1) + fibo(2) -> (0,1) + (1,1) fibo(4) : (2,3) -> fibo(2) + fibo(3) -> (1,1) + (1,2) 피보나치의..
Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 최단경로 알고리즘 중 하나이다. 최단경로 알고리즘의 종류만 짚고 넘어가보자. 최단경로? 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(Dijkstra) 알고리즘 -- 음의 가중치를 허용하지 않음. 벨만포드(Bellman-Ford) 알고리즘 -- 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 다익스트라(Dijkstra)알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식. 시작정점[s]에서 끝정점[t]까지의 최단경로에 정점 x가 존재한다. 이때, 최단경로는 s..
Algorithm] 조합(combination) (JAVA)
2.조합(Combination) 전체 개수 중에서 원하는 개수만 뽑는 경우의 수. 조합의 알고리즘은 arr의 idx번째를, sel에 담자. 라는게 기본 틀이다. 한번 담아보고, 한번 안담아보고를 반복하면 됨.(idx값의 변화) arr에 idx번째를 sel의 k번째에 담고, 담은걸 유효화 하려면 k를 늘려주고 k를 그대로 가져가면된다. 12345678910111213141516171819202122232425public class Combination{ public static void main(String[] args) { int[] arr = {1,3,5,7,9}; //선택하려는 개수 int r = 3; combination(arr, new int[r], 0,0); } static void combin..
Algorithm] 부분집합(powerset) (JAVA)
1. 부분집합(powerset) 배열의 모든 부분집합을 구하는 방법이다. 예를 들어, {1,3,5}의 부분집합은 {1,3,5} {1,3} {1,5} {1} {3,5} {3} {5} 가 될 것이다. 코드의 핵심은 17~20번줄이다. sel이란 selected를 의미하는 준말로 작성하였다. 말 그대로, 선택여부를 판단하기 위한 배열이다. powerset 재귀함수로 들어가기전에 true를 해준다. 그리고 해당 재귀가 기저조건에 의해 종료가 되면, 원래대로 돌려주기 위해서 false로 바꿔준다. 재귀의 순서를 천천히 따라가다보면 이해할 수 있을 것이다. 애증의 재귀.. 1234567891011121314151617181920212223public class 부분집합 { public static void main..
![SWEA] 3131. 100만 이하의 모든 소수](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F7hbgv%2FbtqxxchL7rh%2FI2rOQR27tF4IWaukZ8SKSk%2Fimg.png)
SWEA] 3131. 100만 이하의 모든 소수
SWEA] 3131. 100만 이하의 모든 소수 SWEA 3131. 100만 이하의 모든 소수(Link) 문제의 저작권은 SWEA에 있습니다 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소수 문제는 에라토스테네스의 체 의 방법으로 접근해야한다. 소수는 1과 자기 자신만을 약수로 가지는 수를 말한다. 체로 수를 걸러낸다는 하여 에라토스테네스의 체라고 한단다. 에라토스테네스의 체를 다시 떠올려 봤을때, 기억나는 것은 모든 자연수는 소수의 곱으로 표현될 수 있다. 제일 작은 소수 2를 선택한다. N보다 작은 선택한 수의 배수를 지운다. (곱으로 표현되면 소수가 아니므로) 지워지지 않은 수를 반복한다. 이 작업을 ..