알고리즘
[백준 - 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을 찾는..
[백준 -1181번] 단어정렬 - JAVA 정리 및 해설
[백준 -1181번] 단어정렬 - JAVA 정리 및 해설
2019.01.05안녕하세요. 오늘은 단어 정렬과 그 속에 체크할 점을 짚고 넘어가겠습니다.단어정렬 이문제는 그렇게 어려운 문제는 아닙니다. 기본적으로 정렬이라는 간단한 알고리즘을 통해서 문제를 풀어 내면 됩니다. 문제링크: https://www.acmicpc.net/problem/1181 자바에서 여러가지 조건을 동시에 만족하는 정렬을 사용할때는 Comparator를 이용해서 정렬을 사용해야합니다. 문제의 정렬 조건은길이가 짧은 것부터길이가 같으면 사전 순으로 위와 같기때문에 잘 짚고 넘어가야됩니다. 자바에서는 Comparator가 세부적인 정렬 예를들면, 자료 1 자료 2가 있을때 자료 1은 오름차순 자료 2는 내림차순으로 정렬을 해야하는 경우일때 기본정렬로는 해결이 잘 안되기때문에 comparator를 새로 지정해서..
[백준 - 14500번] 테트로미노 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)
[백준 - 14500번] 테트로미노 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)
2018.12.27안녕하세요. 이번에는 저번 삼성 SW 역량테스트 문제들에 하나인 테트로미노를 풀어보겠습니다. https://www.acmicpc.net/problem/14500 문제에 대해서 간략하게 설명해보도록 하죠. 위의 그림에 있는 블럭들을 n*m자리 숫자가 적힌 판에다가 "1개만" 놓고 그 블럭 아래에 적힌 숫자들의 합이 가장 큰 경우를 따져 주는 문제입니다. 조건 중에 약간 까다로운 조건이 하나 있는데 바로 회전이나 대칭을 시켜도 된다. 입니다.이 조건은 결국 우리가 따져야 할 조건이 여러가지가 있다는 사실을 뜻하기도 합니다. 저는 이문제를 보고 고민을 좀 하게된게 이걸 어떤식으로 계산을 해야할까를 고민을 많이 했죠. 도대체 어떤 경우에 이 합이 최대가 되는 경우를 찾을 수 있을까?저는 일단 DFS를 기준 삼아..
[백준 -13458번] 시험감독 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)
[백준 -13458번] 시험감독 - JAVA 정리 및 해설 (삼성 SW 역량테스트 문제)
2018.12.27이번 문제는 삼성 SW 역량 테스트에서 출제한 문제들을 모아서 한번에 정리하려고 합니다.첫번째는 제가 생각하기에는 가장 쉬운 문제인 시험 감독입니다. 올려도 보는 사람은 없겠지만, 삼성문제에 대해서 정리도 필요하고, 한 번쯤은 정리해보는 시간이 필요할 것 같아서 역량테스트 문제끼리 묶어서 같이 공부하려고 시작을 했습니다. https://www.acmicpc.net/problem/13458 이 문제는 사실 특별하게 "구현"을 하지 않아도 답을 대략적으로 유추할 수 있는 계산 값이 나옵니다. 일단 문제의 조건을 확인을 해보죠. 첫째로, 시험 감독은 각 시험 감독이 최대로 볼 수 있는 수험생의 수는 정해져있습니다.둘째로, 시험 총감독은 무조건 한명만 필요하고 부 감독은 여러명이든 없든 상관이 없으니 그 학생의..
[백준 -10819번] 차이를 최대로 - JAVA 정리 및 해설
[백준 -10819번] 차이를 최대로 - JAVA 정리 및 해설
2018.12.09안녕하세요. 주인장입니다. 오늘은 "차이를 최대로"라는 문제를 풀어볼건데요. 일단 제 생각의 흐름대로 (즉, 삽질 한대로 포스팅을 해보려고 합니다. ) 전 이 차이를 최대로 문제가 최대수 - 최소수를 빼면 된다고 생각했습니다. 그러면 max값 구하기에 수월하다고 생각했는데요. 그래서 일단 수를 받은뒤에 정렬을 해서 최소와 최대를 정렬을 하고 새로운 배열에 제일 최대수 제일 최소수 그다음 최대수 그다음 최소수.... 방식을 취하면 된다고 생각했습니다. 근데 딱히 좋은 방법은 방법은 아니였죠. 이러면 이 최대 합이 56이 나오게 됩니다. 왜냐하면 이방식은 뭔지는 모르겠지만 (즉, n개수가 많아져서 정확하게 뭐가 뭔지 파악하긴 어렵지만.) 62가 나오는 경우가 아니게 되므로, 이방식으로 풀면 안되는 것이죠. ..
[백준 -1260번] DFS와 BFS - JAVA 정리 및 해설
[백준 -1260번] DFS와 BFS - JAVA 정리 및 해설
2018.12.06안녕하세요 . 백준 문제풀이겸 해설을 맡은 주인장입니다.저는 문제를 풀때 꼬리를 물면서 풀기를 좋아합니다. 그래서 DFS와 BFS를 배울때 문제를 풀면서 같이 적용하는 것을 꽤 좋아합니다. DFS와 BFS는 자료를 탐색할때 사용하는 방법으로 자료 탐색시 노드에따라서 어떤식으로 찾을지에 대해서 방식이라고 생각하면 됩니다. 일단 DFS와 BFS를 알기전에 (물론 몰라도 적용은 가능한게 있지만, 그래도 연계해서 알면 좋습니다.) 먼저 익혀야할 개념은 그래프입니다. 그래프는 사실 트리와 DFS와 같은 탐색문제들에 자주 빈번하게 나오는 문제입니다. 그래서 가장 쉬운 이문제를 통해서 두가지 개념을 동시에 알아 보겠습니다.(단, 이문제에 적용하는 것이지 고급개념에는 적용하기 어려울 수 있으니 차후에 제가 따로 그래프..
[BOJ - 1158번] 조세퍼스 문제 - JAVA 정리 및 해설
[BOJ - 1158번] 조세퍼스 문제 - JAVA 정리 및 해설
2018.10.11간간히 올리는 백준해설 문제를 진행하려고 합니다. 틈틈히 제가 좀 정리가 필요한 경우, 이런식으로 블로그에 정리를 해서 올리겠습니다. 문제는 조세퍼스 순열을 구하는 문제로, 순번 찾기 즉, 수건돌리기처럼 제 순번에 잘 튀어 나오는 게 핵심입니다. 그럼 잘 구하면 되는데, 뭐가 문제냐면, 그 순번이 끝지점에 갔을때 원래 위치로 돌아와야하는데, 그게 잘 안됩니다. ㅂㄷㅂㄷ... 즉, 원래 순번으로 다시 돌아오게끔 해주는 작업을 해야한다는 것이죠. 일단, 저는 무식한 방법(Brutal Force)를 이용해서 한번 다 때려 보기로했습니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main ..
[JAVA] 알고스팟 외발뛰기 - JUMPGAME 문제 해설.
[JAVA] 알고스팟 외발뛰기 - JUMPGAME 문제 해설.
2018.10.01프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (속칭 종만북) 8단원의 동적 계획법(Dynamic Programming) 첫문제 알고스팟에서는 ID: JumpGame으로 찾으면 나오는 문제이다. https://algospot.com/judge/problem/read/JUMPGAME 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다. 균형을 잃어서 다른 ..