전체 글110 해싱(Hashing) 1. 개요 해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법이다. 특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 본 글에서 소개할 방법에 따르면, 구현이 간단할 뿐만 아니라 해싱 충돌이 발생할 확률이 매우 낮기 때문에(충돌이 나지 않는다고 가정) 실제 대회에서 자주 사용된다. 2. 구현 dad라는 단어가 있다고 생각하자. 이 단어를 하나의 정수로 치환하려고 한다. 기본적인 아이디어는 "문자의 종류" 진법으로 생각하여 정수로 치환하는 것이다. 'a'는 1, 'b'는 1, … , 'z'는 26으로 생각하자. dad는 아래처럼 하나의 값으로 표현할 수 있다. 'a'를 0부터 취급하지 않는 이유는 "a"와 "aaa"를 구분하지 못함에 있다. 아래의 코드는 하나의 문.. 2020. 8. 7. C++ [STL] vector 구현 1. 정의 구현하고자 하는 자료형 vector를 아래와 같이 정의해보자. A : 값을 저장하는 일차원 배열이다. 배열의 index는 0부터 시작하며, 배열의 최대 크기는 max_size이다. 따라서 A[0]부터 A[max_size-1]까지 총 max_size개의 값을 저장할 수 있다. size : 현재 배열 A에 저장되어 있는 값의 개수를 나타낸다. 따라서 A[0]부터 A[size-1]까지 값이 저장되어 있다. max_size : 배열 A가 최대로 저장할 수 있는 값의 개수를 나타낸다. vector에 값을 추가하다보니, size가 max_size보다 더 커지는 경우를 살펴보자. 다섯번째 값을 추가하고 싶지만, A의 크기가 충분하지 않은 상태이다. 이와 같을 때에는 아래의 과정을 따른다. 1) 기존의 A .. 2020. 8. 5. BOJ 15636 Linear Algebra and Group 문제 링크 아래 표지에 있는 숫자들의 합을 계산하는 문제이다. 그림을 인터넷에서 다운 받은 후, 어떤 특징이 있는지 관찰해보자. 같은 숫자가 적힌 칸의 배경색이 모두 동일하다는 사실을 알 수 있다. 예를 들어, 1이 적혀있는 칸은 분홍색으로 색칠되어 있고 0이 적혀있는 칸은 빨간색으로 색칠되어 있다. 그림은 29개의 줄과 50개의 열로 구성되어 있으며, 총 1450개의 숫자칸이 존재한다. 각 칸에 대한 RGB 값으로 clustering하면 되겠다는 전략을 세웠다. 숫자 부분은 각 칸에서 차지하는 영역이 크지 않으므로 무시하고, 모든 칸의 테두리에 있는 검은 경계선을 제외시킨다. 각 칸에 존재하는 모든 픽셀들에 대한 RGB값의 평균을 다음과 같이 계산할 수 있다. clustering이 성공적으로 잘 이루어.. 2020. 2. 2. SPFA Optimization Techniques Shortest Path Faster Algorithm(SPFA) 알고리즘이 무엇인지 궁금하다면 이 게시글을 참고하자. 본 글에서는 SPFA 최적화 기법에 대해서만 서술하겠다. 1. Small Label First (SLF) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 큐의 가장 앞 부분에 위치한 정점(u)과 최단 거리를 비교한다. 만약 시작점으로부터 u에 이르는 거리보다 v에 이르는 거리가 더 짧다면, 큐의 가장 앞 부분에 v를 삽입하면 된다. 아래의 코드는 BOJ 1753번에 위 방법을 적용한 것이다. 2. Large Label Last (LLL) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 시작점으로부터 큐에 들어가 있는 정점들에 이르는 최단 거.. 2019. 10. 18. 2018 KAKAO CODE FESTIVAL 예선 A번부터 E번까지 해결하였고, F번은 해결하지 못했다. 대회 중에 내가 정답 판정 받은 코드는 여기서 볼 수 있다. 아래는 간략한 풀이 및 스포일러이다. A. 상금 헌터 간단한 구현 문제. 등수가 0일 때에 주의한다. B. 인형들 N이 500이하이므로 평균과 표준편차 정의에 의해 단순히 계산하면 된다. 자료형 오버플로우에 주의한다. C. 숏코딩 == 연산과 != 연산에 대해 구분하여 생각할 수 있다. == 연산의 경우, 연결 관계를 그래프로 표현하였을 때에 각 component가 독립적인 문제이다. 이 component에서 길이가 가장 짧은 하나의 노드와 다른 노드의 연결 관계를 모두 표현하는 것이 최적임을 알 수 있다. != 연산의 경우에 대해서는 서로 다른 컴포넌트 간의 관계만 표현해주는 것이 최적이.. 2018. 8. 5. 이전 1 2 3 4 ··· 22 다음
