4Legs_Archives

문제 링크 : www.acmicpc.net/problem/20113 20113번: 긴급 회의 투표 결과 1번 플레이어가 1표, 3번 플레이어가 2표, 4번 플레이어가 1표를 받아 3번 플레이어가 퇴출된다. www.acmicpc.net 단순 구현 문제이다. 동일 득표자가 2명 이상일 시 아무도 퇴출되지 않음에 유의하자. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; typedef pair p; int n, votes[101]; //0: 무..

문제 링크 : www.acmicpc.net/problem/20112 20112번: 사토르 마방진 사토르 마방진에 대해 들어본 적이 있는가? 사토르 마방진은 간단히 말하면 "가로로 읽었을 때와 세로로 읽었을 때 똑같이 읽히는 단어 집합"이다. 예시로는 다음과 같은 것들이 있다. 라팔아 팔 www.acmicpc.net 저번달에 진행됐던 고리콘 문제들을 하나씩 풀이해볼 예정이다. 대회 당일에 토익시험이 겹쳐 대회에 참여하지는 못했지만, 기출문제들을 풀어보고자 카테고리를 개설했다. 맨 처음 문제답게 상당히 간단한 문제이다. 마방진의 크기도 최대 100으로 작기 때문에, 단순한 비교로도 충분히 문제를 해결할 수 있다. 마방진의 i행 j열 문자가 j행 i열 문자와 같은지만 확인해주면 된다. [코드] 1 2 3 4 ..

문제 링크 : www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 그리디 알고리즘으로 해결이 가능한 활동 선택 문제이다. 핵심은 각 문제들을 어떤 기준으로 정렬할 것인지(즉, 어떤 문제의 우선순위를 높게 잡을 것인지)이다. ① 우선 당연히 받을 수 있는 컵라면의 갯수가 많은 문제를 우선적으로 풀어야 할 것이다. 하지만 위와 같은 상황에서, 보상이 8개인 문제를 먼저 풀게 된다면 데드라인이 1인 문제 하나를 풀 수 없게 된다. 보상이 8인 문제는 데드라인이 3이기 때문에 ..

문제 링크 : www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 평소에 전공지식 공부를 병행한 사람이라면 무언가 번뜩할 것이다. 이 문제는 페이지 교체 알고리즘에 빗대어 설명할 수 있기 때문이다. [OS/운영체제] 페이지 교체 (Page Replacement) - (2) FIFO (First-In, First-Out) Page Replacement FIFO는 가장 단순한 페이지 교체 알고리즘으로, 메모리에 옮겨진 메모리들 중 가장 오래된 페이지를 Victim으..

문제 링크 : www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제가 그리디 알고리즘으로 해결할 수 있다는 것을 캐치한다면, 일반적으로는 더 자릿수가 큰 수의 앞 자리 알파벳부터 큰 수를 부여하는 식의 접근을 할 것이다. 하지만 이러한 접근의 경우 각종 예외 케이스들을 관통하는 하나의 코드를 구현하기 매우 까다롭다. 예를 들어 ABC와 BB 9개, 총 10개의 단어에 대해 A = 9, B = 8, C = 7 이라면 987 + 88 * 9 = 1,77..

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..

문제 링크 : www.acmicpc.net/problem/1602 1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 문제에서 쿼리 형식으로 출발, 도착 노드에 대한 최소 시간을 묻고 있으므로, 모든 노드에 대해 다른 모든 노드까지의 최단경로를 구하는 플로이드-와샬 알고리즘이 적절할 것이다. 다만 도시 별 괴롭힘 시간이라는 별도의 가중치가 존재하는데, 멍멍이는 원숭이가 지나는 경로 중 가장 괴롭힘 시간이 긴 도시에서 괴롭히게 된다. 다만, 플로이드-와샬 알고리즘을..

문제 링크 : www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제를 그래프의 관점에서 이해하면 다음과 같다. ① 서로 연결된 사람은 같은 위원회에 참석한다 = 그래프에서 연결된 노드들은 같은 위원회(그룹)로 취급한다. ② 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. = 그래프의 모든 정점에 대해 그룹화한다. 즉 그래프의 모든 정점에 대해 연결된 노드끼리 그룹(위원회)으로 묶은 후, 그룹의 대표 노드에 대해 다른 모든 노드에 대한 전파 시..

문제 링크 : www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드-와샬 문제라는 것을 캐치하는 것이 문제 해결의 80%는 되는 것 같은 문제이다. 각 물건들의 무게 관계를 그래프의 형태로 이해하고, 문제에서 요구하는 것이 그래프의 각 노드에서 도달할 수 없는 노드들의 갯수이므로 모든 노드에서 다른 모든 노드로의 최단거리를 구하는 플로이드-와샬 알고리즘이 적절함을 캐치해야 한다. 플로이드-와샬 알고리즘(Floyd-Warshall ..

레드-블랙 트리 (Red-Black Tree) 이전 게시글에서 AVL 트리에 대해 설명하였다. AVL 트리는 효율적인 BST 검색을 위해, 트리를 가능한 균형있게 유지하는 것이 핵심이었다. 하지만 삽입과 삭제의 효율이 좋지 않은 문제가 있다. 레드-블랙 트리의 균형을 맞추기 위한 다른 방법으로 등장한 트리이다. 정의 레드-블랙 트리 BST의 모든 노드가 Black 또는 Red로 칠해진 트리로, 다음과 같은 규칙을 가진다. RB1. root 노드와 모든 외부 노드(External Node)는 Black Node이다. (RB1' : 내부 노드로부터 외부 노드로의 포인터는 Black이다. 포인터는 노드를 잇는 간선을 의미한다.) RB2. root에서 외부 노드까지의 경로는 두 개의 연속적인 Red Node를 ..