본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 5582번 : 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net dp문제였습니다. 풀이방법 d[i][j] = i부분과 j부분의 문자가 같다면 그 이전의 최대길이 + 1 로 정의합니다. Code #include using namespace std; string s, t; int ans, d[4001][4001]; int main(){ cin >> s >> t; for(int i = 0; i < s.size(); i++){ for(int j = 0; j..
(C++) - 백준(BOJ) 11657번 : 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 문제였습니다. 풀이방법 1. 매번 edge에대해 벨만포드 알고리즘을 수행합니다. 2. 최단경로는 최대 N개의 정점 N-1개의 간선을 가지므로 N번째 수행시 갱신값이 있다면 음수 사이클 판정을 할 수 있습니다. 3. 음수 사이클이 존재한다면 -1만 출력. 아닐 경우에는 1에서 출발해 2 ~ N으로 가는 정점까지의 시간을 출력. 만..
(C++) - 백준(BOJ) 1915번 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp문제였습니다. 풀이방법 2 X 2짜리 정사각형을 생각합니다. i행 j열이 1이라면 이전에 가장 큰 정사각형의 한 변의 길이가 저장된 (i-1,j-1), (i-1,j), (i,j-1) 위치의 값들중 최소인값 + 1을 저장합니다. 점화식으로 나타낸다면 min({square[i-1][j-1],square[i-1][j],square[i][j-1]}) + 1 Code #include #define INF 0x3f3f3f3f using namespace std; int n,..
(C++) - 백준(BOJ) 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp 문제입니다. 풀이방법 d[i][j] : 현재 i행, j열로 왔을 때 최댓값입니다. i행 j열로 오기 위해서는 이전 위치가 i-1행 j-1열 또는 i-1행 j열뿐입니다. 따라서 해당위치의 최댓값 + triangle[i][j]가 답이 됩니다. 점화식으로 쓴다면, d[i][j] = max(d[i-1][j-1],d[i-1][j]) + triangle[i][j] Code #include using namespace std; int n, triangle[505][505], ..
(C++) - 백준(BOJ) 14476번 : 최대공약수 하나 빼기 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 누적 GCD를 구하는 문제였습니다. 풀이방법 a는 n개의 수를 입력받고 저장하는 배열, lgcd를 왼쪽에서 시작해 오른쪽으로 가며 누적 gcd를 구한 값을 저장하는 배열, rgcd는 오른쪽에서 시작하는 배열이라고 정의합니다. a 8 12 24 36 48 lgcd 8 4 4 4 4 rgcd 4 12 12 12 48 다음 예제에서 i번째 값을 지울 때 이렇게 생각할 수 있습니다. lgcd[i-1] -> 삭제할 ..
(C++) - 백준(BOJ) 1516번 : 게임개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬문제였습니다. 풀이방법 짓는데 오래걸리는 순으로 pq에 넣어 꺼내 확인하면서 진입차수를 줄여가는 방식으로 구현합니다. 진입차수가 0이라면 현재정점 x가 가장 최적으로 지을 수 있는 건물이므로 x의 시간을 next정점의 시간에 더해서 갱신해줍니다. Code #include using namespace std; int n, ind[501]; struct Edge {int v, w; ..
(C++) - 백준(BOJ) 1753번 : 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 dijkstra는 greedy, dp속성을 모두 가지고 있습니다. 시작정점 start -> x -> y -> z 로 가는 경로가 있을때 start에서 x로 가는 경로들 중 가장 작은 cost에 대해 갱신하는 방식입니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pi..
(C++) - 백준(BOJ) 2458번 : 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net floyd warshell 응용 문제였습니다. 풀이방법 간선을 i정점 - j정점으로 표현합니다. 1. 정점 u, v를 m만큼 입력받습니다. 이 정보는 이차원 배열 adj에 가는 경로가 있음을 표현하기 위해 1로 저장됩니다. 2. 입력 후에 바로 가는 경로외에 다른 정점을 거쳐 목적지 정점에 도착할 수 있는지 확인하며 정보를 저장합니다. i - k, k - j 가 연결이 되어있다면 i - j로도 갈 ..

티스토리툴바