5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 예제 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 ans : NO YES 한 번호가 다른 번호의 접두어인 경우가 있는지 체크하는 문제이다. 예를 들어 911과 9112314에서 911은 9112314의 접두어이므로 일관성이 없다고 판단한다. 1. 가장 간단하게 생각할 수 있는 방법으로 첫 문자열부터 끝까지 다 비교하는 방법을 생각했다. 시간제한은 1초이고 전화번호가 최대 10000개..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 예제 mirkovC4nizCC44 C4 ans : mirkovniz --------------------------- 12ab112ab2ab 12ab ans : FRULA 문자열에서 특정 문자열을 찾아 계속 삭제하는 문제이다. 삭제를 계속 반복하면서 삭제할 문자열이 남아있지 않을 때까지 완전탐색으로 풀면 시간초과가 뜬다. 따라서 처음 생각한 방법은 실제로 삭제를 하지는 않고 index만 다루어서 삭제했다 치고 푸는 것이었다. 이 방법은 삭제하는 시..

7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 예제 4 Baha enter Askar enter Baha leave Artem enter ans : Askar Artem 이름이라는 단일 데이터에 대해 빈번한 삽입, 검색, 삭제가 일어나므로 해시 셋이나 셋 자료구조를 사용하면 편하다. 출력 부분을 보면, 사전의 역순으로 출력하는 부분이 있으니 셋 stl을 이용해서 구현했다. 딱히 예외처리 할 부분도 없고 편한 문제다. /** 해시 7785 회사에 있는 사람 **/ #in..

오늘은 해시테이블을 공부했다. 생각보다 해시테이블에 모르는 부분이 많았고 정말 원리 위주로 천천히 공부했다. 해시테이블 같은 자료 구조를 공부하고 문제를 풀 땐 stl을 주로 사용해서 풀었는데, 오늘은 직접 구현해서 풀어봤다. 해시테이블을 공부하면서 놓쳤던 부분도 알게 모르게 챙겨가고 자동으로 복습까지 돼서 다음부턴 꼭 공부한 자료구조를 구현해 봐야겠다. 알고 보니 삼성 코테 B형은 stl을 전혀 사용하지 않고 풀어야 하는데 벡터는 완전 습관이 돼버려서 2차원 동적 배열도 다시 공부해야겠다. 그리고 친구의 추천으로 모르는 게 생기면 챗 GPT를 이용해 봤는데 이 녀석 완전 물건이다. 얼떨결에 진로 상담까지 해버렸다. 프런트엔드, 백엔드, ai 중에 고민이었는데 셋 다 찍먹은 해봐야겠지만 각각 특징과 주로..

해시테이블을 구현할 때 고민되는 부분이 몇 가지 있다. 해시 테이블 크기와 해시 함수이다. 먼저 해시 테이블 크기를 정해보자. 해시 테이블의 크기 해시 테이블에서 원소의 개수 / 테이블의 크기를 load factor라고 하고, 원소의 최대 개수는 곧 삽입의 최대 횟수이다. load factor를 작게 유지하면 충돌이 덜 생겨 연산들이 O(1)에 동작하겠지만 cache hit rate가 줄고 메모리를 많이 차지한다. 반대로 load factor를 크게 유지하면 충돌이 많이 생겨 성능에 악영향을 줄 수 있다. load factor를 정하는 방식은 체이닝 기법이냐 개방 주소화 기법이냐에따라 나뉜다. 먼저 체이닝 기법은 충돌이 어느 정도 발생하더라도 load factor를 1 이하로 둔다. 반면 개방 주소화 기..

일반적으로 효율적인 데이터의 저장 방법(직접 주소 테이블) 일반적으로 (key : value) 데이터를 기본 자료구조에 배치하면 탐색에 O(N)이 걸리거나 삽입/삭제에 O(N)이 걸린다. 가장 빠른 방법이 배열의 index로 key를 사용했을 때 탐색에 O(1) 시간이 걸린다. 그러나 key값의 종류가 대략 10^16 정도로 매우 많아지면 똑같이 배열로 구현할 수 있을까? 현실적으로 불가능하다. 혹은 key값이 최대 2000인데 실제 존재하는 key값은 0, 2000 뿐이라면 배열의 1~1999까지의 공간은 낭비된다. 이러한 문제들을 해시 테이블을 통해 해결할 수 있다. 해시 테이블이란? 해시 테이블은 임의의 길이를 가진 key값에 해시함수를 적용해 고정된 크기의 index를 생성하여 그 index에 값..