알고리즘 3

[자료구조] Hash(해시), Hash Table(해시 테이블)

1. 해시 함수(Hash Funtion) 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash value) 또는 해시코드, 매핑하는 과정 자체를 해싱(hashing) 이라고 합니다. 해시 함수의 가장 기본적인 성질은 두 해시 값이 다르면 원래의 데이터의 값도 다르다는 것입니다. 하지만, 같은 해시값을 가지고 있더라도 원래의 데이터가 꼭 같은 것은 아닙니다. 해시함수의 종류 : MD1, MD4, MD5, SHS, SHA-1, HAS-160 등 2. 해시테이블 (Hash Table) 해시테이블(Hash) 테이블은 효율적인 탐색을 위한 자료구조로 키(Key) 를 값(Value..

[Algorithm] 빅오분석법

빅 오분석(표현)법은 알고리즘의 성능이나 복잡도를 설명하는데 일반적으로 사용하는 표현 방법입니다. 빅 오 분석법에서는 입력 겂의 크개(개수)를 n개라고 가정하고, 이 n개의 입력된 값을 몇번이나 확인해봐야하는 지를 n의 식으로 표현한 것입니다. 즉, 동작하기 위해 필요한 연산횟수를 나타낸다고 생각하면 됩니다.그리고, n이 무한대로 올라가면 n이나 n+2 나 크게 차이가 나지 않기 때문에 2와 같은 상수항은 그냥 무시해도 무방합니다. 빅 오 분석법을 적용하는 방법1, 입력값이 무엇인지 확인 하고 어떤 것을 n으로 놓아야 할지 결정한다.2. 알고리즘에서 수행해야할 연산 횟수를 n의 식으로 표현한다.3. 차수가 제일 높은 항만 남긴다.4. 모든 상수 인수를 없앤다. 어떤 알고리즘이 가장 빠른가?가장 빠른 것은..

땅따먹기(동적계획법, 문제 출처 : 프로그래머스)

[문제] 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (..