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