본문 바로가기

분류 전체보기

 (263)
[프로그래머스 코딩테스트 고득점 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 해당 문제 풀이를 목표로 하겠습니다.
[백준 11501] 주식 그리디 문제 www.acmicpc.net/problem/11501 [문제 풀이] N개의 주가가 주어졌을 때, 최대 이익을 내는 문제입니다. N의 제한이 1,000,000입니다. 테스트 케이스까지 존재하므로 무조건 $O(N)$의 시간 복잡도로 해결해야 합니다. 우선 최대 이익을 내는 방법을 생각해보겠습니다. 주식을 계속 사들인 다음에 최대 가치일 때 한 번에 팔아버리면 당연히 최대로 이익을 얻을 수 있습니다. 예를 들어 주가가 1, 5, 10일 때, 1을 사고 굳이 5에 팔기보다, 10에 파는 것이 이득입니다. 즉, 현재 구입하는 시점 이후에서 가장 비쌀 때 팔아버리면 되고 현재 구입하는 시점이 가장 비싸다면 사지 않는 것이 이득입니다. 문제는 현재 구입하는 시점 이후에 가장 비싼 때가 언젠지 모른다는 것..
[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ 다이나믹 프로그래밍 문제www.acmicpc.net/problem/20500친숙한 문제입니다.[문제 풀이] 1과 5로만 주어진 N자리 자연수 중 15의 배수의 개수를 찾는 문제입니다.15의 배수라고 하니 별다른 특징을 찾기가 힘듭니다. 조금 형태를 바꿀 필요가 있어 보입니다. 15는 3의 배수이면서 5의 배수입니다. 3과 5는 배수를 구할 때 상당히 익숙한 수입니다.그러므로 15의 배수인 수를 구하기 위해 3의 배수이면서 5의 배수인 수를 구해보겠습니다. 우선 3의 배수는 모든 자리의 수를 전부 더하고 3으로 나눴을 때 나누어 떨어지는 성질이 있습니다.그리고 5의 배수는 1의 자릿수가 0이거나 5입니다. 그러므로 15의 배수는 모든 자리의 수를 전부 더한 값을 3으로 나눴을 때 나누어 떨어지면서, 1의 ..

티스토리툴바