Software Engineering Note

문제: MAXSUM / 구현 역시나 모든 경우를 다 해보면 TLE가 난다. 입력 크기 때문에 O(n^2)도 안될 듯하다. 입력으로 들어올 때 loop 한번에 해결해야 한다. 삽질 몇 번 해보고 나서 어떤 사실을 알게 되었다. 1) 음수가 부분합에 포함되어도 합한 값이 양수면 어쨌든 나중에 도움이 될 수도 있다. 그러나 음수면 도움이 안된다.2) 양수들만 모여있는 부분합이 최대 값이 될 수도 있다. 위의 두 가지를 고려해서 변수를 두 개 잡아서 해결했다. 현재 자신보다 커지는 경우만 선택하는 greedy 한놈, 합한 값이 양수면 안가리고 선택하는 any 한놈.[출처] [AOJ 문제] 최대 연속 부분합 찾기|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/m..

문제: BRUTEFORCE / 분할정복 [해결책 / 후기] 무척 고생한 문제다. 어떤 사람들은 바로 해결전략이 떠오르겠지만 머리가 별로 안좋은 난..쿨럭~ 1. 정답 파악 풀이 방법과 상관없이 정답이 무엇인지 따져본다. N=10일 때 한자리 암호를 만드는 방법은 10가지이다. 2자리 암호를 만드는 방법은, 첫 자리에 10가지가 있고 둘 째 자리에도 10자리가 올 수 있으므로 총 100가지가 된다. 그렇다면 이것은 중복순열? 정답인 즉, N+N^(A+1)+N^(A+2) .... N^B 가 된다. 2. 풀이법에 대한 고찰 이제 정답은 알았다. 그런데 풀이법이 만만찮다. (1) 일단 본능적으로 pow 함수를 쓰면 된다는 생각이 든다. pow(N, A)+pow(N, A+1)+pow(N, A+2) ... 더 효율..

문제: DECODE / 구현 후기 - 이것도 고전.. 알고리즘은 빨리 나왔는데 의외의 착오를... Encoding 문제와 짝을 이룬다. 해결전략 - 2차원 배열을 만들어서 spiral 형태로 순회. (하나는 진행방향 파악을 위한 배열, 다른 하나는 데이터 저장을 위한 배열) 1) 입력받은 binary string을 2차원 배열에 행으로 끊어서 저장한다. 2) spiral 형태로 순회 하면서 5개씩 끊어 문자로 decoding한다. 3) decoding 결과를 문자열로 저장한다. ※ 문제에서 아래 부분을 꼭 고려해야 한다. You should throw away any trailing spaces and/or partial characters found while decoding.[출처] [AOJ 문제] ..