분류 전체보기

안녕하세요. 주인장입니다. 오늘은 "차이를 최대로"라는 문제를 풀어볼건데요. 일단 제 생각의 흐름대로 (즉, 삽질 한대로 포스팅을 해보려고 합니다. ) 전 이 차이를 최대로 문제가 최대수 - 최소수를 빼면 된다고 생각했습니다. 그러면 max값 구하기에 수월하다고 생각했는데요. 그래서 일단 수를 받은뒤에 정렬을 해서 최소와 최대를 정렬을 하고 새로운 배열에 제일 최대수 제일 최소수 그다음 최대수 그다음 최소수.... 방식을 취하면 된다고 생각했습니다. 근데 딱히 좋은 방법은 방법은 아니였죠. 이러면 이 최대 합이 56이 나오게 됩니다. 왜냐하면 이방식은 뭔지는 모르겠지만 (즉, n개수가 많아져서 정확하게 뭐가 뭔지 파악하긴 어렵지만.) 62가 나오는 경우가 아니게 되므로, 이방식으로 풀면 안되는 것이죠. ..

안녕하세요 . 백준 문제풀이겸 해설을 맡은 주인장입니다.저는 문제를 풀때 꼬리를 물면서 풀기를 좋아합니다. 그래서 DFS와 BFS를 배울때 문제를 풀면서 같이 적용하는 것을 꽤 좋아합니다. DFS와 BFS는 자료를 탐색할때 사용하는 방법으로 자료 탐색시 노드에따라서 어떤식으로 찾을지에 대해서 방식이라고 생각하면 됩니다. 일단 DFS와 BFS를 알기전에 (물론 몰라도 적용은 가능한게 있지만, 그래도 연계해서 알면 좋습니다.) 먼저 익혀야할 개념은 그래프입니다. 그래프는 사실 트리와 DFS와 같은 탐색문제들에 자주 빈번하게 나오는 문제입니다. 그래서 가장 쉬운 이문제를 통해서 두가지 개념을 동시에 알아 보겠습니다.(단, 이문제에 적용하는 것이지 고급개념에는 적용하기 어려울 수 있으니 차후에 제가 따로 그래프..

간간히 올리는 백준해설 문제를 진행하려고 합니다. 틈틈히 제가 좀 정리가 필요한 경우, 이런식으로 블로그에 정리를 해서 올리겠습니다. 문제는 조세퍼스 순열을 구하는 문제로, 순번 찾기 즉, 수건돌리기처럼 제 순번에 잘 튀어 나오는 게 핵심입니다. 그럼 잘 구하면 되는데, 뭐가 문제냐면, 그 순번이 끝지점에 갔을때 원래 위치로 돌아와야하는데, 그게 잘 안됩니다. ㅂㄷㅂㄷ... 즉, 원래 순번으로 다시 돌아오게끔 해주는 작업을 해야한다는 것이죠. 일단, 저는 무식한 방법(Brutal Force)를 이용해서 한번 다 때려 보기로했습니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main ..

프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (속칭 종만북) 8단원의 동적 계획법(Dynamic Programming) 첫문제 알고스팟에서는 ID: JumpGame으로 찾으면 나오는 문제이다. https://algospot.com/judge/problem/read/JUMPGAME 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다. 균형을 잃어서 다른 ..