알고리즘/백준 알고리즘
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
2020.02.18안녕하세요. 오늘 풀어볼문제는 백준 다리 놓기입니다. 이 문제는 다이나믹 프로그래밍 혹은 조합으로 문제를 푸는 문제입니다. https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 일단 이문제에서 결국 포인트로 잡아야하는 부분은 얼만큼 최대한 많은 여러가지의 경우의 수를 체크할 수 있냐라는 포인트입니다. 예시를 들어서 설명해보겠습니다. 한점에서 3점으로 만들 수 있는 경우의 수는 3가지입니다. 근데 저희가 문제가 되는 것은 N개의 점일때 M개의 점을 따..
[백준 - 12790번] Mini Fantasy War - 자바(JAVA) 정리 및 해설
[백준 - 12790번] Mini Fantasy War - 자바(JAVA) 정리 및 해설
2019.09.27안녕하세요. 이번 문제는 구현 문제인 Mini Fantasy War를 풀어보겠습니다. 이문제는 구현 문제인데, 개인적인 생각을 정리하기 위해서 적습니다. 구현 문제에서는 코드를 얼마나 줄일수있냐가 문제를 빠르게 풀 수 있는 지를 가르는 척도라고 생각합니다. 즉, 체력, 마력, 공격력, 방어력을 함수처리를 해버리는 걸로 문제 해결을 편하게 할 수 있습니다. Main문에 여러가지 코드를 넣는 것보단 외부에 함수를 만들어서 한번에 처리하는 것이 나중에 코드를 고치거나 오류점을 찾아내기가 편할 겁니다. /** 2019. 9. 23. */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
[백준 - 5585번] 거스름돈 - JAVA 정리 및 해설
[백준 - 5585번] 거스름돈 - JAVA 정리 및 해설
2019.09.27안녕하세요. 오늘 풀어볼 문제는 거스름돈입니다. 이 문제는 그리디 방식의 문제입니다. https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 거스름돈의 경우는 구현 문제라고 해서 문제를 풀었습..
[백준 - 1912번] 연속합- JAVA 정리 및 해설
[백준 - 1912번] 연속합- JAVA 정리 및 해설
2019.07.13안녕하세요. 오늘 풀어 볼 문제는 연속합입니다. 연속합은 Dynamic Programming을 이용한 문제입니다. 연속합은 연속된 수중에서 가장 큰 합을 구하는 문제이기 때문에 수열마다 연속적으로 수를 더해가면서 그합이 가장 큰 경우를 찾으면 된다고 생각해서 문제를 이런식으로 풀 수도 있습니다. 수열에서 n번째 수부터 마지막까지 연속적으로 더해가면서 가장 큰 수를 cache[n]에 저장하고 그 cache배열에서 가장 큰수를 더해가는 방식으로 문제를 풀었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..
[백준 - 2579번] 계단오르기 - 자바(JAVA) 정리 및 해설
[백준 - 2579번] 계단오르기 - 자바(JAVA) 정리 및 해설
2019.03.13오늘은 대표적 DP(Dynamic Programming)문제인 계단오르기를 보겠습니다. Dynamic Programming 초반에 가장 많이 연습하게 되는 문제인 계단오르기는 처음에 접할때는 조금 어렵습니다.. 일단 저는 DP에 대해서 짚고 넘어가야된다고 생각합니다. 우리는 왜 DP를 사용하는 것에 대해서 정확한 인지가 필요하고 이걸 바탕으로 문제를 풀어보도록하겠습니다. DP는 기본적으로 중복으로 여러번 계산하는 것을 막기위해서 고안된 방법입니다. 개념이 길긴하지만, 간단하게 쉬운 사례를 들면. 파스칼의 삼각형을 생각해보면 쉬운데 파스칼의 삼각형은 이항계수의 앞의 계수를 구할때 사용하는 방법인데, 이게 삼각형의 모양을 띄고 있다보니, 중복되는 경우가 발생합니다. 그래서 이경우 재귀적(재귀인지 혹은 For..
[백준 - 2292번] 벌집 - 자바(JAVA) 정리 및 해설
[백준 - 2292번] 벌집 - 자바(JAVA) 정리 및 해설
2019.03.06안녕하세요. 오늘 풀어볼 문제는 벌집입니다. 벌집은 단순히 수학적 공식으로도 풀수 있는 문제이지만, (결국 그게 수학적인 규칙성을 찾아서 공식화 시킨거긴 하지만.) 그 공식 과정을 직접 일일히 대조하는 방식으로 진행했습니다.저는 일단 인접한 방들을 기점삼아서 즉 2~7까지 인접해 있는 수들의 규칙성을 확인해보는 식으로 수를 만들어 갔습니다.첫번째 1을 거쳐서 방을 지나가기때문에 다음 방은 2일것이니N =2 2, 3, 4, 5, 6, 7 N=3 9, 11, 13, 15, 17, 19N=4 22, 25, 28, 31, 34, 37..... 계속 이런식으로 진행하게 될것입니다. 그 그림들로 보시면 N은 각 방을 지나서 갈수 있는 곳이고, 그 수에 있는 수들이 색깔별로 늘어나가는 숫자라고 생각하면 됩니다. 근데..
[백준 - 3055번] 탈출 - 자바(JAVA) 정리 및 해설
[백준 - 3055번] 탈출 - 자바(JAVA) 정리 및 해설
2019.02.17이번 문제 탈출은 두 개포인트에서 시작하는 BFS를 다루는 문제입니다. 동시간에 두가지 곳에서 동시에 퍼져나가는 경우에는 BFS를 사용합니다. 이렇게 풀지 않으면 안풀리는 경우가 많은데요. 어차피 같은 시간에 같은 공간에서 같은 회차로 움직여야하기때문에, 그런것을 감안을 해서 문제를 풀어야합니다.그럼 문제를 풀어가는 논리적인 구성을 생각해봅시다. 1. 일단 이문제는 BFS를 풀어야한다는 사실을 알았고, 미로찾기와 같은 x,y를 동시에 queue안에 넣어야합니다. 물론, 두 queue를 이용해서 사용할 수 있지만, 저는 혹시 모를 상황을 대비(그렇게 된 경우는 적으나, 두 큐에 넣었을때 같은 순서로 되지 않을 경우가 있을 수도? 있을 것같아서 저는 적어도 두 인수를 가진 상황이면 그냥 묶어서 집어넣습니다...
[백준 - 7576번] 토마토 - 자바(JAVA) 정리 및 해설
[백준 - 7576번] 토마토 - 자바(JAVA) 정리 및 해설
2019.02.08이번시간에는 토마토 BFS 문제에 대해서 풀어보도록 하겠습니다.이 문제는 익은 토마토가 옆의 토마토를 다음날에 익게 만들고 그 일수를 구해야하는 대표적인 문제입니다.그럼 이 일수를 구하는데 가장 유요한 코딩전략은 BFS입니다. 왜냐하면 한박스 내에 몇개의 익은 토마토가 있는지 모르기 때문에, 1일당 각각의 익은 토마토별로 안익은 토마토를 익게 만들어야합니다. 그렇다면 dfs로 구현하기에는 어렵기때문에 BFS를 사용해서 문제를 풀어야하겠죠. 이미 다익은 경우와 못익히는 경우에는 출력을 다르게 해줘야하지만, 그렇게 어렵지 않으니 바로 설명해보죠.1. 토마토처럼 x,y좌표를 통해서 위치를 판단하는 경우에는 두가지 인수를 동시에 움직여야합니다.BFS의 경우 Queue 안에 넣어야하는데요. 물론 x값과 y값을 두..
[백준 - 9461번] 파도반 수열 - JAVA 정리 및 해설
[백준 - 9461번] 파도반 수열 - JAVA 정리 및 해설
2019.02.08오늘은 파도반 수열에 대해서 정리해보도록 하겠습니다. 파도반 수열은 두방식으로 둘다 풀리는 문제중 하나입니다. Top-down방식과 Bottom-Up 방식 두 가지로 풀 수 있는 문제입니다. 이런문제에서 주의 해야할 점은 딱 하나 정도인데요. 이 답이 나오는 범위를 체크를 해줘야 한다는 점입니다. N이 여기서는 100까지로 한정되어 있는데 이 범위가 int의 범위를 벗어나는지를 체크를 해보고 넘어가야됩니다.이 문제는 dp중에 점화식을 찾기가 쉬운 문제중 하나입니다. cache[n] = cache[n-1] + cache[n-5]로 범위는 간단합니다. 더 쉽게 생각해보면, p(11)이 나오기 위해서는 -> 12길이짜리 삼각형이 나오기 위해서는 9 삼각형 p(10)과 3 삼각형 p(6) 을 더해서 만들어지니...
[백준 - 2163번] 초콜렛 자르기 - JAVA 정리 및 해설 (DP방식)
[백준 - 2163번] 초콜렛 자르기 - JAVA 정리 및 해설 (DP방식)
2019.02.08백준 2163번 초콜렛 자르기를 풀어보도록 하겠습니다. 초콜렛 자르기는 사실 쉽게 접근할 수 있습니다. 그저 N*M -1 의 방식으로 푸는게 훨씬 쉽게 풀 수 있는데요.(ㅂㄷㅂㄷ) 저는 이문제의 하단에 보면, 알고리즘 분류의 수학과 "다이나믹 프로그래밍"에 낚여서 이걸 진짜 다이나믹 프로그래밍으로만 생각했습니다. 왜그랬을까요... 덕분에 잠도 못자고 이거 생각해봤네요. 암튼 덕분에 다이나믹 프로그래밍으로도 문제를 풀어서 맞춰서 여기에 어떤 방식으로 풀었는지에 대해서 설명을 해보려합니다. 제가 말하는 cache[][]는 여러분들이 dp[][]로 쓰는 중복 체크를 하기위해 쓴 배열이라고 생각해주시면 됩니다. 0. 가장 중요한건 cache를 -1로 모두 채우고 시작하는 작업이 필요합니다. 1. 일단 우리가 기..
백준 답안 공유 - 백준알고리즘
백준 답안 공유 - 백준알고리즘
2019.01.29제가 풀었던 문제들은 따로 제 github에 올려두었습니다. 대부분의 문제들은 JAVA로 풀었습니다.간혹 안풀려져있고, 문제만 떨렁 놓여져있는 경우가 있을 겁니다. 그럴경우에는 깃허브 커밋 남겨주시면 최대한 풀어서 올려보도록 하겠습니다. 아직 많이 부족합니다. 열심히 공부해서 여러가지 문제를 풀 수 있는 날이 올때까지 고생좀 해보겠습니다.아래는 주소입니다.https://github.com/ventulus95/BaekjoonAnswer 쉬운 문제들은 파일을 만들지 않고, 직접 사이트에서 풀었습니다. 백준에서 @ventulus95을 찾아주시면 올라가지 않았던 문제들도 확인 하실 수 있을 겁니다. 18년도 12월 말과 1월초에 푼 문제들은 위에 언제 풀었는지가 적혀있습니다.
[백준 - 1436번] 영화감독 숌 - JAVA 정리 및 해설
[백준 - 1436번] 영화감독 숌 - JAVA 정리 및 해설
2019.01.05안녕하세요. 영화감독 숌에 대해서 정리와 해설을 해보겠습니다. 사실 처음에 볼때는 일정한 규칙을 만들어서 생각해보는 문제라고 생각했으나, 그냥 일일히 컴퓨터에 돌려도 되는 브루트포스(brutal force)문제입니다. 문제 링크: https://www.acmicpc.net/problem/1436 처음에 접근할때는 이문제를 그저 규칙찾아서 규칙만들고, 문제를 풀면 된다고 생각했는데... 틀리고난 다음에 이것이 브루트포스라는 것을 확인했습니다. 일단 규칙만드는게 안되는게 일단 규칙이 상당히 까다롭고 상황마다 경우가 달라질 수 도 있기때문에 규칙을 세워서 하는 방식은 빠르게 접었습니다. 그러면 브루트포스 방식은 직접 666이 들어가는 수를 찾아서 해결하는 것입니다. 즉, 숫자를 늘려가면서 연속된 666을 찾는..