티스토리

Software Engineering Note

검색하기

블로그 홈

Software Engineering Note

devmoons.tistory.com/m

Software Engineer / Backend/ BigData

구독자: 1

방명록 방문하기

주요 글 목록

원주율 외우기 문제: PI / 동적계획법 원주율을 외운다는 스토리는 뒤로하고 문제의 핵심은 끊어읽는 모든 경우를 어떻게 처리해야할까? 이다. 어떻게 돌아가는지 좀 써보자. 앞에서부터 3을 끊고, 나머지 처리앞에서부터 4를 끊고, 나머지 처리앞에서부터 5를 끊고, 나머지 처리 뒷 부분, 나머지 처리들도 마찬가지로 반복된다. 그런데, 저걸 그때그때 모두 계산하면 너무 오래 걸리잖아? 어차피 중복이 있을 것같단 말이지.. 예를들어 8까지 읽었다고 치자. 그러면 처리:남은길이 = 8:N 이 될텐데, 이 조합으로 access할 경우가 있다는 거다. 그러니까 저런 경우는 한 번 계산한걸 저장해두고 써먹자.. 이렇게 해서 쥐어짠 코드는 다음과 같다. 대충 이런 그림.. int fn(string str) { int minCost =.. 공감수 0 댓글수 0 2015. 6. 28.
최소, 최대 정사각형 찾기 2 문제: MMRECT2 / 구현 MMRECT1 문제랑 똑같은데 점의 갯수가 최대 20,000 개까지 입력될 수 있다. MMRECT1 처럼알고리즘으로 풀면 TLE를 면치 못하겠다. 해서, 메모리를 좀 이용하기로 했다. 해결전략 1. x좌표가 같은 점들을 한 곳에 모아놓는다. (map)2. 루프를 돌면서 입력된 점을 하나씩 꺼내고, map에서 좌표리스트를 꺼낸다.3. 좌표리스트를 돌면서 다음을 수행 (정사각형의 조건을 생각해보자)- x좌표는 어차피 같으니까 y 차이를 구한다. (=dist)- 좌표 p1, p2에서 같은 방향으로 dist만큼 떨어진 점이 있는지 찾아본다.- 예를 들어, y 값이 2 차이나면 두 점의 왼쪽에 2만큼 떨어진 곳에 점이 있거나, 오른쪽으로 2만큼 떨어진 곳에 점이 있어야한다.4. 정사.. 공감수 0 댓글수 0 2015. 1. 3.
최소, 최대 정사각형 찾기 1 문제: 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 공감수 0 댓글수 0 2014. 12. 27.
Mismatched Parenthesis 문제: FIXPAREN / 구현, 자료구조 잘못 매칭된 괄호를 수정하는 문제. 괄호마다 우선순위가 있고, 잘못된 매칭인 경우 우선순위가 높은 괄호로 변환해야 한다. 스택에 무조건 쌓기만 하고 나중에 빼면 출력 순서가 보장되지 않으므로 임의로 index를 지정할 수 있는 배열을 출력용으로 사용했다. 해결전략 1. 왼쪽 괄호인 경우 스택에 넣는다. 이때, (입력 문자열에서의 위치, 문자) 가 저장되는 정보단위가 된다.2. 오른쪽 괄호인 경우 스택에서 왼쪽괄호를 pop한다. (문제 조건을 읽어보면 오른쪽 괄호전에는 반드시 왼쪽 괄호가 저장됨을 보장할 수 있다.)3. 왼쪽, 오른쪽 우선순위를 비교해서 우선순위가 높은 문자로 변환한다. 그리고 출력용 배열에 저장한다. 코드: https://github.com/xg.. 공감수 0 댓글수 0 2014. 9. 21.
Weekly Calendar 문제: WEEKLYCALENDAR / 구현 1. 달력을 만들고 시작하니 편하다.2. 작년/내년 달력으로 넘어가는 경우를 체크해야 한다. 코드: https://github.com/xgate/algospot/blob/master/IMPL/WEEKLYCALENDAR.cpp 공감수 0 댓글수 0 2014. 8. 25.
째능 교육 문제: XHAENEUNG / 구현 처음에는 map에다가 넣고 어쩌고 하려다 그냥 무식하게 풀었다. 힌트 - 결국 모든 알파벳이 한 번씩 사용되어야 하므로 정렬하면 비교가 쉬워진다. 코드: https://github.com/xgate/algospot/blob/master/IMPL/XHAENEUNG.cpp 공감수 0 댓글수 0 2014. 8. 23.
DARPA Grand Challenge 문제: DARPA / 동적계획법, 이진탐색 처음에 greedy로 접근했다가 몇 번 물먹은 문제다. 잊고 지내다가 알고리즘 책(프로그래밍 콘테스트 챌린징)에서 유사한 문제를 보고 다시 도전해서 성공했다. 핵심전략은 다음과 같다. 모든 카메라에 대해, 임의의 두 카메라 간격을 d로 만들 수 있는지 확인한다. 1. d값은 입력으로 주어진 간격의 최대 값부터 시작한다.2. 만약 모든 카메라를 d간격 이상으로 설치할 수 있다면 d값을 늘려서 시도해본다. 왜? 가장 가까운 카메라 간격을 최대화 시켜야 하니까.3. 만약 실패하면 d값을 줄여서 시도해본다. 이렇게 d값을 조절해가면서 범위를 좁혀나간다. 2, 3번 과정에 이진탐색이 적용된다. 2번일 경우 left 값을 mid값으로 한다. 3번일 경우 right 값을 m.. 공감수 0 댓글수 0 2014. 8. 16.
Lucky Lucky Number 문제: LUCKYNUM / 그리디(탐욕적인 방법) [ 해결책/후기 ] 문제를 보자마자 떠오르는 생각은 주어진 입력으로 구성된 모든 숫자를 만들고 그 숫자 중에서 정답을 찾는 것이다. 그러나 최대 200자리까지 입력되는데 이 방법을 썼다가는 TLE가 뻔하다. OTL 그러니 다른 접근 방법을 찾아야하는데 내가 접근한 방법은 lucky number에 가까운 수를 만들어가는 것이었다. 예를 들면 k=6일때 입력 값 n중에서 6이 입력되었는지 살펴보고 6을 먼저 찜하는 것이다. 이 경우, 첫 자리 수를 6을 선택하면 최선의 선택이 되기때문이다. (6이 또 있으면 역시 다음자리 수로 6을 선택하는 것이 최선이다.) 또 이런 생각도 해볼 수 있다. k=6이고 6은 입력 된 숫자에 없고, 5와 7이 입력값에 있을 경우.. 공감수 0 댓글수 0 2014. 8. 16.
Microwaving Lunch Boxes 문제: 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 공감수 0 댓글수 0 2014. 8. 16.
Repeatless Numbers 문제: REPEATLESS / 경우의 수 [해결책 / 후기] 제한 시간이 10000ms(10초)라고 해서 만만하게 볼 문제가 아니었다. 처음에는 모든 수에 대해서 중복되는 수로 구성되어 있는지를 조사하였지만 여지없이 TLE .. OTL 그러다 해결책이 떠올랐다. 이 문제는, 10개의 숫자 중 n개의 수를 중복 없이 뽑는 문제와 비슷해보인다. (순열..!!) nPr = n! / (n-k)! (n개의 수에서 k개를 중복없이 뽑는 경우의 수) 그래서 해결책을 두 부분으로 나눌 수 있었다. 1) 순열을 이용해서 몇 자리 수인지 결정. n번째 수가 2자리 수인가? 3자리수인가?를 결정 하는 것이다.만약 정답이 3자리 수(100 < n < 1000)라면, 이 수는 적어도 10개의 수 중 2개를 뽑는 방법의 가지수보.. 공감수 0 댓글수 0 2014. 8. 16.
할 일 순서 정하기 문제: ORDERING / 그래프 [해결책 / 후기] 유명한 문제인 것 같다. 위상정렬이라는 것도 처음 알게 되었다. 내용은 일의 순서를 정하는 것. 문제 해결을 위해서 반드시 위상정렬을 이용해야 하는건 아닌 듯하다. 다음과 깉이 생각해볼 수 있겠다. 1. 작업을 그래프로 추상화 * 각 작업은 그래프에서 하나의 정점(vertice)이 된다. * 작업 A를 마치고 B를 한다는 것은 A에서 B로 가는 간선(edge)을 긋는 것이다.* 이때 B의 입력차수는 1증가 한다. 입력 차수가 있다는 것은 이전에 처리해야할 작업이 있음을 의미한다. 2. 작업 순서 (1) 정점 사이에 간선을 긋는다.(2) 입력 차수가 0인 작업들을 "우선순위 큐"에 넣는다. 그냥 큐를 사용하면 오답이 되는데, 문제에 "사전순"이라는 조건.. 공감수 0 댓글수 0 2014. 8. 16.
최대 연속 부분합 찾기 문제: MAXSUM / 구현 역시나 모든 경우를 다 해보면 TLE가 난다. 입력 크기 때문에 O(n^2)도 안될 듯하다. 입력으로 들어올 때 loop 한번에 해결해야 한다. 삽질 몇 번 해보고 나서 어떤 사실을 알게 되었다. 1) 음수가 부분합에 포함되어도 합한 값이 양수면 어쨌든 나중에 도움이 될 수도 있다. 그러나 음수면 도움이 안된다.2) 양수들만 모여있는 부분합이 최대 값이 될 수도 있다. 위의 두 가지를 고려해서 변수를 두 개 잡아서 해결했다. 현재 자신보다 커지는 경우만 선택하는 greedy 한놈, 합한 값이 양수면 안가리고 선택하는 any 한놈.[출처] [AOJ 문제] 최대 연속 부분합 찾기|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/m.. 공감수 0 댓글수 0 2014. 8. 16.
Brute-Force Attack 문제: 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) ... 더 효율.. 공감수 0 댓글수 0 2014. 8. 16.
Decoding 문제: 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 문제] .. 공감수 0 댓글수 0 2014. 8. 16.
Encoding 문제: 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 공감수 0 댓글수 0 2014. 8. 16.
Conversions 문제: CONVERT / 구현 그냥 구현하면 됨.. 코드: https://github.com/xgate/algospot/blob/master/IMPL/CONVERT.cpp 공감수 0 댓글수 0 2014. 8. 16.
Best Path On A Diamond 문제: DIAMONDPATH / 동적계획법(DP) 해결전략 시작점부터 계속해서 최대값을 유지해나간다. 최종 값이 최대값이 되려면 그 이전 단계까지의 값도 최대 값이 되어야 한다. 1) 1~5단계가 있다고 하면 일단 1->2단계로 가는 최대 값을 구한다. 2) 다음 2->3단계로 가는 최대 값을 구한다. 이런 식으로 5단계까지 간다. 코드: https://github.com/xgate/algospot/blob/master/DP/DIAMONDPATH.cpp 공감수 0 댓글수 0 2014. 8. 16.
Coin Change 문제: COIINS / 동적계획법 (DP) [ 해결전략 ] 10, 50, 100원으로 110원을 만드는 경우를 생각해보자. 10x1110x5+50x150x210x1+100x1 이렇게 네 가지 경우이다. 더 작게 생각해보면 50원을 만들 수 있는 방법은 2가지 (10x5, 50원 자기자신) 이다. 여기서 어렵게 느껴지는 부분은 모든 경우의 수를 다 고려해야 한다는 점이다. 즉, 10원을 한 번 사용해보고(10원), 두 번 사용해보고(20원), 세 번 사용해보고(30원)... 만드려는 금액이 110원보다 작은 범위에서 모든 조합을 시도해봐야 한다. 동전의 종류가 많아진다면? 일일이 조합해서 카운트 하는 방법으로는 문제를 해결할 수 없다. 여기서 어떤 사실을 고려해야 하는지 생각해보면 실마리를 잡을 수 있다... 공감수 0 댓글수 0 2014. 8. 7.
Endians 문제: ENDIANS / 구현 해결전략. - 1byte씩 읽어서 메모리에 값을 역으로 저장한다. 1) 입력 값이 저장된 변수의 주소+3위치로 이동한다. 1byte 단위로 이동을 위해 char형 포인터로 변환한다. 2) 결과값을 저장할 변수의 주소로 이동한다. 역시 char형 포인터로 변환. 3) 입력 값 변수의 주소 값은 감소, 결과 값 변수의 주소 값은 증가 하며 메모리 복사.[출처] [AOJ 문제] Endians|작성자 DevMoon 코드: https://github.com/xgate/algospot/blob/master/IMPL/ENDIANS.cpp 공감수 0 댓글수 0 2014. 8. 7.
N-Queen 문제: 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 문제] .. 공감수 0 댓글수 0 2014. 8. 7.
남극기지 문제: 남극기지 / 그래프 or 이진탐색 모든 노드가 전파를 받을 수 있어야 하고 전파의 출력은 최소화 해야한다. 이 문제를 해결하는데 두 가지 방법을 사용할 수 있다. 1. parametric search parametric search는 어떤 알고리즘으로 해를 바로 구해내는 것이 아니고, 임의의 값을 던지고 맞는지 확인해가며 해를 구하는 방법이다. 앞에서 언급한 임의의 값을 정하는 과정에 이진탐색이 사용될 수 있다. 이 방법을 이용한 알고리즘은 다음과 같다. 1. 초기 값으로 해의 최소값과 최대값을 이진탐색의 low, high 값으로 각각 지정한다. 2. mid((low+high)/2)값이 해가 될 수 있는지 검사해본다. 이말의 의미는 전파의 출력이 mid값인 경우 모든 노드들이 연락을 주고 받을 수.. 공감수 0 댓글수 0 2014. 8. 5.
Shisen-sho 문제: Shisen-sho / 조합탐색 사천성이라는 게임이 문제의 배경이고 게임 난이도를 정하는 것이 문제이다. 게임 난이도는 한 번에 없앨 수 있는 tile의 쌍으로 정해진다. 탐색의 방향이 정해져있으면 간단했을 건데 상.하.좌.우 모두 훑어봐야 하고, 중복되는 경우는 카운트 하지 말아야하기 때문에 약간 까다로웠다. 소소한 고민. 1. 꺽어지는 경우를 어떻게 판단할까? 문제에서는 3번 이상 방향이 전환되는 경우는 카운트하지 말아야한다고 했다. 방향 전환 유무를 어떻게 감지할까? 생각해보니 이전위치와 다음위치를 검사하면 될것같았다. 방향이 바뀌지 않았다면, 다음위치와 이전 위치가 적어도 x, y 둘 중 하나의 값은 같을 것이다. 둘다 다르다면 방향이 전환된 것이다. 그래서 재귀함수에 이전좌표를 넘겨줬다... 공감수 0 댓글수 0 2014. 8. 5.
Fast Matrix Exponentiation 문제: MATEXP / 분할정복 한 번에 한 번씩 계산해서는 시간내에 해결할 수 없다. 그렇다면? 반 씩 나누어서 계산하면 빠르게 해결할 수 있다. 1*1 행렬 계산을 해서 승수 2에 대한 값을 만들고, 다시 2*2를 해서 승수 4에 대한 값을 만들고.. 이런 식으로 하면 logN번만 계산하면 된다. 100 by 100 행렬 계산에 그리 큰 시간이 소요되지 않으므로, 행렬 계산은 단순하게 3중 loop로 처리했다. 총 복잡도는 코드: https://github.com/xgate/algospot/blob/master/DIV/MATEXP.cpp 공감수 0 댓글수 0 2014. 8. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.