[SWEA] 9468. 친구 추천 (C++, 라이브러리 X)
B형 실전 문제 풀이 Graph와 Bucket을 이용했다. Graph와 Linked List를 이용해서 Edge를 만들면 Edge를 Delete할 때 해당 node의 모든 edge를 탐색하야하므로 시간초과가 난다. 그렇다고해서 N * N의 edge 배열을 만들기엔 N이 ...
최근 포스트
[SWEA] 9467. 문자열 암호화 (C++, 라이브러리 X)
B형 실전 문제 풀이 바꾸는 문자열이 3글자로 고정돼있으므로 Hash를 이용하면 1대1 매핑이 가능하다. 문자열의 크기 (50000), change 호출 횟수(50000) 을 고려하면 완전 탐색은 50000 * 50000 로 시간초과가 난다. 그래서 Hash Table을...
[SWEA] 12526. 자동완성 (C++, 라이브러리 X)
B형 실전 문제 풀이 Trie를 만들고 카운트(cnt), 밴 여부(ban), 추천 노드(best) 를 저장. input을 할 때마다 카운트를 1씩 더하고, 부모 노드를 순회하면서 best와 비교 및 교체. ban을 하면 ban을 true로 해서 추천되지 않도록 하고, 부...
[SWEA] 7091. 은기의 아주 큰 그림 (C++, 라이브러리 X)
Hash 기본문제 풀이 Rabin-Karp 알고리즘을 사용하여 그림의 해시값을 구하여 은기와 선생님의 그림을 비교한다. 먼저 가로의 해시값을 구하고 가로의 해시값으로 세로의 해시값을 구한다. 실수 가로와 세로에 같은 Hash function을 사용하면 전체 Hash f...
[SWEA] 4038. 단어가 등장하는 횟수 (C++, 라이브러리 X)
Hash 기본문제 풀이 Hash를 사용하지 않고 KMP 알고리즘을 사용했습니다. 참고: KMP : 문자열 검색 알고리즘 실수 테스트 케이스를 여러번 실행할 때에는 전역변수 초기화를 잘 해줄 것.