tony9402

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

USACO를 돌면서 공부를 해보려고 한다. 최근 출제된 문제부터 풀 예정이며 실버를 풀면서 적응해 나가며 어려운 문제를 풀 예정이다. 문제를 풀면서 항상 업데이트 할 예정이다. 번호 오름차순으로 보기 번호 내림차순으로 보기

USACO를 돌면서 공부를 해보려고 한다. 최근 출제된 문제부터 풀 예정이며 브론즈부터 풀면서 적응해 나가며 어려운 문제를 풀 예정이다. 문제를 풀면서 항상 업데이트 할 예정이다. 번호 오름차순으로 보기 번호 내림차순으로 보기

요즘 DP를 공부하지 않았더니 잘 안풀린다. 그래서 쉬운 문제부터 다시 풀어나가면서 다시 감을 익히려고 한다. DP 공부 및 문제를 풀면서 항상 업데이트 할 예정이다.

간단한 알고리즘부터 간단히 작성할 예정이다. 설명위주보다 난 기록을 남기는 위주라 설명은 다른 블로그나 참고할 곳을 링크할꺼다. 블로그 1. kks227 순회에는 간단히 전위, 중위, 후위, 레벨 순회가 있다. 각각 영어로 preorder, inorder, postorder, level-order라 불리며 각 예제 코드는 아래와 같다. Preorder Inorder Postorder Level-order

이 글은 지속적으로 업데이트가 될 예정입니다. 알고리즘 공부를 제대로 해보려고 한다. 공부를 시작하기 전에 들어본 적 있는 자료구조 및 알고리즘을 나열해보려고 한다. 간단한 종류로 나눈다면 아래와 같다. 문자열 수학 트리 그래프 정렬 다이나믹 프로그래밍 네트워크 플로우 아래 Bar는 내가 아는 정도를 표시하는 것이다. 문자열 KMP 알고리즘 라빈카프 알고리즘 트라이(Trie) 아호코라식 접미사 배열(Suffix Array) Z 알고리즘 Hashing LCP Manacher 트리 트리 순회 이진 검색 트리 우선순위 큐 유니온 파인드 세그먼트 트리 펜윅 느리게 갱신되는 세그먼트 트리 머지소트 트리 세그먼트 트리 비츠 스플레이 Persistent Segment Tree LCA(최소 공통 조상) Heavy-Li..

SCCC 14일차 스터디 MST/위상정렬 MST에는 크루스칼 알고리즘, 프림 알고리즘이 있다. 프림 알고리즘은 pq를 이용한 다익스트라와 거의 비슷하니 금방 이해를 할 것이다. 크루스칼 알고리즘은 disjoint-set 을 이용한다. 아직 못 푼 문제가 많다.... (스터디때 문제들이 조금 어려웠던 문제들이 많았다.) 1. 최소 스패닝 트리 - ●●○○○2. 네트워크 연결 - ●●○○○(1번을 풀었다면 ○○○○○ - toooooo easy)3. 음악 프로그램 - ●●◐○○4. 문제집 - ●●○○○5. 줄 세우기 - ●●○○○ (4번을 풀었다면 ○○○○○ - toooooo easy)

12일차에는 스터디가 아니라 컨테스트가 진행되었다. sccc 스터디 2月 11日에 13일차 최단거리로 스터디가 진행되었다. 최단거리에는 여러가지 알고리즘이 존재한다. 1. 다익스트라 => 맨 처음에 짰을때 queue로 짰지만 priority_queue로 짜도록 노력하자..2. 벨만-포드 => 음수간선이 있을때도 사용가능3. 플로이드 => n이 충분히 작을때 사용할 수 있다.4. SPFA 1. 최단경로 - ●●○○○2. 최소비용 구하기 - ●●○○○3. 거의 최단경로 - ●●●◐○4. 네트워크 복구 - ●●◐○○5. 케빈 베이컨의 6단계 법칙 - ●◐○○○6. 플로이드 - ●◐○○○7. 저울 - ●●◐○○8. 타임머신 - ●●◐○○9. 웜홀 - ●●◐○○10. 파티 - ●●○○○

sccc 스터디 11일차 1月 29日 DFS/BFS에 대해 스터디를 진행하였다. 넓이 우선 탐색 => BFS깊이 우선 탐색 => DFS최단 거리를 구할땐 DFS로 하지 말고 BFS로 하자.... 1. DFS와 BFS - ●○○○○2. 미로 탐색 - ●◐○○○3. 숨바꼭질 - ●●○○○4. 토마토 - ●●○○○5. 단지번호붙이기 - ●○○○○6. 유기농 배추 - ●○○○○7. 경로 찾기 - ●●◐○○8. 연결 요소의 개수 - ●●○○○9. 영역 구하기 - ●◐○○○10. 로또 - ●◐○○○11. 나이트의 이동 - ●◐○○○12. 말이 되고픈 원숭이 - ●◐○○○13. 집배원 한상덕 - 아직 안품14. 상범 빌딩 - ●●●○○15. 열쇠 - ●●●●○16. 벽 부수고 이동하기2 - ●●●◐○17. 레이저 통..

sccc 스터디 10일차 1月 28日 이날엔 이분탐색에 대해서 스터디를 진행했었다. 간단히 설명하자면 이분탐색은 찾을 범위의 양 끝점을 잡고 찾을려하는 값을 찾아가는 것이다. 단 여기서 이분탐색을 적용하기 위해서는 정렬이 되어있어야한다. 즉 단조증가나, 단조감소여야 적용가능하다. 이분탐색은 계속 반을 쪼개가면서 찾기 때문에 원하는 수를 찾는데 O(log N) 만큼 걸린다. 파라메트릭 서치라는 것도 있는데 이것은 이분탐색을 기반을 두면서 최적의 답을 찾아가는 것이다. 1. 수 찾기 - ●○○○○2. 숫자카드 - ●○○○○3. 나무자르기 - ●●◐○○4. 예산 - ●●◐○○5. 숫자카드2 - ●○○○○6. 공유기 설치 - ●●●○○7. 기타 레슨 - ●●●○○8. 나는야 포켓몬 마스터 이다솜 - ●●○○○