Algorithm
-
[백준] #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 #비트연..
-
[백준] #1759 암호만들기 - (BF)Algorithm/알고리즘 백준 풀이 2020. 2. 12. 18:51
dk문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 목표 주어진 알파벳으로 조건에 맞는 암호 생성 풀이 1. 조건을 확인할 수 있는 함수 생성 2. DFS를 사용하여 재귀함수 구현 내가 푼 방식: 정렬된 알파벳 배열에서 가장 작은 알파벳을 나타내는 인덱스를 사용하여 깊이우선탐색 수행 다른 코드: 비슷하지만 뭔가 더 전문적인거같음 코드 #1. 내코드 #include #include #include using namespace std; int S,..
-
[백준] #1080 행렬 - (BF)Algorithm/알고리즘 백준 풀이 2020. 2. 12. 17:24
문제 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 목적 2개의 행렬 A, B가 주어졌을때 A를 변환하여 B로 만들때의 최소 변환횟수 구하기 + 행렬의 변환은 변환위치를 기준으로 3*3만큼의 부분행렬을 변환함. 풀이 이 문제는 내가 제대로 이해를 못한거같다. 일단 변환은 3*3의 부분행렬만 변환하는것이므로 행렬의 원소를 오른쪽위에서 왼쪽아래로 하나하나 비교하면서 다르면 변환을 진행하되 범위에 제한을 N-3, M-3으로 줘야지 3*3행렬의 변환을 진행할수있다..