알고리즘 문제해결전략

1. 도입 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있습니다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다. 이 차이점은 아래 그림에서 알 수 있습니다. 첫 번째 그림은 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고 두 번째 그림은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여줍니다. 분할 정..

https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이www.algospot.com  문제를 풀려고 고민을 꽤 오래했지만 결국 풀지못하고 답안 코드를 봤다. 알고 스팟에 답안 제출한 코드는 아래와 같다. import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main { public static int[][][] cov..

https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로www.algospot.com  1. 첫 번째 시도 첫 번째 시도에서는 런타임 에러[RTE (nonzero return code)] 가 나왔다. 아래 소스의 43 라인에서 myFriends.get(studnet1) 의 값이 null 인지 체크해주지 않아서 발생한 문제였다. 문제의 원인을 찾았으니 null 체크 코드를 추가하고 다시 답안을 제출해보았다.import java.util.*;public..

1. 도입 프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽습니다. 이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어봅시다. 무식하게 풀 수 있을까? 흔히 전산학에서 '무식하게 푼다(brute-force)'는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부릅니다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을..

1. 도입 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 합니다. 전 세계 99%의 프로그래머는 알고리즘을 새로 만들기보다 배워서 써먹는 쪽에 지대한 관심을 가지고 있습니다. 그래서 대개 알고리즘의 증명에 관해서는 일찌감치 잊어버리는 게 어떨까 하는 유혹을 받기가 쉽고요. 하지만, 알고리즘의 증명을 이해하지 않고서는 알고리즘을 제대로 공부했다고 할 수 없습니다. 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문입니다. 모든 알고리즘은 사실 치열한 고민과 개선 과정을 거쳐 태어납니다. 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많습니다. 따라서 의사 코드를 달달 외우기만 해서는 알고리즘에 담겨 ..

1. 도입반복문이 지배한다.여기 자동차 두 개가 있습니다. 서울에서 부산까지 서둘러 가야 하는데, 어느 쪽을 타고 가야 더 빨리 도착할 수 있을지를 알고 싶습니다. 다음은 두 자동차에 대한 정보입니다.항목자동차 A자동차 B시동 거는 데 걸리는 시간3분5초문 열었다 닫는 데 걸리는 시간1분0초운전석 등받이 조절에 걸리는 시간5분0초앞 유리 닦는 데 걸리는 시간4분0초최대 시속200km/h40km/h 네, 사실 자동차 B는 자전거입니다. 문이 없으니 문을 열었다 닫을 필요도 없고, 등받이가 없으니 등받이를 조절할 필요도 없지요. 하지만 그렇다고 해서 서울에서 부산까지 자전거를 타는 사람은 아마 별로 없을 겁니다. 자동차에서 더 오래 걸리는 항목들은 출발할 떄 한 번만 적용되는 반면, 최대 시속은 서울에서 부..

1. 실수 자료형의 이해 실수 연산의 어려움아래 코드는 [1, n] 범위의 모든 자연수 중 1/x * x = 1 인 x의 수를 세는 countObvious()의 구현을 보여줍니다. 누가 보더라도 이 식은 항상 성립해야 하니, countObvious(n)을 호출하면 당연히 n이 반환되어야 할 것입니다. 그런데 이 함수를 직접 실행해보면 결과는 그렇지 않다는 것을 알게 됩니다. 대표적으로 제 컴퓨터에서는 countObvious(50) = 48 라고 나옵니다. 설마 우리 프로그램에 버그가 있는 것일까요? 아니면 CPU에 문제가 있는 것일까요? 이 의문을 해결하려면 컴퓨터가 사용하는 실수 표현 방식에 대해 알아야 합니다.// 잘못된 실수 연산의 예제int coundObvious(int n) { int sa..