Software Engineering Note

문제: PI / 동적계획법 원주율을 외운다는 스토리는 뒤로하고 문제의 핵심은 끊어읽는 모든 경우를 어떻게 처리해야할까? 이다. 어떻게 돌아가는지 좀 써보자. 앞에서부터 3을 끊고, 나머지 처리앞에서부터 4를 끊고, 나머지 처리앞에서부터 5를 끊고, 나머지 처리 뒷 부분, 나머지 처리들도 마찬가지로 반복된다. 그런데, 저걸 그때그때 모두 계산하면 너무 오래 걸리잖아? 어차피 중복이 있을 것같단 말이지.. 예를들어 8까지 읽었다고 치자. 그러면 처리:남은길이 = 8:N 이 될텐데, 이 조합으로 access할 경우가 있다는 거다. 그러니까 저런 경우는 한 번 계산한걸 저장해두고 써먹자.. 이렇게 해서 쥐어짠 코드는 다음과 같다. 대충 이런 그림.. int fn(string str) { int minCost =..

문제: MMRECT2 / 구현 MMRECT1 문제랑 똑같은데 점의 갯수가 최대 20,000 개까지 입력될 수 있다. MMRECT1 처럼알고리즘으로 풀면 TLE를 면치 못하겠다. 해서, 메모리를 좀 이용하기로 했다. 해결전략 1. x좌표가 같은 점들을 한 곳에 모아놓는다. (map)2. 루프를 돌면서 입력된 점을 하나씩 꺼내고, map에서 좌표리스트를 꺼낸다.3. 좌표리스트를 돌면서 다음을 수행 (정사각형의 조건을 생각해보자)- x좌표는 어차피 같으니까 y 차이를 구한다. (=dist)- 좌표 p1, p2에서 같은 방향으로 dist만큼 떨어진 점이 있는지 찾아본다.- 예를 들어, y 값이 2 차이나면 두 점의 왼쪽에 2만큼 떨어진 곳에 점이 있거나, 오른쪽으로 2만큼 떨어진 곳에 점이 있어야한다.4. 정사..

문제: MMRECT1 / 구현 문제를 처음 보고 "좌표를 어떻게 표현해야 할까?" 하는 고민.. -10000 ~ 10000 범위를 모두 표현하기는 불가능해보인다. 점의 갯수가 50개 이하니까 입력된 점을 체크해보는 방식이 합리적으로 보인다. 정사각형의 특징을 이용하면 빨리 풀 수 있을 듯 해결전략 1. 시작점 하나를 선택2. x는 같은데 y좌표가 다른 점을 찾는다. 그리고 거리(=dist)를 구한다.3. y는 같으면서, x가 dist만큼 떨어진 점을 찾는다.4. 2에서 구한 점의 y 좌표와, 3에서 구한 점의 x 좌표를 값으로 갖는 점이 존재하는지 체크하고 최소/최대값 갱신 코드: https://github.com/xgate/algospot/blob/master/IMPL/MMRECT1.cpp

문제: FIXPAREN / 구현, 자료구조 잘못 매칭된 괄호를 수정하는 문제. 괄호마다 우선순위가 있고, 잘못된 매칭인 경우 우선순위가 높은 괄호로 변환해야 한다. 스택에 무조건 쌓기만 하고 나중에 빼면 출력 순서가 보장되지 않으므로 임의로 index를 지정할 수 있는 배열을 출력용으로 사용했다. 해결전략 1. 왼쪽 괄호인 경우 스택에 넣는다. 이때, (입력 문자열에서의 위치, 문자) 가 저장되는 정보단위가 된다.2. 오른쪽 괄호인 경우 스택에서 왼쪽괄호를 pop한다. (문제 조건을 읽어보면 오른쪽 괄호전에는 반드시 왼쪽 괄호가 저장됨을 보장할 수 있다.)3. 왼쪽, 오른쪽 우선순위를 비교해서 우선순위가 높은 문자로 변환한다. 그리고 출력용 배열에 저장한다. 코드: https://github.com/xg..

문제: WEEKLYCALENDAR / 구현 1. 달력을 만들고 시작하니 편하다.2. 작년/내년 달력으로 넘어가는 경우를 체크해야 한다. 코드: https://github.com/xgate/algospot/blob/master/IMPL/WEEKLYCALENDAR.cpp

문제: XHAENEUNG / 구현 처음에는 map에다가 넣고 어쩌고 하려다 그냥 무식하게 풀었다. 힌트 - 결국 모든 알파벳이 한 번씩 사용되어야 하므로 정렬하면 비교가 쉬워진다. 코드: https://github.com/xgate/algospot/blob/master/IMPL/XHAENEUNG.cpp

문제: DARPA / 동적계획법, 이진탐색 처음에 greedy로 접근했다가 몇 번 물먹은 문제다. 잊고 지내다가 알고리즘 책(프로그래밍 콘테스트 챌린징)에서 유사한 문제를 보고 다시 도전해서 성공했다. 핵심전략은 다음과 같다. 모든 카메라에 대해, 임의의 두 카메라 간격을 d로 만들 수 있는지 확인한다. 1. d값은 입력으로 주어진 간격의 최대 값부터 시작한다.2. 만약 모든 카메라를 d간격 이상으로 설치할 수 있다면 d값을 늘려서 시도해본다. 왜? 가장 가까운 카메라 간격을 최대화 시켜야 하니까.3. 만약 실패하면 d값을 줄여서 시도해본다. 이렇게 d값을 조절해가면서 범위를 좁혀나간다. 2, 3번 과정에 이진탐색이 적용된다. 2번일 경우 left 값을 mid값으로 한다. 3번일 경우 right 값을 m..

문제: LUCKYNUM / 그리디(탐욕적인 방법) [ 해결책/후기 ] 문제를 보자마자 떠오르는 생각은 주어진 입력으로 구성된 모든 숫자를 만들고 그 숫자 중에서 정답을 찾는 것이다. 그러나 최대 200자리까지 입력되는데 이 방법을 썼다가는 TLE가 뻔하다. OTL 그러니 다른 접근 방법을 찾아야하는데 내가 접근한 방법은 lucky number에 가까운 수를 만들어가는 것이었다. 예를 들면 k=6일때 입력 값 n중에서 6이 입력되었는지 살펴보고 6을 먼저 찜하는 것이다. 이 경우, 첫 자리 수를 6을 선택하면 최선의 선택이 되기때문이다. (6이 또 있으면 역시 다음자리 수로 6을 선택하는 것이 최선이다.) 또 이런 생각도 해볼 수 있다. k=6이고 6은 입력 된 숫자에 없고, 5와 7이 입력값에 있을 경우..

문제: LUNCHBOX / 그리디(탐욕적인 방법) [해결책 / 후기] 힌트 - 먹는 시간이 오래 걸리는 사람을 먼저 처리한다. 입력이 A, B, C, D 네명에 대하여 다음과 같을 때 M: 4 2 6 1 E: 5 2 2 1 아래와 같이 시간 흐름을 그려보니 문제가 좀 명확해졌다. (총 14분의 시간이 걸림) 빨간 숫자는 식사가 끝나는 시간을 나타낸다. 1) 먹는 시간이 오래걸리는 사람 기준으로 내림차순으로 정렬하고 2) 전자렌지가 사용가능한 시점을 기준으로 시간을 측정하였다. 코드: https://github.com/xgate/algospot/blob/master/GREEDY/LUNCHBOX.cpp[출처] [AOJ 문제] Microwaving Lunch Boxes|작성자 DevMoon

문제: REPEATLESS / 경우의 수 [해결책 / 후기] 제한 시간이 10000ms(10초)라고 해서 만만하게 볼 문제가 아니었다. 처음에는 모든 수에 대해서 중복되는 수로 구성되어 있는지를 조사하였지만 여지없이 TLE .. OTL 그러다 해결책이 떠올랐다. 이 문제는, 10개의 숫자 중 n개의 수를 중복 없이 뽑는 문제와 비슷해보인다. (순열..!!) nPr = n! / (n-k)! (n개의 수에서 k개를 중복없이 뽑는 경우의 수) 그래서 해결책을 두 부분으로 나눌 수 있었다. 1) 순열을 이용해서 몇 자리 수인지 결정. n번째 수가 2자리 수인가? 3자리수인가?를 결정 하는 것이다.만약 정답이 3자리 수(100 < n < 1000)라면, 이 수는 적어도 10개의 수 중 2개를 뽑는 방법의 가지수보..