Software Engineering Note

1월 1주, 2주에 페이스북에서 주최하는 해커컵 Qualification Round와 Round1 이 지나갔습니다. 주말에 귀찮음을 간신히 부여잡고, 각각 가장 쉬운 한문제씩 풀어봤습니다. 1. Progress Pie 보시면 아시겠지만, 이 문제는 입력으로 점이 주어졌을때, 특정 영역에 속하느냐를 묻는 문제입니다. 그런데 하필 원이라, 수학지식을 동원해야 할것같습니다. 두 가지를 만족하면 되겠죠. - 주어진 점과 중심의 거리가 반지름보다 작아야한다.- 중심점과 주어진점 사이의 각도가, 주어진 각도보다 작아야한다. (주어진 각도라 함은 진행률을 각도로 환산한 값을 의미) 두 점 사이의 각도? 검색하면 잘 나옵니다. (예를들면, http://yangpro.github.io/play-with-canvas-tr..

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

우리나라 시간으로 2015년 1월 18일 (일) 새벽 3시부터 라운드1이 열렸다. 예선에서 한 문제를 맞춰 라운드1에 왔다. 빨리 푸는 순서로 다음라운드로 올라가는줄 알고 새벽 3시에 일어날 생각하고 있었는데 다행히 순위 관계없이 동점자 모두 진출 규칙이라 아침에 일어났다. 바로 카페로 가서 풀이 시작.. 한 문제라도 풀 수 있을까? 걱정했지만 생각보다 많이 풀렸다. 1. Homework 주어진 숫자 범위 내에 정해진 소수 갯수를 약수로 갖는 숫자가 몇 개인지를 판단하는 문제다. 결국 소수 구하는 문제인데 입력 크기를 보면 그때 그때 구하는건 무리다. 조건에 맞게 캐시를 만들어놓고 계속 캐시를 이용하도록 했다. 관련 알고리즘: 아리스토테네스의 체코드: https://github.com/xgate/comp..

2015년 1월 9일 (금) 페이스북 해커컵이 열렸다. 대회가 열리는지도 모르고 있었는데 사내에 관심있는 사람들은 모여서 같이 하자는 글이 올라와서 알게되었다. 할 일도 딱히 없어서 회의실에 모여 문제를 풀었다. 저녁 8시에 모였는데 이미 대회는 시작되었더군.. 내가 풀기 시작했을 때도 60시간 넘게 남아있었으니.. 예선전답게 문제푸는 시간은 넉넉하게 주어졌다. (여기에 제시된 코드는 대회때 제출한 것은 아니고, 나름 다듬은 후에 input/output으로 검증한 것임을 알려둔다.) 1. Cooking the Books 주어진 숫자에서 한 번만 swap해서 최소/최대 값을 찾는 문제. 아.. 문제를 읽고 섣불리 풀다가 물먹은 문제다. 역시 방심은 금물.. 입력 값이 길지않기 때문에 모든 경우의 수를 만들..

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

지나가다 본 문제인데 호기심이 생겨 풀어보았다. 문제는 다음과 같다. 개미수열? http://navercast.naver.com/contents.nhn?rid=22&contents_id=2322 출처 : https://www.facebook.com/photo.php?fbid=718742614882121&set=gm.870169196356951&type=1 '읽고 말하기 수열' 이라고 부르는 것같은데 바로 위에 있는 수가 몇 개인지 쭈-욱 나열하는 것이다. 111 (1이 1개)12 (1이 2개)1121 (1이 1개 2가 1개)... C, Python, Java로 각각 풀어보았다. 1. C (재귀) #include #include const int MAX_DEPTH = 10; int getLength(cha..

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