본문 바로가기

Algorithm

백준 11049 행렬 곱셈 순서 Java 2019. 8. 13. 동적 프로그래밍에서 유명한 문제인 행렬 곱셈 순서 문제이다. 2018년도에 알고리즘 수업을 들으면서 한 번 봤던 문제인데 이번에 제대로 이해하려고 노력해보니까 정말 헷갈리고 어려웠다.. 행렬 곱셈은 A행렬과 B행렬을 곱하면 A의 행의수 * A의 열의 수 * B의 열의 수 를 곱하면 행렬 곱셈 횟수가 나오게 된다. dp[i][j]에는 i번과 j번의 곱셈 횟수가 저장된다. 예제처럼 3개의 행렬의 곱셈 횟수를 구하는 과정을 보면 0번째 행렬과 1번째 행렬의 곱셈 횟수가 dp[0][1]에 저장되고 1번째 행렬과 2번째 행렬의 곱셈횟수가 dp[1][2]에 저장되고 0번째 행렬과 dp[1][2]와 곱해서 dp[0][2]에 저장되고 2번째 행렬과 dp[0][1]과 곱해서 전에 저장했던 dp[0][2]와 더 작은 값을..
백준 2661 좋은수열 Java 2019. 8. 13. 알고리즘 분류 백트래킹으로 분류되어있는 좋은 수열 문제이다. 내가 헷갈렸던 부분은 수열을 인접한 두 개의 부분 수열을 검사하는 부분이었다. 생각의 폭이 좁아서인지 검사를 앞에서부터 해야 한다고 생각했다. 그래서 방법을 떠올리기가 힘들었다. 하지만 검사할 때 뒤에서부터, 새로 추가된 수부터 검사를 하면 되는 것이었다. 새로 1, 2, 3 중 하나의 수를 추가할 때 앞에 수랑 겹치지 않게 추가하고 뒤에서부터 2개씩, 3개씩.. n/2개씩 검사하면 되는 문제였다. String클래스의 substring메소드를 활용해서 검사했는데 처음엔 무조건 2개씩 검사하므로 k라는 변수에 2를 넣고 substring으로 범위를 설정해서 검사하였고 k를 1씩 늘렸다. 검사는 무조건 길이/2까지 하기 때문에 k가 문자열의 길이/..
백준 9576 책 나눠주기 Java 2019. 8. 13. 그리디로 분류되어있는 문제인 책 나눠주기 이다. 그리디 외에도 네트워크 플로우, 이분 매칭, 최대 유량등 다양한 방법으로 풀 수 있는 문제인 것 같다. 문제의 내용은 책이 1부터 N까지 있다고 할 때 입력받은 a와 b사이에서 책을 하나씩 줄 수 있을 때 M개의 입력받은 a와 b사이에서 최대 몇명에게 책을 줄 수 있는지를 출력하면 되는 문제이다. 어떻게 그리디적으로 풀 수 있을지 고민을 많이 했다. 답은 b순으로 오름차순 정렬하는 것이였다. 입력 받은 a와 b를 배열에 넣어두고 b순으로 오름차순 정렬을 하고 for문을 돌며 각각의 조건대로 a부터 b까지 책이 남아있다면 책을 주면 된다. 생각해보면 앞에서부터 책이 남아있는지 찾으면 b만 오름차순으로 정렬해놓으면 학생들에게 책을 최대로 많이 줄 수 있는 것이..
백준 1005 ACM Craft Java 2019. 8. 13. 백준에서 가장 많이 풀린 문제 중 하나인 ACM Craft이다. 풀어본 사람이 많은 만큼 정답률도 18%로 매우 낮다. 나 또한 위상 정렬에 대해 공부하기 전에 풀려고 시도했다가 처참히 실패한 후 시도했지만 풀지 못한 문제에 오랫동안 묵혀있던 문제이다. 낮은 정답률에 비해 위상 정렬에 대해 알고 있다면 비교적 쉽게 풀 수 있는 문제이다. 위상 정렬은 DAG에서 방향성을 거스르지 않고 정점들을 나열하는 알고리즘이다. DAG는 Direct Acyclic Graph로 사이클 없는 방향 그래프를 말한다. 위상 정렬에 관한 내용은 아래의 링크에서 친절하고 자세히 설명해 준다. https://jason9319.tistory.com/93 이 문제에 적용할 위상 정렬 방법은 indegree의 수를 이용하는 방법이다. ..
백준 2252 줄 세우기 Java 2019. 8. 12. 위상 정렬을 사용해서 풀어야 하는 줄 세우기 문제이다. 위상 정렬은 DAG에서 방향성을 거스르지 않고 정점들을 나열하는 알고리즘이다. DAG는 Direct Acyclic Graph로 사이클 없는 방향 그래프를 말한다. 위상 정렬에 관한 내용은 아래의 링크에서 친절하고 자세히 설명해 준다. https://jason9319.tistory.com/93 Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Directed Acyclic Graph의 줄임말로 직역하자면 사이클이없는 방향(유향) 그래프 정도가 될 것입니.. jason9319.tistory.com 문제의 내용은 두 학생의 번호 A, B..
백준 9375 패션왕 신해빈 Java 2019. 8. 9. 단계별로 풀어보기 -> 수학 3에서 만난 문제인 패션왕 신해빈 문제이다. 문제의 내용은 해빈이가 가진 의상의 이름과 종류가 주어지고 해빈이는 한번 입었던 옷의 조합은 다시 입지 않을 때 해빈이가 알몸이 아닌 상태로 옷을 입을 수 있는 경우의 수를 출력하면 된다. 문제에 의상의 이름과 종류가 주어지는데 의상의 이름은 중복되는 것이 없다고 문제에서 주어졌기 때문에 의상의 이름에 신경을 쓸 필요는 없다. 이 문제에선 경우의 수를 구하는 공식이 있는데 (옷의 종류별 수 +1) * (옷의 종류별 수 +1) *...(옷의 종류별 수 +1) -1이다. 마지막에 -1을 하는 이유는 알몸이 아닌 상태를 제외하기 때문이다. 옷의 종류별 수를 구하기 위해 자료구조로 Map을 사용하여 종류별로 저장하고 종류별 수를 알아내기 ..
백준 11279 최대 힙 Java 2019. 8. 8. 힙 자료구조를 사용해야 하는 최대 힙 문제이다 문제의 내용은 2가지 연산을 지원하는데 0인 경우엔 최대힙에서 가장 윗부분 가장 큰 수를 삭제 후 출력 0이 아닌 경우엔 최대힙에 삽입하는 것이다. 힙 정렬을 배웠지만 힙 정렬은 삽입 없이 삭제 후 다시 힙으로 만들어 주는 과정을 반복하지 삽입과 삭제를 따로 구현하지 않아서 힙에서 삽입과 삭제를 따로 구현하려니까 생각대로 잘 안됐다. 코드를 천천히 살펴보면서 꼭 복습해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..
백준 14888 연산자 끼워넣기 Java 2019. 8. 7. 단계별로 풀어보기 -> 백트래킹에 있는 있는 문제이며 삼성 SW 역량테스트 기출문제 이기도 한 연산자 끼워넣기 문제이다. 한 번에 맞히긴 했지만 다른 분들의 소스와 시간 차이가 너무 많이 나서 내가 한 방법과 그들의 방법을 비교하며 정리하고자 한다. 문제의 내용은 N개의 수가 주어지고 더하기, 빼기, 곱하기, 나누기 순으로 몇 개를 사용할 수 있는지가 주어진다. N개의 수의 순서는 변하지 않는다. 연산자를 끼워넣어서 만들 수 있는 최댓값과 최솟값을 출력하면 되는 문제이다. 내가 한 방법은 만들 수 있는 연산자의 모든 경우를 백트래킹으로 탐색해서 연산자의 길이가 N-1이면 직접 계산해서 최댓값과 최솟값을 구했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2..

티스토리툴바