본문 바로가기

Dot Algo∙ DS

해시(Hash)와 해시 테이블(Hash Table)
Dot Algo∙ DS/자료구조 2022. 5. 5. 해시(Hash)와 해시 테이블(Hash Table) 해시 테이블 Hash Table 해시 테이블은 키를 저장하거나 해당 키와 관련된 값을 저장하는 데 사용되는 자료구조다. 삽입, 삭제, 조회가 평균 O(1) 시간에 수행된다. 기본 개념은 키를 배열에 저장하는 것이다. 배열에 저장되는 위치(슬롯)는, 키를 '해시 코드(hash code)'한 결과에 따라 결정된다. 해시 코드란 키값에 해시 함수를 적용해서 계산된 정수값을 말한다. 해시 함수를 잘 고른다면, 객체를 배열에 균일하게 분배할 수 있다. 해시 충돌 Hash Collision 1) 연결리스트를 통해 객체 저장 다른 두 개의 키가 동일한 위치(해시 코드가 일치)로 매핑되면 충돌이 발생했다고 한다. 충돌을 처리하는 일반적인 방법 중 하나는 각 배열의 인덱스에서 연결리스트를 통해 객체를 저장하는 것이다. ..
[BOJ] 백준 13506번 카멜레온 부분 문자열 (Java)
Dot Algo∙ DS/PS 2022. 4. 16. [BOJ] 백준 13506번 카멜레온 부분 문자열 (Java) #13506 카멜레온 부분 문자열 난이도 : 플레 4 유형 : 문자열 / kmp 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net ▸ 문제 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오. 예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix..
[BOJ] 백준 1605번 반복 부분 문자열 (Java)
Dot Algo∙ DS/PS 2022. 4. 13. [BOJ] 백준 1605번 반복 부분 문자열 (Java) #1605 반복 부분문자열 난이도 : 플레 3 유형 : 접미사 배열, LCP 배열 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net (3033번 중복 문제) 3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net ▸ 문제 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나..
[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 4. 7. [알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java) 접미사(Suffix) 접미사(suffix)는 파생어를 만드는 접사로 단어 뒤에 붙어 새로운 단어가 되게 하는 말이다. 문자열 s의 i번째 접미사란, s 의 i번째 글자부터 마지막 글자까지 포함되는 부분문자열을 뜻한다. 문자열 "alohomora" A[i] S[A[i]···] 0 a l o h o m o r a 1 l o h o m o r a 2 o h o m o r a 3 h o m o r a 4 o m o r a 5 m o r a 6 o r a 7 r a 8 a 접미사 배열(Suffix Array) 문자열을 다룰 때 빼놓을 수 없는 자료 구조로 접미사 배열(Suffix Array)가 있다. 접미사 배열은 흔히 '문자열의 맥가이버 칼'이라고 불리며, 굉장히 다양한 문제를 푸는 데 쓸 수 있다. 접미사 배..
[BOJ] 백준 3107번 IPv6 (Java)
Dot Algo∙ DS/PS 2022. 3. 24. [BOJ] 백준 3107번 IPv6 (Java) #3107 IPv6 난이도 : 골드 5 유형 : 문자열 / 정규식 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net ▸ 문제 IPv6은 길이가 128비트인 차세대 인터넷 프로토콜이다. IPv6의 주소는 32자리의 16진수를 4자리씩 끊어 나타낸다. 이때, 각 그룹은 콜론 (:)으로 구분해서 나타낸다. 예를 들면, 다음과 같다. 2001:0db8:85a3:0000:0000:8a2e:0370:7334 32자리의 16진수는 사람이 읽고 쓰기에 불편하고, 대부분의 자리가 0이기 때문에 아래와 같이 축약할 수 있다. 각 그룹의 앞자리의 0의 전체 또는 일부를..
[BOJ] 백준 1493번 박스 채우기 (Java)
Dot Algo∙ DS/PS 2022. 3. 23. [BOJ] 백준 1493번 박스 채우기 (Java) #1493 박스 채우기 난이도 : 골드 4 유형 : 그리디 / 분할정복 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net ▸ 문제 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...) 세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필..
[BOJ] 백준 12899번 데이터 구조 (Java)
Dot Algo∙ DS/PS 2022. 3. 22. [BOJ] 백준 12899번 데이터 구조 (Java) #12899 데이터 구조 난이도 : 플레 4 유형 : 세그먼트 트리 / 인덱스 트리 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net ▸ 문제 자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. ▸ 입력 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2..
[BOJ] 백준 10838번 트리 (Java)
Dot Algo∙ DS/PS 2022. 3. 21. [BOJ] 백준 10838번 트리 (Java) #10838 트리 난이도 : 골드 1 유형 : 트리 / LCA 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ▸ 문제 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 적용할 수 있는 연산은 세 종류이며, 이를 통해 트리의 모양을 바꾸거나 트리 에지에 색칠을 할 수 있다. 각 연산과 그 의미는 다음과 같다. paint(a, b, c): a번 노드와 b번 노드를 잇는 최..

티스토리툴바

티스토리툴바