분류 전체보기
-
[백준 2468] - [DFS BFS] - 안전영역 (JAVA)알고리즘/BFS_DFS 2018. 12. 27. 18:17
문제 링크 : https://www.acmicpc.net/problem/2468 이 문제는 정말 분노를 유발하는 문제였다. 일단 문제를 풀기에 앞서 이문제를 풀기전에 꼭 명심해야할 사항을 먼저 적고 시작하겠다. 각 영역의 높이를 기준으로 문제를 풀면 틀린다. 비가 안왔을 경우에 대해서도 처리를 해야한다. 위의 말이 무엇인지는 문제를 풀다보면 이해가 저절로 갈것이라 생각한다. 계속 문제가 틀렸다 나오길래 멘탈이 무너진 상태에서 질문 검색을 통해 확인해보니 비가 온 높이로 잠기는 안전영역을 확인하는것이었다. 안전 영역 자체의 높이로만 DFS 혹은 BFS 탐색을 돌리면 비가 안왔을 경우인 비의 높이 0 에대해서 대응을 하지 못하기 때문에 계속 틀리다는 결과를 받았다. 문제가 매우 모호한 문제이기에 이 문제를 ..
-
[백준 10610] - [그리디알고리즘] - 30 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 16:24
문제 링크 : https://www.acmicpc.net/problem/10610 이 문제는 그리디 알고리즘 문제 중에서 어려운 편에 속하는 문제이다. 문제 자체에 오해 할 수 있는 요소가 존재해서 다들 잘못 이해 하고 접근하다가 계속 틀리다는 결과를 받는거 같다. N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 입력값 은 최대 10^5 의 숫자라고 하는게 100000 까지 입력을 받는게 아니라 자리수가 10^5개라는 말이었다. 대부분의 사람들도 100000 까지만 입력 받는걸로 이해하고 문제를 접근해서 고생을 한 거 같다. 정수형 타입인 int 나 실수형 타입인 long 이나 10^5개의 자리수를 입력 받을 수 있는 자료형은 없다. 그럼 어떻게 문제를 풀어야 할..
-
[백준 5585] - [그리디알고리즘] - 거스름돈 (JAVA)알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 12. 27. 14:46
문제 링크 : https://www.acmicpc.net/problem/5585 이문제는 어렵지 않은 그리디 알고리즘 문제이다. 그리디 알고리즘 이란 탐욕적 알고리즘으로 모든 경우의 수를 다 구하면 된다. 거스름돈을 구하는 경우는 아주 쉬운 예제 인데 접근 법은 남은 잔액에서 금액이 큰 동전부터 지급 가능한 개수를 구해나가면 된다. 예제로 380원이 물건 값이 나왔고 1000엔을 받았을때 620원을 거스름돈으로 지불해야 한다. 지불 할 수 있는 동전은 500, 100, 50, 10, 5, 1 엔 총 6가지의 동전이 존재한다. 최소의 개수로 거스름돈을 지불 하고자 한다면 금액이 큰 동전 위주로 지불해주면 되기 때문에 금액이 큰 500엔 부터 줄 수 있는 경우의 수를 구한다. 1) 500엔 으로 지불 가능한..
-
[백준 2156] - [다이나믹프로그래밍] - 포도주 시식 (JAVA)알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 12. 27. 13:33
문제 링크 : https://www.acmicpc.net/problem/2156 이 문제는 다이나믹 프로그래밍 (DP) 으로 접근 하면 된다. 다이나믹 프로그래밍에서 제일 중요한건 점화식이다. 같은 규칙으로 계산이 되고 그 규칙을 찾고 찾은 규칙에서 점화식을 구하면 문제는 아주 쉽게 풀린다. 모든 DP 문제는 점화식 구하는게 일이다. 이 문제에서 제공하는 조건은 두가지가 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 일단 첫번째 조건은 한 잔에 들어 있는 포도주를 찔끔찔끔 마실수 없다는걸 말하는 거고 두번째 조건은 연속으로 3잔을 마실수 없다는걸 말한다. 이 두번째 조건이 점화식을 구..
-
[백준 1799] - [백트래킹] - 비숍 (JAVA)알고리즘/백트래킹 2018. 12. 26. 17:13
문제 링크 : https://www.acmicpc.net/problem/1799이 문제는 이전에 풀었던 N-Queen 문제의 확장판 문제이다. 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen 그리고 백트래킹 문제의 최고존엄 문제 급이지 않을까 생각한다. 이 문제를 잘못 접근하게 되면 문제는 풀겠지만 시간 초과에 걸리게 된다. 잘못접근하는 대부분의 이슈는 하나의 체스판을 전체 탐색을 할경우 생기게 된다. 비숍은 대각선으로 움직인다. 그렇다면 대각선에는 비숍이 위치할 수 없다. 아래처럼 2,2 에 비숍이 위치할 경우 대각선에 위치한 모든 좌표에는 비숍을 놓을 수 없다. B 또 여기서 하나 중요하게 고려해야할게 있는데 2, 2에 비숍을 놓았을경우 비숍의 좌표 기..
-
[백준 2661] - [백트래킹] - 좋은 수열 (JAVA)알고리즘/백트래킹 2018. 12. 26. 16:13
문제링크 : https://www.acmicpc.net/problem/2661 이 문제는 아주 쉽게 백트래킹으로 접근 할 수 있다. 모든 경우의 수를 탐색하면서 조건에 성립되면 결과를 출력하면 된다. 이 문제에서 제시하는 조건은 다음과 같다.임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않아야 한다. (나쁜 수열이면 안된다.)나올 수 있는 좋은 수열 중에서 가장 작은 수를 출력해야 한다. 첫번째 조건을 확인하는 함수 하나를 만들고 두번째 조건은 첫번째로 좋은 수열이 나온 좋은 수열이 제일 작은 수열이기 때문에 좋은 수열이 나오면 모든 탐색을 종료 시키면 되기 때문에 따로 조건을 확인하는 함수를 만들 필요는 없다. 좋은 수열인지 확인하는 함수는 아래와 같이 만들었다. public static bool..
-
[백준 1759] - [백트래킹] - 암호 만들기 (JAVA)알고리즘/백트래킹 2018. 12. 26. 15:19
문제 링크 : https://www.acmicpc.net/problem/1759 이 문제는 백트래킹으로 쉽게 접근 할 수 있다. 이전에 풀었던 백트래킹 문제들을 하나씩 풀어본다면 아주 쉽게 코드를 작성 할 수 있다. 모든 경우에 수를 전부 탐색하면서 문제에서 제시한 3가지 조건을 만족 시키는 경우 생성된 암호를 출력 해주고 다시 다른 경우의 수를 탐색하면 된다. 이전에 풀었던 백트래킹 문제를 기억해가면서 풀어보니 정말 쉽게 문제를 풀 수 있었다. 만약 기억이 안난다면 다른 백트래킹 문제를 풀어보면서 접근해보면 좋을듯 하다. 백트래킹 관련 글 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen2018/11/23 - [알고리즘/백트래킹] - [백준-1987]-[D..
-
[백준 6603] - [백트래킹] - 로또 (JAVA)알고리즘/백트래킹 2018. 12. 26. 14:08
문제 링크 : https://www.acmicpc.net/problem/6603 이 문제는 백트래킹으로 접근 하면 되는 문제다. 백트래킹은 모든 경우의 수를 탐색을 진행 할때 탐색을 한 후에 다시 값을 탐색하기 이전으로 되돌리는 형태의 알고리즘 이다. 이 문제는 그럼 어떻게 접근을 해야 할까? 주어진 k 개의 원소 중에서 하나씩 뽑아서 로또 번호를 생성하면 된다. 한번 로또 번호에 사용된 원소는 다시 사용 될 수 없기 때문에 i 번째 원소가 로또 번호로 생성 됐다면 그 다음 로또번호는 i+1 부터 k-1 번 째 원소가 될 수 있다. 예를 들어 k 는 7 이고 원소들의 집합으로 {1, 2, 3, 4, 5, 6, 7} 을 입력 받은 상태에서 { 1, 2, 3} 까지 로또 번호를 생성 했다면 그 다음 로또 번..