본문 바로가기

알고리즘131

[백준] 1717 집합의 표현(유니온 파인드) 유니온 파인드 상호 배타적 집합이라고도 한다. 2가지 연산으로 이루어져 있다. 1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산- 구현은 트리를 이용해서 한다. - parent[i] = i 의 parent 가 저장되어 있음 * parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의 *** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다. https://www.acmicpc.net/problem/1717 2017. 7. 6.
[백준][그래프] 2623 음악프로그램 가수의 순서에 따라 인입간선의 개수를 설정하고, 하나씩 제거하면서 DAG로 문제를 해결한다. https://www.acmicpc.net/problem/2623 2017. 7. 4.
[백준][위상정렬] 2056 작업 DAG 이 문제도 DAG 형태로 풀 수 있다. 1. 선행관계 처리를 위해 노드별로 인입되는 간선의 개수를 기록한다. 2. 인입 간선이 0인 노드를 큐에 넣어서, 선행 처리가 끝난 노드에서 방문가능 한 노드 들을 차례로 방문하면서 시간을 더해준다. 3. 최종적으로 시간이 가장 많이 걸리는 작업을 출력한다. https://www.acmicpc.net/problem/2056 2017. 6. 27.
[백준][다이나믹] 1890 점프 다이나믹 프로그래밍을 이용하여 풀이가 가능하다. 현재위치까지 이동가능한 경우의 수(dp[x][y])를 다음 이동가능한 위치(dp[x+move][y], dp[x][y+move])에 더하여 이동가능한 경우를 모두 더하여 준다. 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 3 3 https://www.acmicpc.net/problem/1890 2017. 6. 26.
[백준][다이나믹] 11048 이동하기 이 문제는 DP로 해결 가능하다. 아래와 같이 해결이 가능하다. https://www.acmicpc.net/problem/11048 2017. 6. 26.
[백준][트리] 11437 LCA LCA 문제는 우선 트리형태를 구성해서BFS를 이용하여 현재 노드의 부모노드, 깊이를 구한다. 그다음 깊이를 동일하게 설정하고, 한단계씩 올라오면서 부모가 같아지면 그때 부모를 출력하면 해결할 수 있다. https://www.acmicpc.net/problem/11437 2017. 6. 22.
[백준][그래프] 1916 최소비용 구하기 - 다익스트라 알고리즘 이 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. * 주의 사항은 nXn 배열을 이용하여 간선의 정보를 입력 받는데 동일한 경로로 다른 비용의 데이터가 입력되는 경우에 대한 회피만 잘 해주면 된다. https://www.acmicpc.net/problem/1916 2017. 6. 22.
[백준][그래프] 1753 최단경로 - 다익스트라 알고리즘 최단경로 문제는 다익스트라 알고리즘을 이용하여 최단경로를 확인한다. 현재 최소값을 가지는 경로를 선택하여 해당 경로 부터의 거리를 확인하면 된다. https://www.acmicpc.net/problem/1753 2017. 6. 22.
[백준][최단거리] 11657 타임머신(벨만포드 알고리즘) 시작지점 부터의 최단거리 확인을 위한 알고리즘을 사용하여 처리한다. 음수를 입력받을 수 있기 때문에 벨만포드 알고리즘을 이용한다. https://www.acmicpc.net/problem/11657 2017. 6. 21.
[백준][다이나믹] 10844 쉬운계단수 쉬운 계단수는 앞에서 선택된 숫자 다음에 올 수 있는 숫자는 앞숫자-1, 앞숫자+1 이라는 것을 생각하여 해결 할 수 있다. 자리수가 1일때는 1~9까지 9개가 존재한다. 자리수가 2일때부터 다음숫자에 0이 나올 수가 있다. 앞자리가 0, 9일때는 뒤에 1, 8만 올 수 있으므로 하나만 선택가능하다. 하지만 1~8은 -1 또는 +1 인 숫자가 올 수 있다. 이를 이용하여 다음과 같이 해결하면 된다. memo[length][number] = memo[length-1][number - 1] + memo[length-1][number + 1 이 결과를 MOD 로 나눈 나머지를 저장하면 된다. https://www.acmicpc.net/problem/10844 2017. 6. 21.
[백준][위상정렬, DAG] 2252 줄세우기 줄세우기 문제는 DAG로 표현할 수 있다. 메모리 절약을 위해 간선의 연결 상태는 리스트로 표현한다. 노드에 입력이 들어는 것을 따로 배열로 표현하여 더이상 연결이 되지 않는 노드는 제거하면 된다. https://www.acmicpc.net/problem/2252 2017. 6. 20.
[백준][다이나믹] 1520 내리막길 내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. DFS를 이용하여 종점을 찾아서 다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 최종 위치에서 되돌아 가면서 경로를 표시하고, 새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 10 1020 19 18 17 16 15 14 13 12 11 19 18 17 16 15 14 13 12 11 10 18 17 16 15 14 13 12 11 10 9 17 16 15 14 13 12 11 10 9 8 16 15 14 13 12 11 10 9 8 7 15.. 2017. 6. 20.
[정올][다이나믹] 2293, 동전 1 N개의 동전의 가치를 합하여, K원을 만드는 경우를 구한다. 1, 2, 5 원의 동전을 이용하여 10원을 만드는 경우는 다음과 같다. 사용동전1 2 5 개수 1 1 1 2 1+1 2 2 3 1+1+1 1+2 2 4 1+1+1+1 1+1+2, 2+2 3 5 1+1+1+1+1 1+1+1+2, 1+2+2 5 4 5원을 만드는 경우는 위와 같다. 1원동전 사용: 1원을 5개 사용2원동전 사용: 3원을 만드는 경우에 2원을 더하여 생성5원동전 사용: 0원을 만드는 경우에 5원을 더하여 생성 https://www.acmicpc.net/problem/2293 2017. 6. 19.
[백준][다이나믹] 2156 포도주 시식 포도주 시식은 포도주를 첫번째로 마시는 경우, 두번째로 마시는 경우, 마시지 않는 경우로 나누어서 생각하면 해결할 수 있다. 6개의 와인잔이 1000, 900, 2, 1, 800, 700 의 순서로 놓여져 있는 경우 다음과 같이 생각할 수 있다. 순서 1 2 3 4 5 6 첫 번째로 마시는 경우 1000 900 1002 1901 2700 2601 두 번째로 마시는 경우 0 1900 902 1003 2701 3400 마시지 않는 경우 0 1000 1900 1900 1901 2701 3번의 경우에 첫 번째로 마시는 경우는 이전에 마시지 않는 경우에서 자신을 더하는 것이다. -> 1000 + 2 = 1002두 번째로 마시는 경우는 이전에 첫번째로 마시는 경우에 자신을 더하는 것이다. -> 900 + 2 = 9.. 2017. 6. 19.
[백준] 1003 피보나치 함수 일반적으로 다이나믹 프로그래밍을 이용하여 피보나치 함수를 구현하는 방법을 그대로 이용하면된다. 다른점은 0을 출력하는 것과 1을 출력하는 것을 따로 저장하여 다음 값의 호출에 0과 1을 출력하는 경우를 모두 더하여 출력하면 된다. dp[N][0] : N번째 수의 0 출력 횟수dp[N][1] : N번째 수의 1 출력 횟수 i번째 수의 0과 1출력 횟수는 다음과 같다. dp[i][0] = dp[i-2][0] + dp[i-1][0];dp[i][1] = dp[i-2][1] + dp[i-1][1]; 2017. 6. 1.
[백준] 1932 숫자삼각형 숫자 삼각형은 위에서부터 순서대로 아래로 내려가면서 현재 노드까지 최대값을 계산하여 자장하는 다이나믹 프로그래밍으로 해결하면된다. 트리형태를 배열에 저장하면 배열의 상단, 좌상단이 현재의 노드에 접근이 가능한 노드 이므로 이 두개의 값과 현재의 값을 더하여 최대값을 저장한다. 2017. 5. 31.
[정올][bfs] 2613 토마토(고) BFS를 이용하여 익지 않은 토마토가 존재하는 곳으로 한번씩 이동하여 더이상 처리할 곳이 없을 때 까지 이동하면 된다. BFS 이용시 재귀를 이용하게 되면 스택오버플로우가 발생한다. 2017. 5. 12.
[정올][다이나믹] 1411 두 줄로 타일 깔기 두줄로 타일깔기는 라인 길이에 따라 타일을 배열하는 방법을 생각해서 처리하면된다. 구현할 때 재귀를 이용하여 처리하면 stack overflow 가 발생한다. f(n) 을 구하는 방법은 f(n-1) 의 타일 개수에 1 x 2 타일을 하나 추가하는 방법과f(n-2)의 타일 개수에 2 x 2 타일을 추가하는 방법 두개를 더하면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=687&sca=3050http://huiyu.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-%EB%AC%B8%EC%A0%9C 2017. 4. 25.
[정올][다이나믹] 1408 전깃줄(초) 전깃줄 문제는 다이나믹 알고리즘의 LIS를 응용하는 문제이다. 입력받은 전봇대의 쌍 중에서 하나를 기준으로 정렬하여, 정렬되지 않은 전봇대중 가장 많이 정렬되어 있는 전봇대의 값에서 전체를 빼면 제거해야할 최소의 전봇대 개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=684&sca=3050 2017. 4. 24.
[백준][DP] 9251 LCS 알고리즘 LCS(Longest Common Subsequence)는 다이나믹 프로그래밍을 이용한 알고리즘 문제 풀이에 자주 이용된다. 이는 문자열 두개를 비교하여 순서대로 있는 가장 긴 문자의 수를 세는 것이다. 배열을 만들어서 문자가 일치할 때는 좌측 상단의 값에 +1을 하여 주고, 일치 하지 않으면 좌측 또는 상단의 값 중 더 큰값을 선택하여 준다. 이를 끝까지 반복하여 나오는 가장 큰 수가 LCS 값이 된다. import java.util.Scanner; public class Problem9251 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.nextLine();String str.. 2017. 4. 20.
[알고리즘] 최소비용 신장트리 - 프림알고리즘 최소비용 신장트리 구현알고리즘 중에서 프림알고리즘을 구현해 보았다. 프림알고리즘은 하나의 노드를 선택해서 다른노드로 가는 최소비용의 간선을 선택하고, 다음에는 선택한 노드중에서 나머지 노드로 가는 최소비용의 간선을 선택하여 최소비용 트리를 구현하는 것이다. 2017. 4. 18.
[알고리즘] 조합 조합은 n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 것을 말한다. 012에서 2개를 골라서 만들수 있는 부분집합의 개수는01, 02, 12 의 세가지 경우이다. 조합은 for 문을 이용하여 구현할 수도 있고, 재귀를 이용하여 구현할 수도 있다. 2017. 4. 17.
[정올][분할정복] 1335 색종이만들기 색종이 만들기는 사각형을 4등분하여 나누어 가면서 색종이가 모두 하나의 색인지를 확인하여 나가면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=614&sca=3060 2017. 4. 14.
[스크랩] [정올] 문제 해답 정올 같은 사이트의 문제해답을 올리시는 분이 있어서 스크랩 해석을 상세하게 해주시기 때문에 많은 도움이 된다. http://comganet.github.io/dp/2016/06/03/dp-1007 2017. 4. 13.
[정올][다이나믹] 1520 계단오르기 계단오르기는 다이나믹으로 해결할 수 있다. 연속해서 오른 계단이 하나인 것과 두개인 것을 계산하여 처리할 수 있다. 1번은 연속해서 오른 계단이 하나인것, 즉 두번 뛰어서 오른 계단에 대한 정보를 확인하는 것이다. i-2 번째 계단의 1번 연속, 2번 연속해서 오른 계단의 최대값가 현재 계단의 값의 합이다. 2번은 연속해서 오른계단이 두개인것, 즉 이전계단에서 한번오른 것이다. 이전계단에서 한번오른 값과 현재의 값을 더하여 결정한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=792&sca=3050 2017. 4. 13.
[정올][다이나믹] 1407 숫자카드 숫자카드 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 27123을 2글자씩 읽어서 숫자로 확인하고 34이상이면 분할한다. 27, 123 으로 분할하고 카드로 표현할 수 있는 형태가 몇개인지 확인한다. 카드로 표현 가능한 개수는 마지막 수를 표현하는 카드가 한자리 수인지, 두자리 수인지로 구분하여 점화식을 구성한다. D[i] = (D[i-1][0] * 2 )/2 + D[i-1][1] + (D[i-1][0] * 2 )/2 끝자리가 한자리수이면 마지막에 하나더 숫자가 붙어서 두자리 또는 한자리가 될수 있기 때문이다. 끝자리가 두자리수 이면 한자리수로 붙어서 표현이 가능하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=683&sca=3050 2017. 4. 13.
[정올][최단거리] 1108 페이지 전환 각 노드에서 자신을 제외한 노드로 이동하는 최단거리를 구하여 모두 더하는 문제이다. BFS를 이용하여 문제를 해결할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=50&sfl=wr_hit&stx=1108&sop=and 2017. 4. 11.
[정올][다이나믹] 1848 극장좌석 극장좌석문제는 다이나믹 프로그래밍으로 풀이가 가능하다. 전제조건은 좌우 한칸으로는 이동이 가능하다. 좌석이 2개일 경우 아래의 두개의 경우가 가능1, 22, 1좌석이 3개일때는 좌석이 2개인 경우에서 끝자리가 2인 경우는 3과 교환이 가능하기 때문에 2가지 경우가 나오고, 1인경우는 3과 교환이 불가능 하여 끝에 3이 붙는 하나의 경우만 나온다. 끝이 2 인 경우: (1*2)/2 + 1 = 2끝이 2 이 아닌 경우: (1*2)/2 = 1좌석이 3개인 경우 3가지 종류가 가능1, 2 -> 1, 2, 3 1, 3, 22, 1 -> 2, 1, 3좌석이 4개일때는 좌석이 3개인 경우에서 끝자리가 3인 경우는 4와 교환이 가능하기 때문에 4가지 경우가 나오고, 2인 경우는 4와 교환이 불가능하이 끝에 4가 붙는 .. 2017. 4. 11.
[알고리즘] 알고리즘 강좌 자료와 온라인 문제 사이트 정보 올림피아드나 알고리즘 공부를 위해서 보면 좋을 교육 자료 모음 문제해결을 위한 창의적 알고리즘 KOI 교육교재(초급)문제해결을 위한 창의적 알고리즘 KOI 교육교재(중급)문제해결을 위한 창의적 알고리즘 KOI 교육교재(고급) 바로가기 -> https://www.digitalculture.or.kr/koi/StudyOnline.do# 소프트웨어 중심사회(http://www.software.kr/um/main.do)- 소프트웨어 관련 진로 정보- 각종 정부 시책 정보- 알고리즘 교육 정보 제가 주로 사용하는 사이트는 백준과 정올이다. 백준은 문제를 풀다가 질문에서 문제 풀이에 대한 힌트를 얻을 수 있다.정올은 틀리면 해당 테스트 케이스를 알려주기 때문에 도움이 된다. 백준, 정올에 동일한 문제가 있기 .. 2017. 1. 17.
[정올][백트래킹] 1027 좋은 수열 숫자를 1, 2, 3 으로 문자열에 하나씩 붙여 가면서문자열의 길이를 반으로 나눠서 확인할 수 있는 가장 긴 길이부터 1개까지 확인하여 좋은 수열인지 확인한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=306&sca=3030 2016. 10. 9.

티스토리툴바