groti's blog

해시 테이블이란? 해시 테이블(hash table)은 키를 값에 매핑하여 데이터를 관리하는 연관 배열 자료구조이다. 한 마디로 키와 값이 1 대 1로 연결되고, 키를 이용하여 값을 저장, 삭제, 검색할 수 있는 것이다. 해시 테이블에서 키와 값을 맵핑하기 위해서는 해시코드가 필요하다. 해시코는 키를 정수로 변환한 값을 말한다. 예를 들어, 크기 50의 배열 A가 있고, 문자열 "abcdef"를 정수 100과 맵핑하려고 한다. 이때 문자열 "abcdef"를 특정 정수로 변환하여 25를 얻었다면, A[25]에 100을 저장하여 "abcdef"와 100을 맵핑할 수 있다. key -> function(key) -> hash code => index -> 값 저장, 삭제, 검색 해시 함수 해시 함수(hash f..

1. 문제 해석 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 알파벳 대문자로 이루어진 N개의 단어가 주어진다. 이때, 각 알파벳 대문자를 0~9 중 하나로 바꿔서 N개의 수를 합한다. 같은 알파벳은 같은 숫자로 바꿔야 하고, , 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 모든 단어에 포함된 알파벳은 최대 10개를 넘지 않는다. 알파벳과 ..

1. 문제 해석 각각의 빨간색 정점과 파란색 정점이 N개가 있다. 각 정점은 1~N의 번호를 가진다. 1 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다. 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i-1번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다. 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i-1번 정점을 연결하는 간선이 존재한다. 서로 다른 간선의 끝점을 공유하지 않도록 N개의 간선을 선택하는 방법의 수를 구해야 한다. (1 T; while (T--) { cin >> N; cout

1. 문제 해석 https://www.acmicpc.net/problem/18248 18248번: 제야의 종 첫 줄에 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 100)이 주어진다. i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 ai,1, ai,2, ..., ai,M 이 주어지는데, ai,j가 1이면 사람 i가 j 번째 타종을 들었음을 의미하고, 0이면 듣지 못했음을 의미한다. www.acmicpc.net 제야의 종소리는 특정 거리 R 이내에 있는 사람만 들을 수 있다. 거리 R의 값은 종을 칠 때마다 바뀐다. N명의 사람이 있고 M번 종을 친다. 사람들은 움직이지 않는다. N명에 사람 각가에 대한 각 M번의 타종을 들었는 지의 여부가 주어졌을 때, , 실제로 가능한 상확인 지 2. 접근방법 ..