tony9402

올해 소프트웨어 마에스트로 11기 활동이 끝나고 활동 중에 못했던 알고리즘, 자료구조 공부를 하고 있다. 몇일 전에 트라이 자료구조를 공부하려고 공부하고 트라이 관련 문제를 쭉 풀었다. 이 글은 내가 공부했던 것을 정리하는 글이다. (난 트라이 이론을 정리는 안하고 트라이 구현 및 문제 풀이 위주로 작성한다.) 이 글에서는 트라이를 맨 처음에 짠 코드에서 최적화 시킨 코드까지 어떤 과정을 거쳤는지 정리한다. 1. 포인터를 이용한 구현 with map 처음부터 간단하게 짜기 힘들다. 포인터를 이용해서 먼저 직접 짜보는게 좋다. 나도 트라이 이론만 보고 혼자 포인터를 이용해서 짰었다. 빌드 과정은 완전한 O(NL)이 아니라 map을 사용하기 때문에 log 26 (더미노드 없다고 생각하면) 정도가 붙겠지만....

운이 좋게 류호석님이 준비하신 코딩 테스트에 검수자로 참여했습니다. 소마 11기 활동을 하면서 검수활동을 시작해보려 했는데 호석님이 절 검수자로 뽑아주셔서 참여하게 되었습니다. 검수는 거의 처음이라 잘 해낼 수 있을지 걱정이 되었지만 하기 쉬운것부터 하나씩 했습니다. 골목 대장 호석 문제의 정해가 이분탐색 + 다익스트라인데 옛날에 최단경로에서 잘못짠 다익스트라로 고통을 받은 기억이 떠올라 다른 분들 소스코드를 보고 그 데이터가 없어서 추가하는 것부터 시작했습니다. (하지만 커팅 등 다른 풀이는 생각못하고 있었네요.. ) 문제를 보고 풀이 실수할만 부분들을 찾아 그 풀이가 통과되는지 등 데이터가 약하지는 않은지, 문제 지문 오류 등을 검수했습니다. 대회에 작은 이슈가 있었지만 이번 대회를 통해 검수할 방향..

SCCC 스터디 5일차 1月 16日 (수학 어렵다.........................) 1. 수학1 에라토스테네스의 체 - N 이하의 소수를 빠르게 찾는 알고리즘이다. 소수의 배수를 없애는 방식으로 진행한다. 자세한 내용은 여기에서 참고하면 될 것이다. 이 방법을 이용하면 시간복잡도는 O(n log log n)이다. 유클리드 호제법 - 최대공약수(GCD)를 빠르게 구하는 알고리즘이다.나머지 연산을 이용해서 빨리 구할 수 있는데 이에 대한 자세한 내용은 여기에서 참고하면 될 것이다. 에라토스테네스의 체 - 소수인지 판별하는 방식은 거의 동일하지만 소스코드를 작성할때 살짝 다른게 있다. 다른 곳에서 계산과정 중 오버플로우를 방지하기 위해서 사용한다고 들었다. - 에라토스테네스 1. 에라토스테네스의 ..

SCCC 스터디 5일차 1月 15日 오늘은 미세먼지로 인해 전날 스터디 모임이 취소가 됬다. 그래도 배울 내용은 적어 홈스터디로 진행됬다. 1. 분할정복 분할정복은 Divide and Conquer로 문제를 같은 유형의 여러 작은 문제들로 나눈 뒤, 그 작은 문제들의 답을 이용해서 문제를 해결하는 방식을 말한다. 분할정복을 이용하면 시간 복잡도를 줄일 수 있다. 예를 들어, 1부터 100까지 더하는 것을 공식을 이용하지 않고 더한다면 아주 간단하게 O(n)로 더할수는 있다. 하지만 분할정복을 이용하면 O(log n)으로 더 줄일 수 있다. 1 + 2 + 3 + ... + 51 + 52 + 53 + ... + 99 + 100 이를 한번 Divide(분할)을 해보자. 1 + 2 + 3 + ... + 50 +..

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..

문제 : 1,2,3 더하기 4 문제 유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자. 4를 1,2,3더하기로 표현해보면 3+1 2+2 1+3 2+1+1 1+2+1 1+1+2 1+1+1+1 이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자. 3+1 (1+3) 2+2 2+1+1 (1+2+1, 1+1+2) 1+1+1+1 이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까? 1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다. 한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다. 4를 가지고 예..

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 2 이 문제는 1,2,3 더하기 문제를 이용해서 풀었다. 먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자. 4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다. 따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vect..

알고리즘 분류 : 다이나믹 프로그래밍(DP) 문제 : 1, 2, 3 더하기 이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다. 5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자. 2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자. 2는 1, ..