백준 13 문제. 1. BOJ 31430 : A+B - 투 스텝 - B1 A + B가 최대 2*10^18까지 가능하다. 그런데 'a' = 0, 'b' = 1, ... 이렇게 매핑하면 26진법으로 표현이 되면서도 26^13 이 2*10^18보다 더 크므로 26진법 인코딩을 해주면 된다. 이후에 다음 프로그램 에서는 26진법 표현을 받고 이를 다시 10진법으로 변환하면 된다. 처음으로 푼 투 스텝 문제라서 리뷰해보았다. 투 스텝 문제를 이해하고 입문하기 매우 좋은 문제라 생각한다. 2. BOJ 15651 : N과 M (3) - S3 Backtracking 문제다. 그냥 N^M 가지의 경우의 수를 전부 돌려보면 된다. 다른 N과 M 문제들과 비슷한 문제였다. 3. BOJ 5347 : LCM - S5 Numbe..

백준 19 문제. 1. BOJ 11502 : 세 개의 소수 문제 - S4 Number Theory(Primality Test) + Bruteforcing 문제. 1000 이하의 모든 소수를 찾는 건 그냥 O(N^2)로도 찾을 수 있다. 1000 이하의 소수는 대략 200 개 미만일 것이라 생각해서 세 수를 찾는 건 O(N^3)로 모든 조합을 찾아보았다. 앞에 소수 찾는 걸 Sieve로 좀 더 빠르게 찾을 수는 있는데... 귀찮아서 구현을 안 했다. 2. BOJ 11332 : 시간 초과 - S3 Implementation + Case-working 문제. 시간복잡도를 나타내는 문자열에 따라서 로직을 전부 다르게 구현해야 한다. O(N^2), O(N^3), O(2^N), O(N!)은 오버플로우가 나타날 가능..

백준 16~17문제. 1. BOJ 23760 : 까다로운 아이들과 선물 상자 - P5 (업다운 랜덤디펜스 성공! Solved - 18:01) Segment Tree + Binary Search 문제. 쿼리 순서대로 K 번째로 큰 수를 Segment Tree에 쿼리를 날려서 찾고 이를 업데이트 해주는 문제였다. 쿼리는 Binary Search를 응용하면 된다. 처음에 쿼리 순서를 마음대로 바꿔도 되는가 싶어서 예제가 이해 안 되었는데, 나중에보니 순서가 고정이라서 쉽게 풀었던 문제. 2. BOJ 23757 : 아이들과 선물 상자 - S2 Priority Queue 문제. 위의 BOJ 23760을 푼 김에 같이 풀어본 문제였는데, K=1이 고정인 문제여서 PQ로 풀 수 있었다. PQ 공부하기 좋은 문제라 생..

백준 21 문제. 1. BOJ 31287 : 장난감 강아지 - S3 Simulation + Bruteforcing 문제. min(N,K)번 반복시에 (0,0)으로 돌아오는 경우가 있는지를 알아보면 된다. 2. BOJ 13076 : Distinct rational numbers - G1 [업다운 랜덤디펜스 성공! Solved - 11:08] Math + Euler Phi function 문제. a/b가 다른 경우의 수들을 구하라면 a,b가 서로 서로소인 경우들을 전부 더해주면 된다. 그리고 0도 포함해야하니 +1. 오일러 피 함수 문제를 오랜만에 봐서 다른 문제에 제출한거 가져다가 썼다. 3. BOJ 1854 : K번째 최단경로 찾기 - P4 Dijkstra 문제. 그냥 각 노드가 i번째로 우선순위 큐에서..

백준 14 문제. 1. BOJ 14588 : Line Friends (Small) - G5 Floyd-Warshall 문제. 각 선분에 대해서 겹치면 1로 두고, 이후에 Floyd-Warshall 실행. 그러면 각 쿼리별로 O(1)만에 대답 가능하니 총 시간복잡도는 O(N^3+Q)가 된다. 2. BOJ 1525 : 퍼즐 - G2 BFS + Tree Set / Hash Set 문제. 메모리 제한 때문에 보드의 상태를 최대한 효율적으로 표현해야 했는데, 각 보드의 상태를 9자리 수로 표현함으로써 해결하였다. (예 : [[1,2,3],[4,5,6],[7,0,8]] -> 123456708) 이후에 BFS를 돌리면 되는데, visited 배열은 tree_set이나 hash_set을 써서 하면 된다. 나는 메모리 ..

최근에 블로그에 일지만 올리니까 블로그 자체가 내 PS 기록으로만 가득찰 것 같아 매일 마다 적어두고 일 주에 한 번씩 올리려고 한다. 사실 매일마다 올리기 귀찮아서;; 백준 10 문제. 1. BOJ 27903 인생 - Unrated Golfscript로 풀었다. 핸들 때문에 printf, print, cout 등등이 다 막혀서 매우 막막했던 문제. 근데 핸들에 따라서 난이도가 천지차이가 나므로 이건 아무리 생각해도 Unrated 문제가 맞다. (만약 백준 핸들이 aaaaaa 이런식이면 파이썬으로도 쉽게 풀 수 있다... print(chr(97)+...) 이런식으로) 2. BOJ 15912 우주선 만들기 - G3 [업다운 랜덤디펜스 성공! Solved - 20: 42] DP + PQ / Tree Set로..