Software Engineering Note

문제: ORDERING / 그래프 [해결책 / 후기] 유명한 문제인 것 같다. 위상정렬이라는 것도 처음 알게 되었다. 내용은 일의 순서를 정하는 것. 문제 해결을 위해서 반드시 위상정렬을 이용해야 하는건 아닌 듯하다. 다음과 깉이 생각해볼 수 있겠다. 1. 작업을 그래프로 추상화 * 각 작업은 그래프에서 하나의 정점(vertice)이 된다. * 작업 A를 마치고 B를 한다는 것은 A에서 B로 가는 간선(edge)을 긋는 것이다.* 이때 B의 입력차수는 1증가 한다. 입력 차수가 있다는 것은 이전에 처리해야할 작업이 있음을 의미한다. 2. 작업 순서 (1) 정점 사이에 간선을 긋는다.(2) 입력 차수가 0인 작업들을 "우선순위 큐"에 넣는다. 그냥 큐를 사용하면 오답이 되는데, 문제에 "사전순"이라는 조건..

문제: 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 문제] ..

문제: ENCODING / 구현 후기 - 의외의 실수로 엄청나게 고전한 문제.. 입력에 문제가 있을수도 있다.- 문자열을 입력 받을 때 입력이 제대로 되는지 확인할 것. 문자열 크기를 충분히 크게 잡을 것. 해결전략 - 2차원 배열을 만들어서 spiral 형태로 순회 1) 입력받은 문자열을 2진수로 encoding한다. 2) encoding된 문자열을 2차원 배열에 spiral 형태로 저장한다.3) 2차원 배열에 저장된 내용을 한 행씩 output 문자열에 복사한다.[출처] [AOJ 문제] Encoding|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/master/IMPL/ENCODING.cpp

문제: CONVERT / 구현 그냥 구현하면 됨.. 코드: https://github.com/xgate/algospot/blob/master/IMPL/CONVERT.cpp

문제: DIAMONDPATH / 동적계획법(DP) 해결전략 시작점부터 계속해서 최대값을 유지해나간다. 최종 값이 최대값이 되려면 그 이전 단계까지의 값도 최대 값이 되어야 한다. 1) 1~5단계가 있다고 하면 일단 1->2단계로 가는 최대 값을 구한다. 2) 다음 2->3단계로 가는 최대 값을 구한다. 이런 식으로 5단계까지 간다. 코드: https://github.com/xgate/algospot/blob/master/DP/DIAMONDPATH.cpp

문제: COIINS / 동적계획법 (DP) [ 해결전략 ] 10, 50, 100원으로 110원을 만드는 경우를 생각해보자. 10x1110x5+50x150x210x1+100x1 이렇게 네 가지 경우이다. 더 작게 생각해보면 50원을 만들 수 있는 방법은 2가지 (10x5, 50원 자기자신) 이다. 여기서 어렵게 느껴지는 부분은 모든 경우의 수를 다 고려해야 한다는 점이다. 즉, 10원을 한 번 사용해보고(10원), 두 번 사용해보고(20원), 세 번 사용해보고(30원)... 만드려는 금액이 110원보다 작은 범위에서 모든 조합을 시도해봐야 한다. 동전의 종류가 많아진다면? 일일이 조합해서 카운트 하는 방법으로는 문제를 해결할 수 없다. 여기서 어떤 사실을 고려해야 하는지 생각해보면 실마리를 잡을 수 있다...

문제: ENDIANS / 구현 해결전략. - 1byte씩 읽어서 메모리에 값을 역으로 저장한다. 1) 입력 값이 저장된 변수의 주소+3위치로 이동한다. 1byte 단위로 이동을 위해 char형 포인터로 변환한다. 2) 결과값을 저장할 변수의 주소로 이동한다. 역시 char형 포인터로 변환. 3) 입력 값 변수의 주소 값은 감소, 결과 값 변수의 주소 값은 증가 하며 메모리 복사.[출처] [AOJ 문제] Endians|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/master/IMPL/ENDIANS.cpp

문제: NQUEEN / 조합탐색 해결전략 1. 이중배열 이용[출처] [AOJ 문제] N-Queen|작성자 DevMoon 1) 퀸을 놓기전에 상, 좌상, 우상 방향에 퀸이 있는지 검사한다. 2) 있으면 다른 칸에 놓는 것을 시도하고, 없으면 그 자리에 놓는다. 3) 다음 퀸을 놓기위해 재귀함수를 호출한다.[출처] [AOJ 문제] N-Queen|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/master/SEARCH/NQUEEN1.cpp 해결전략 2. bit 연산 이용 1) queen의 위치를 bit로 표현한다. 2) 위의 행에 있는 queen과 겹치는지 bit 연산을 이용해서 판단한다. 3) 다음 퀸을 놓기위해 재귀함수를 호출한다.[출처] [AOJ 문제] ..