welcome!

백준 1748 수 이어 쓰기 1 문제보기https://www.acmicpc.net/problem/1748 수를 n 까지 이어쓰는데, n까지 이어썼을 때 총 길이가 몇인지 세는 것이다.그래서 나는 len 함수를 만들어서 일일히 길이를 다 더해주기로 생각했다.함수는 log10 n 의 시간복잡도를 가지고, 총 n번 반복하니, n* logn 의 시간복잡도를 가지는 풀이이다. 좀더 멋진 풀이 방법이 있긴하다. 시간복잡도는 n이다.for 문을 딱 1번 1~n까지 순회하는데, i가 1~9까지는 1씩 길이가 더해지고, 10~99 까지는 2씩 길이를 더해준다.이렇게 하려면 int base = 10, cnt=1, ans=0;for (int i=1; i

Trie Introduction트라이는 자료를 찾는데 특화된 자료 구조이다. 트라이(Trie)의 어원은 retrieval (찾는다)의 중간글자 trie에서 유래되었다.트라이 자료구조는 종종 radix tree, prefix tree라고도 불린다. 앞 문자를 기준으로 차차 트리의 자식 vertex로 한글자씩 진행해 나가기 때문이다. 잘 이해하지 못 해도 다음 그림을 보면 이해할 수 있다.아래의 그림은 to, tea, ted, ten, a, in, inn 7 글자에 대해 트라이 자료구조로 만들어 본것이다. 위키피디아에서 퍼왔다. 이렇게 트라이 자료구조를 만드는 것은 내가 저런 단어들을 가지고 있어요~ 라는 뜻과 같다. 우리가 구현할 트라이 자료구조는 위 그림과는 좀 다르다.차차 더 읽어가면 트라이 자료구조에..

시작하기에 앞서특정한 입력값 집합으로 이루어진 문제에 대한 정답은 같은 문제에 대한 작은 입력 값 집합에 대한 정답으로 축소할 수 있습니다. (이것은 부분 문제subproblem 이라는 꽤 중요한 표현입니다.)예를 들어, 두 양의 정수 a, b의 최대공약수(GCD)를 구하는 문제를 생각해보자. 여기서 b>a. 이 문제는 더 작은 입력값인 b mod a 와 a의 최대공약수를 구하는 문제로 축소될 수 있다. 왜냐하면 gcd(b mod a, a) = gcd(a, b)이기 때문이다.이런 문제 축소가 수행될 수 있다면, 원 문제의 정답은 이런 축소된 문제의 흐름(좀 더 엄밀하게는 축소된 문제의 나열sequence of reductions) 속에서 찾아 낼 수 있다. 계속 축소하다보면 정답을 정확하게 알 수 있는 ..

내가 제일 약한 자료구조문제 http://codeforces.com/problemset/problem/911/E 자료구조문제는 자료구조를 응용해서 푸는 문제이긴한데, 그 동작이 영 익숙치 않다. 이번 문제는 다음과 같다. 한 개의 큐와 한 개의 스택를 이용해 하나의 배열로 정렬하여 두어야한다.문제는 그림으로 그려보면 대충 다음과같다.1과 2의 동작을 할 수 있는데 array에 반드시 sorting 되어야한다.그래서 문제 이름이 stack sorting 이다. 그래서 sorting 이 될수 없으면 -1을 반환해야한다. 문제가 여기까지이면 nice이다. (그래도 까다롭고 어려울 듯)그런데 문제는 이 요구사항에서 한 걸음 더 나가는데, 배열 size가 n이라고 할 때 단 k만 주어진다. 그래서 문제 input..

2차원평면에서 원의 방정식 응용 문제 컬링 게임을 하는데 컬링이 y=0인 지점부터 차곡차곡 쌓인다. 컬링은 x가 주어졌을때 (x, 10^100) 인 지점부터 y=0인 지점으로 가며 경로상에 동일한 컬링이 있을때 그곳에 부딪히고 멈춘다.입력이 주어진것부터 컬링을 하는것이며,인풋이 아래와 같을때 그림은 대충 저렇다.6 2 5 5 6 8 3 12 그런데 쌓이는 상태를 어떻게 저장해줘야 새로운 컬링을 그곳에 부딪힌다는 생각을 할 수 있기 때문에,나는 이 곳에서 막혔었다. 하지만 생각해보면 결국은 이미 사용한 컬링들은 (x,y) 를 저장하고 다음 새 컬링이 올때 그것을 참조하면된다. 그렇담 y는 어떻게 결정되는가? 두 원이 접하기 위해선 다음과같은 방정식을 만족해야한다.두 원의 반지름의 합 = 두 원의 원점 사이..

http://codeforces.com/problemset/problem/908/B 음... S사 입사 테스트 급 문제였다 ㅋㅋ굉장히 쉬운 문제였는데 숫자와 방향 맵핑에서 24가지의 경우의 수가 생성될 수 있는데 난 그것을 파악하지 못하고 4가지의 경우의 수밖에 생각하지 못했다. (항상 동서남북 순서대로 맵핑될 거라고 생가을 했기때문에 ...)testcase에 14개의 경우의 수가 나왔을 때 뭐였는지 몰랐다.하지만 생각보다 쉬운문제였다. ㅡ.ㅡ;;;하아 영어의 어려움이란 소스보기https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/908B.c

Codeforces 911D Inversion Counting숫자로 이루어진 집합에서 그 집합에서의 특정 두 원소 ai, aj의 위치가 i > j 일떄 ai

a/b가 주어졌을 때 소수점 아래에 정확히 c가 있는 자릿수 구하기1

난이도 6/10DP문제, 특히 난이도가 높다고 생각한다. 특히 탑 구현? 부분 즉, dp 2차원을 어떤 정보로 memoization 할것인가가 크게 걸렸다. 나는 온전하게 문제를 풀지 못하였지만, 기억을 잃지 않으려고 포스트를 써본다. 각기 높이가 다른 블록이 여러개 주어지는데, 이것들로 두탑을 만드는데 두 탑의 높이가 같게 만든다.그런데 그것이 최대가 되는 지점을 생각해야한다. 최적화이다.인공지능이라는 어려운 주제를 구현하는 방법을 모르고,쉬운 방법을 원한다면 모든 경우의 수를 다 고려하는게 좋다, 그리고 가장 큰 특성치(두 탑의 높이가 같으며 최대 높이)인 지점을 찾는것.결국은 brute force와 그 지수복잡도를 해결하기 위한 subproblem의 만남이다. 즉 dp문제. 어떤 지점에서 subpr..

이전포스트 보기 Extracting the grid이전 포스트에서는, 몇 몇 선을 찾긴했다. 근데 그 많은 선들은 퍼즐이 어디에 위치하고 있는지 찾기엔 적절하지 않았다. 그래서 이번 포스트에서는 좀 수학적인 이야기를 곁들어서 퍼즐이 정확히 어디에 위치하는지 찾아내볼것이다. 그리고 퍼즐의 왜곡을 없애서 퍼즐을 마치 바로 위에서 수직으로 보는 듯한 이미지로 만들것이다. Merging lines이미지의 물리적인 선은 원래 선과 관련된 "수학적인" 선을 가지는데, 이건 근처의 가능한 선들을 합침으로 인해 이 것을 보완할 수 있다. 아래는 이전 포스트에서 Hough transform을 통해서 얻은 결과물이다.선을 합친다는건, 근처의 선들을 평균낸다는 것을 뜻한다. 그래서 특정 반경에 있는 선들은 결국엔 같이 합쳐..