Hash Table은 key로부터 매핑된(key-value 형식) 자료구조로 Hahsing이라는 기술을 사용합니다. Hash, Hashing해시는 O(1)을 지향합니다. 데이터 개수 N과 무관하게 단번에 값을 찾아내겠다는 것입니다.주어진 키를 사용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 합니다.해시 함수에 주어진 레코드의 키에 해시 함수를 가하면 그 레코드가 저장되어야 할 인덱스가 나옵니다. 당연히 이 계산은 매우 빨라야 합니다. 키에 해시 함수를 가하여 채운 도표가 해시 테이블입니다. Hash function주어진 데이터를 실제 정수 값으로 변환하는 함수입니다. 여기서 나오는 정수값은 테이블의 인덱스로 사용할 수 있는 정수(해시 코드)입니다. key-value 값으로 연결될 때, ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 앞뒤를 뒤집어도 똑같은 문자열을 Palindrome 주어진 문자열 s의 부분문자열 중 가장 긴 팰린드롬의 길이를 반환 제한사항 문자열 s의 길이는 2,500 이하의 자연수 풀이 DP로 풀어볼 수도 있다. 시간 복잡도를 줄여줄 수 있는 Manachar Algorithm으로 풀어보려고 한다. Manacher Algorithm 각 문자를 중심으로 좌, 우 문자를 비교한다. dbcbabcbabc 라는 문자열을 예시로 들면 그림과 같이 팰린드롬을 만드는 부분문자열이 존재한다. 순차적으로 탐색을 진행한다. 팰린드롬..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 A와 B가 n개의 육면체 주사위로 승부 각 면이 나올 확률이 동일 A와 B는 n / 2 개씩 가져가 주사위를 굴린 뒤, 나온 수를 합한 점수로 계산 A는 주어진 주사위에서 승리할 확률이 가장 높은 주사위를 선택 제한사항 승리할 확률이 가장 높은 주사위 조합으로 주어짐 n은 2의 배수 dice의 개수는 10개 이하 dice에 적힌 수는 100이하 자연수 풀이 각 주사위를 고를 수 있는 조합(combination) 구하기 n/2개를 던져서 나올 수 있는 조합 구하기 A가 고른 주사위들(1번의 원소들)을 2..

6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 문제 월드컵 최종 예선에서는 6개국으로 구성 각 국가별로 한 번씩 총 5번의 경기 각 나라의 승, 무승부, 패를 보여주는 결과지 네 가지의 결과에서 가능한 결과라면 1, 불가능이라면 0으로 출력 제한사항 네 가지의 결과지 6개국의 결과로 승, 무승부, 패의 순서로 빈칸을 포함하여 18개 숫자로 구성 풀이 이게 어렵나? 승과 패가 같고 무승부를 대응해서 풀면 되지 안되더라... 문제 유형이 백트래킹에 맞춰 고민하기 시작했다. 일단 월드컵의 경기는 총 15번을 진행한다..

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 수열 A에서 가장 긴 증가하는 부분 수열의 길이를 출력 제한사항 수열의 크기 N은 1,000,000 이하의 자연수 수열 A를 이루고 있는 A𝘅는 1,000,000 이하의 자연수 풀이 수열 A로 [10, 20, 10, 30, 20, 50]이 주어진 상황에서 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]으로 길이 4를 반환하면 된다. DP로 풀게 되면 O(n²) 시간 복잡도를 가지게 된다. 이를 개선하기 위해서는 이진 탐색을 해야한다. Longes..

15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 문제 주어진 A를 최소 횟수로 연산을 수행하여 B로 만드는 문제 연산의 3종류 삽입: 한 위치에 문자 하나를 삽입 삭제: 문자 하나를 삭제 교체: 문자 하나를 다른 문자로 교체 제한사항 문자열은 알파벳 소문자로만 구성 문자열은 최대 1000글자 풀이 문제의 핵심은 얼마나 중복된 문자를 확인하는지가 중요하다. 물론 이 문제를 혼자서 해결 못했기에 이렇게 블로그에 정리 중이다. 편집 거리 알고리즘 위키의 Edit distance 내용을 보게 되면 다양한 종류에 대한 내용이 나온다. 글에서 이야기 하는 것은 2개의 문자열이 주어졌을 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 주어진 N과 사칙연산만으로 주어진 number와 동일하게 만들 수 있는 최소 횟수 제한사항 N은 1 이상 9 이하 number는 1 이상 32,000 이하 수식에는 괄호와 사칙연산만 가능 나누기 연산에서 나머지는 무시 최솟값이 8보다 크면 -1을 return 풀이 단순하게 사칙연산 말고도 55 같이 숫자를 붙여서도 표현할 수 있는 걸 확인 그리고 문제가 짧은만큼 문장 하나하나가 다 핵심이다...

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 총 3 가지 모양의 그래프 존재 여러 그래프들로 향하는 임의의 정점(이후 중점이라고 표현)이 존재 간선 정보가 담긴 배열 정점의 번호와 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 반환 조건 그래프의 수는 2개 이상 존재 간선은 최대 1,000,000개 풀이 일단 자료가 1,000,000개 라면 단순한 반복문으로 푸는 거에 문제가 생긴다. Dictionary로..