♠ 그리디 알고리즘의 정의 https://jy-deeplearning.tistory.com/64 그리디 알고리즘(백준 알고리즘 11399)♣ 정의 매 선택에서 가장 최적인 답을 선택해서 적합한 결과를 만들자는 의미의 알고리즘 즉 각 부분에서의 최적의 답을 모두 모았을 때 종합적으로도 최적의 결과가 나오는 문제에 적절한 알jy-deeplearning.tistory.com 그리디 알고리즘은 매 선택에서 지금 당장 최적인 답을 선택하여 적합한 결과를 도출하려는 알고리즘 설계 기법이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 종합적으로 보았을 때는 최적이라는 보장이 없다.   ♠ 문제 이해(백준 알고리즘 4055번) 이 문제는 아람이가 아침 8시부터 자정까지 열리는 파티들을 최..

♠ 문제 이해 이 문제는 가위바위보의 승리 확률을 구하는 문제이다. 동주와 항승이가 n번 가위바위보를 할 수 있는데, n번까지 가는 동안 k번 먼저 이기는 사람이 승리한다. n이 항상 k보다 크거나 같기 때문에 n번을 하기 전에 승부가 날 수도 있다.  ♠ 각 경우의 수 구하기 예를 들어 N = 3, K = 2 일 때 항승이가 승리할 수 있는 경우의 수는 다음과 같다. [이, 이][이, 비, 이][비, 이, 이][이, 지, 이][지, 이, 이] 위의 경우의 수를 살펴보면 [이, 이] 는 N=2, K=2 인 경우에도 나올 수 있는 경우이다. 즉 현재 N번(3번) 가위바위보를 하는 경우의 수만이 아니라 그 전의 N-1번(2번)에서 K번 이기는 경우까지 고려해야 하는 것이다. 점화식으로 나타내면 이렇게 될 것..

♣ 문제 이해  위의 문제는 K와 R로만 이뤄진 문자열이 주어졌을 때 'R'로만 이뤄진 문자열, 또는 양끝에 같은 수의 K를 가지고, 가운데에는 R들이 올 수 있는 문자열 중 가장 긴 문자열의 길이를 출력하는 문제이다.  또한 힌트에 의하면 문자열에서 몇 개의 문자를 지워서 부분 문자열을 만드는 것도 가능하다.   예제를 보면 ㅋㅋ루ㅋㅋ 문자열의 조건을 만족하는 문자열은 아래와 같다.  R, KRK, KKRKK 이 중 가장 긴 문자열의 길이는 5이다.   두 번째 예제를 보면 조건을 만족하는 문자열은 아래와 같다. R, RR, RRR, RRRR K가 R의 양쪽에 같은 갯수만큼 와야 하는데 그게 불가능하기 때문에 가운데 K를 지워버리고 R을 모두 붙여서 ㅋㅋ루ㅋㅋ 문자열을 만드는 게 더 최대의 길이를 구하..

♠ 문제 이해   주어진 n을 이용하여 그래프를 만들어서 가로, 세로축에 따라 어떤 숫자가 나오는지를 계산하면 해결할 수 있는 문제이다. 0, 0 위치에 1이 들어가고, 대각선 방향으로 숫자가 점점 커지며 들어가는 규칙이 있다.  ♠ 수학적 알고리즘 정리 우선 가로, 세로에 따라 해당 칸의 숫자를 구하는 수학 알고리즘을 정리해보았다.  n = 4 일 때의 행렬을 그려보았다. 가로를 i, 세로를 j 라고 생각해서 위의 행렬을 가로, 세로 크기로 나타내면 아래와 같다.  1) 윗부분의 숫자 구하기 대각선으로 자르면 각 구간에서 i+j의 합이 같다. i + j = 0 인 구간에서 i + j = 3 인 구간까지를 행렬의 '윗부분'이라고 생각할 때, 각 구간의 첫 번째 수를 구하는 알고리즘은 아래와 같다.   i..

♣ 위상정렬의 정의위상정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 아래와 같은 비순환 방향 그래프(DAG: Directed Acyclic Graph) 에서 가능하다.  위의 DAG에서 노드들을 방향성에 거스르지 않는 순서대로 나열하면 아래와 같다. (위상정렬 결과) 예시1 예시2 사이클은 노드 사이에 선수관계를 알 수 없는 그래프를 의미한다. 사이클이 있는 방향 그래프에서는 어느 노드가 선순위에 있는지 알 수 없기 때문에 위상정렬이 불가능하다.   ♣ 진입차수와 진출차수진입차수(Indegree)는 노드로 들어오는 간선의 수를 의미한다. 진출차수(Outdegree)는 노드에서 나가는 간선의 수를 의미한다. 위 그래프에서 노드 4를 예로 들면 진..

♣ 누적합https://jy-deeplearning.tistory.com/175 누적합(백준 알고리즘 10986번)♣ 누적합누적합은 배열의 일부 구간에 대한 합을 쉽게 구할 수 있는 알고리즘으로, 배열의 값이 변하지 않는다면 누적합 역시 변하지 않는다는 점을 이용한다. 미리 구해둔 누적합을 이용하여jy-deeplearning.tistory.com ♣ 문제 이해 이 문제는 정수 N개로 이루어진 배열의 부분합에서 합이 K가 되는 부분합의 개수를 구하는 것이다.  n = 6k = 5list = [1, 2, 3, 4, 5, 0] 위 예시를 보면 주어진 리스트 안의 숫자는 4개이고, 이 리스트의 부분합 중 합이 5인 갯수를 찾는다.  list = [1, 2, 3, 4, 5, 0]#부분합이 5인 조합[(2, 3),..