해시(hash)8 [Programmers] 전화번호 목록 https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 전화번호 목록에 있는 모든 번호들을 해시 테이블(hash table)에 저장한 다음, 각각의 전화번호들에 대해 앞에서부터 1, 2, $\cdots, $ 전체 글자 만큼의 접두사에 해당하는 전화번호가 해시 테이블에 존재하는지 확인한다. 구현 해시 테이블의 역할을 수행할 컨테이너로 std::unordered_map 형식의 컨테이너를 활용하였다. [스포 주의] 아래 '더보기'를 누.. 2024. 1. 7. [Programmers] [1차] 뉴스 클러스터링 https://school.programmers.co.kr/learn/courses/30/lessons/17677 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 주어지는 두 개의 문자열에 대해 각각, 두 글자씩 끊어 읽었을 때 모두 알파벳으로 이루어져 있으면 끊어 읽은 문자열의 등장 횟수를 기록한다. 이때 두 개의 알파벳으로 이루어진 문자열이 등장하는 횟수 중 최솟값은 교집합에 해당하며, 최댓값은 합집합에 해당하는 값임에 착안하여 자카드 유사도를 계산한다. 구현 풀이 1) 두 글자씩 끊어 읽은 문자를 STL의 컨테이너를 활용해 기록하.. 2024. 1. 6. [Baekjoon] 20920번: 영단어 암기는 괴로워 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 해결 과정 착안 문자열을 키로 가지며, 등장하는 빈도 수를 값으로 저장하여 문제를 해결하고자 std::map과 같은 컨테이너를 활용하고자 하였다. 이때 키의 자료형이 문자열 형이므로 해시 테이블(hash table)을 사용하는 것이 일반적으로 속도 측면에서 유리하기 때문에 std::unordered_map 클래스를 사용해 데.. 2023. 7. 9. [Baekjoon] 1920번: 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해결 과정 착안 반복적으로 탐색을 빠르게 수행하는 것이 문제에서 요구하는 핵심이므로, 아래와 같이 일반적으로 탐색 속도가 매우 빠른 것으로 알려져 있는 방법으로 각각 문제를 해결하고자 하였다. 해시(hash) 맵을 사용한 방법 이진 탐색(binary search, 이분 탐색)을 사용하는 방법 구현 [스포 주의] (해시 맵 사용) 아래 '더보기'.. 2023. 6. 9. [Baekjoon] 7785번: 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 해결 과정 착안 많은 문자열에 대해, 입출력마다 요소를 보관할 컨테이너에 요소가 존재하는지 판단해야하기 때문에 해시(hash) 코드를 키로 가지는 std::map 클래스를 이용하고자 했다. 이때 주어지는 문자열의 길이가 5 이하이므로 매우 짧은 편에 속해, unsigned long long 자료형과 다항 롤링 해시(polynomial rolling ha.. 2023. 6. 7. [Baekjoon] 25192번: 인사성 밝은 곰곰이 https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 문제 해결 과정 착안 동일한 값을 가지는 요소를 중복하여 저장하지 않고 한 번만 저장하는 STL의 컨테이너를 사용하여 닉네임 문자열을 저장한 다음, ENTER 문자열이 입력되기 직전 또는 프로그램 종료 직전까지 컨테이너에 들어온 요소 수를 출력하고자 했다. ENTER 문자열이 입력된 뒤에는 컨테이너를 초기화하여 처음부터 다시 요소 수를 계산하고자 하였다. 구현 처음엔 별 생각.. 2023. 6. 4. 이전 1 2 다음
