전체 글
-
[백준] #19115 가장 큰 정사각형 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 17:37
문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 목표 0과 1로 이루어진 배열이 주어질때 1로 이루어진 가장 큰 정사각형의 넓이를 출력 풀이 dp를 사용하여 dp배열에 가장 큰 정사각형의 변의 길이를 저장한다. 점화식 dp[i][j] = if ( dp[i][j]==1 && dp[i][j-1]!=0 && dp[i-1][j]!=0 && dp[i-1][j-1]!=0 ) dp[i][j] = min(dp[i][j-1], dp[i-1][j]); dp[i][j] = min(dp[i][j], dp[i-1][j-1]) + 1..
-
[백준] #9252 LCS2(Longest Common Subsequence) - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 17:01
문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 목표 두개의 문자가 주어졌을때 두 문자의 부분수열중 최장길이의 부분수열을 구하는 문제 풀이 dp를 사용하여 각 구간마다 최장부분수열의 길이를 저장시켜놓는다. 사진에서 동그라미 친 부분은 두 문자열의 부분문자가 같은 구간 => dp값이 1증가해야한다. 점화식 dp[i][j] = if (s1[i] == s2[j]) dp[i-1][j-1] + 1; ..
-
[백준] #11659 구간합 구하기4 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 16:22
문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. www.acmicpc.net 목표 N개가 주어졌을때 주어지는 구간의 합을 구하기 풀이 시간초과때문에 수를 읽을때마다 누적합을 구하는 배열을 생성함 그후 (n,m)범위가 들어오면 totalSum[m] - totalSum[n-1]연산으로 구간합을 구함 즉 (0~m) 까지의 전체합에서 (0~n-1)까지의 전체합을 빼주면됨 코드..
-
[백준] #2579 계단 오르기 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 15:30
문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 목표 가중치가 쓰인 계단이 있을때 마지막 계단까지 이동하며 얻을수 있는 최대 가중치 구하기(단, 3개연속 불가능) 풀이 점화식: dp[i] = sta..
-
[백준] #1932 정수삼각형 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 15:28
(문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 목표 정수로 이루어진 삼각형이 주어질때 맨위에서 대각선으로만 내려가면서 수를 선택하여 최대값을 구하는문제 풀이 DP로 풀이 점화..
-
[알고리즘] #13. SCC(코사라주, 타잔) 알고리즘Algorithm/알고리즘 2020. 2. 26. 17:44
#SCC(Strongly Connected Component): 강한 연결 요소 유향 그래프에서 임의의 두 정점 A, B에 대해 항상 A->B로 가는 경로가 존재하는 정점 그룹. + 즉 SCC안의 어떤 두 정점을 선택해도 서로 도달할 수 있는 경로가 존재한다. + SCC는 항상 최대로 정의된다. + 즉 SCC는 집합 내의 정점들이 서로 왕복 가능한 최대 크기의 집합이다. * 코사라주 알고리즘, 타잔 알고리즘은 모두 DFS(깊이 우선 탐색)를 기반으로 동작한다. #코사라주 알고리즘 주어진 그래프의 SCC(강한 연결 요소)를 찾기 위한 알고리즘 즉, 그래프 A가 주어질때, 1. 그래프 A에 대해 DFS를 수행하며, 방문하는 순서대로 스택 S에 삽입한다. 2. 그래프 A의 역방향 그래프 A'에 대해 스택 S에..
-
[알고리즘] #12. 위상정렬(Topological Sort)Algorithm/알고리즘 2020. 2. 18. 13:14
#위상정렬 어떠한 일을 하기 위한 순서를 탐색하는 알고리즘 즉, "순서가 정해져있는 작업"을 수행할때 그 순서를 결정하기위한 알고리즘 방향 그래프에 존재하는 각 정점의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는것 => 그래프를 정렬 ##조건 DAG(Directed Acyclic Graph): 방향성이 있고, 사이클이 없는 그래프 ##특징 하나의 그래프에는 여러개의 위상정렬이 존재한다. ##알고리즘 1. 진입차수가 0인 정점을 큐에 삽입. 2. 큐에서 원소를 꺼내고, 모든 간선을 제거 3. 간선을 제거한 이후에 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌때까지 2~3번 과정을 반복 모든원소를 방문: 위상정렬의 결과는 큐에서 꺼낸 순서 모든원소를 방문하기전에 큐가 비는경우: 사이클이 존재하는..
-
[알고리즘] #11. DP(DynamicPrograming): 비트마스킹(외판원 순회)Algorithm/알고리즘 2020. 2. 16. 06:59
#비트마스킹(Bit Masking) 알고리즘보다는 bit단위 테크닉에 가까운 기법 + 정수를 이진수로 표현하는것을 활용 => bit단위로 값을 보존하며 진행 + 0=flase=off / 1=true=on => 비트로 상태를 나타낼수 있다. + 최적의 성능을 얻는데 필수적인 기법(컴퓨터 하드웨어) #비트의 활용 집합 A={0, 1, 2, 3, 4} A의 부분집합을 표현하는 방법 1. int형 인덱스 활용 int[] arr_1234 = {1, 1, 1, 1, 0} int[] arr_124 = {1, 0, 1, 1, 0} => 문제점: 메모리낭비, 오버헤드 증가 2. 비트마스킹 활용 => 1개의 정수로 표현가능 {1, 2, 3, 4} = 11110 => 30 {1, 2, 4} = 10110 => 22 #비트연..