전체 글 (209) 썸네일형 리스트형 [프로그래머스 코딩테스트 고득점 Kit - 해시] 위장 해시 문제 programmers.co.kr/learn/courses/30/lessons/42578 [문제 풀이] 한 가지 이상의 의상을 사용하여 조합할 수 있는 경우의 수를 구하는 문제입니다. 다른 종류의 옷들을 조합하는 문제입니다. 주의할 점은 하나의 옷을 입고 나면 나머지는 입지 않는 경우가 존재합니다. 간단한 경우의 수 문제입니다. 2개의 옷과 3개의 모자가 존재할 때, 가능한 조합의 수가 6개라는 건 자명합니다. 하지만 입지 않는 경우를 넣어 조금 문제를 어렵게 보이도록 하였습니다. 우선 map을 하나 만들고 주어진 의상 배열을 순회하면서 key로는 의상의 종류를, value로는 가짓수를 기록합니다. 예를 들어 [[yellow_hat, headgear], [blue_sunglasses, eyewe.. [프로그래머스 코딩테스트 고득점 Kit - 해시] 전화번호 목록 문자열 문제 programmers.co.kr/learn/courses/30/lessons/42577 www.acmicpc.net/problem/5052 위 문제와 동일한 문제입니다. [문제 풀이] 주어진 문자열이 접두어에 해당하는지 판별하는 문제입니다. 해시 파트에 있지만 문자열로 풀었습니다. 이 문제를 처음 백준 온라인 저지에서 봤을 때 해시로 푼다는 생각은 전혀 없었습니다. 정해라고 생각했던 풀이는 문자열을 정렬하고 인접한 두 문자열을 비교하는 방법이었습니다. $O(NlogN)$의 시간 복잡도로 해결이 가능합니다. 그리고 트라이 자료구조를 이용하여 $O(NL)$의 시간 복잡도로 해결이 가능합니다. 트라이의 연습을 위해 트라이 자료구조를 사용하였습니다. 트라이에 문자열을 넣으면서 문자열의 끝에 해당하는.. [프로그래머스 코딩테스트 고득점 Kit - 해시] 완주하지 못한 선수 해시 문제 programmers.co.kr/learn/courses/30/lessons/42576 [문제 풀이] 두 집합의 차집합을 구하는 문제입니다. 집합에서 중복을 허용했으므로 set이 아닌 map을 사용하였습니다. map의 key로 문자열을, value로 동명이인의 수를 기록합니다. 그리고 completion에서 명단을 하나씩 확인하면서 map의 value를 1씩 줄여나갑니다. value가 1이었던 경우 map에서 삭제합니다. 두 집합의 크기 차이가 1이었으므로 위의 과정을 완료하면 map에는 하나의 값만 남게 되고 그 값의 key(string)를 출력하면 해결이 가능합니다. c++의 map은 레드블랙트리 기반이므로 삽입, 삭제, 탐색 모두 $O(logn)$의 시간 복잡도를 갖습니다. Java의 H.. [백준 12899] 데이터 구조 세그먼트 트리 문제 www.acmicpc.net/problem/12899 www.acmicpc.net/problem/1168 해당 문제의 응용문제입니다. 위 문제도 같이 푸는 것을 권장합니다. [문제 풀이] 2번 쿼리마다 k번째 수를 반환하는 문제입니다. 1번 쿼리는 자연수를 추가하는 역할입니다. 쿼리의 개수가 심상치 않습니다. 쿼리의 개수를 보니 매 쿼리를 logn정도로 처리해야 시간 초과가 걸리지 않을 것 같습니다. 세그먼트 트리로 접근해 봅시다. 이 문제를 처음 세그먼트 트리로 생각해보면 상당히 막막합니다. 약간의 팁을 드리면 대부분의 세그먼트 트리 문제는 구간 합, 최소, 최대를 생각하고 접근하는 것이 좋습니다. 세그먼트 트리라고 생각은 들지만 평소에 풀던 세그먼트 트리와는 조금 다른 형태입니다... [붕어빵 꼬리먼저 팀] 6회차 - 학습 마무리 2021/02/13 동계 모각코 6회차 오늘 공부하고자 했던 정점 분할에 대한 이해와 문제 풀이를 마쳤습니다. [정점 분할] www.acmicpc.net/problem/2316 최대 유량에서 정점의 중복마저 제거하는 문제입니다. 정점 분할은 하나의 알고리즘이라기보다는 최대 유량 문제에서 그래프를 구성하는 하나의 스킬입니다. 일반적인 최대 유량 문제에서는 간선의 용량만 신경 써줘도 문제가 해결이 가능했으나 위 문제처럼 정점의 중복을 예방하기 위해서는 정점 분할이 필요합니다. 우선 최대 유량 문제에서는 간선을 선택하는 순서에 상관없이 최적의 선택을 하기 위해 음의 유량이라는 개념을 도입하였습니다. 단순하게 최대 유량을 흘릴 때에는 간선을 선택하는 순서에 따라 최적이 달라지는 문제가 발생합니다. 그러나 그런 .. [붕어빵 꼬리먼저 팀] 6회차 - 학습 계획 2021/02/13 동계 모각코 6회차 오늘 학습할 주제는 정점 분할입니다. www.acmicpc.net/problem/2316 해당 문제 풀이를 목표로 하겠습니다. [붕어빵 꼬리먼저 팀] 5회차 - 학습 마무리 2021/01/28 동계 모각코 5회차 오늘 공부하고자 했던 최대 유량에 대한 이해와 문제 풀이를 마쳤습니다. [최대 유량] www.acmicpc.net/problem/17412 최대 유량을 이용하여 두 도시를 얼마나 많이 왕복할 수 있는지를 구하는 문제입니다. 우선 해당 문제에서는 정석적인 최대 유량 문제라기보다, 간선이 추가됨에 따라 용량이 1씩 늘어나는 방식으로 생각합니다. 1번 도시에서 2번 도시까지 흘릴 수 있는 유량의 최대를 구한다면 자연스럽게 1번 도시와 2번 도시를 왕복할 수 있는 횟수를 구할 수 있게 됩니다. 간선이 중복될 수 있으므로 용량을 계속 더해줄 수 있도록 합니다. N의 값이 작으므로 2차원 배열을 사용하였습니다. 사용 가능한 알고리즘 중 Edmonds-Karp 알고리즘을 사용하.. [붕어빵 꼬리먼저 팀] 5회차 - 학습 계획 2021/01/28 동계 모각코 5회차 오늘 학습할 주제는 네트워크 플로우입니다. www.acmicpc.net/problem/17412 해당 문제 풀이를 목표로 하겠습니다. 이전 1 ··· 21 22 23 24 25 26 27 다음
