C++
-
알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)알고리즘 2020. 11. 9. 23:46
부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다. 합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다. 전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는 조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 예를 들어보자 n = 3, W =6 w1 = 2, w2 = 4, w3 = 5 이라 할때 각 노드들의..
-
알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!알고리즘 2020. 11. 9. 23:17
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자) 되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 seungjuitmemo.tistory.com 이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다. 몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위..
-
알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)알고리즘 2020. 10. 8. 22:25
외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 찾는 알고리즘 start node가 있고 n-1 개의 node를 거쳐 1번 node로 돌아간다. brute-force 알고리즘을 이용해서 문제를 해결할 수도 있지만 n이 20만 되어도 걸리는 시간복잡도는 19!usecs(대략 3857년)으로 평생 구하지 못한다. 하지만 동적프로그래밍을 이용한 TSP알고리즘이면 45초만에 해결가능하다. 그렇다면 예제를 TSP알고리즘을 이용하여 풀어보자 다음과 같이 가중치가 있고, 노드 4개로 이루어진 그래프(V)가 있다. 그리고 위 그래프를 인접매..
-
알고리즘: Dynamic programming을 이용한 이항계수(Binomial Coefficient) (feat.c++)알고리즘 2020. 10. 2. 15:39
이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dyna..
-
알고리즘: 슈트라센(Strassen) 행렬 곱셈 알고리즘 (feat.c++ ,pseudocode)알고리즘 2020. 9. 27. 15:33
이번 포스팅은 일반적인 정방행렬의 곱셈을 알아보고 더 빠른 슈트라센(Strassen) 행렬곱셈에 대해서 알아본다. void matrixMulti(const int a[][N], const int b[][N], int c[][N]) { for (int i = 0; i < N;i++) for (int j = 0; j < N; j++) { c[i][j] = 0; for (int k = 0; k < N; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } } 일반적인 행렬곱셈은 우리가 아는 행렬곱셈 그대로 코딩하면 위와 같은 3중 for문으로 구성된다. 1. 시간복잡도 분석 입력 크기 행과 열의 수가 n이라고 할 때 1) 곱셈의 관점 2) 덧셈의..
-
알고리즘: 백준 2565번 전깃줄 (feat. c++) 최장증가수열문제(LIS)알고리즘 2020. 8. 31. 22:41
백준 2565번 문제입니다. 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 좀 꼬아놓은 최장증가 수열 문제 (사실 최장증가수열문제는 처음 접해보았다...) 처음에는 파이썬으로 스택을 이용해서 풀었지만 무슨 이유인지 틀렸다고 나왔다... (틀린 코드) n = int(input()) line_list = [] for i in range(n): line_list.append(list(map(int, input().split()))) del_count = 0 while True: cross = [] for i in ran..
-
알고리즘: 백준 2293번 동전 1 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 25. 20:51
백준 2293번 링크입니다. 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 결론부터 말하면 dp를 이용해 풀어야 풀린다. 시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 처음에는 dfs를 이용해 풀었지만 시간초과가 나길래 결국은 다른 분의 답을 참고하였다. import sys class Node: # 방문처리를 위해 노드 클래스를 만들었다. def __init__(self, data): self.data = data def dfs(start, tar..
-
알고리즘: 백준 11057번 오르막 수 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 24. 11:45
백준 11057 링크입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽지만 어떤 구조를 이용하면 좋을지가 가장 어렵다. dp를 이차원리스트로 해서 dp[i][j] = 길이가 i인 끝자리수가 j인 오르막 수 라고 하면 쉽게 해결할 수 있다. (끝자리수를 기준으로 나누는게 포인트) i는 1 ~ 1000 j는 0 ~ 9까지 가능하다 예를 들어 dp[2][3]을 구한다고 하면 dp[2][3] = dp[1][2] + dp[1][1] + dp[1..