free from

문제소개 1348주차장은 이분매칭 + 이분탐색 문제입니다. 차 한대씩 주차 공간 1곳에 주차하는 것이기 때문에 직관적으로 이분매칭을 생각할 수 있습니다. 저는 이 문제를 MCMF 그러니깐 SPFA로 해결하려고 시도했다가 "아 그러면 안되는 구나"를 깨달았고 SPFA와 이분매칭을 조금더 생각할 수 있었습니다. 문제풀이 3 13 .C.....P.X... XX.......X..P XX.....C..... 문제는 다음과 같은 입력값을 받습니다. 그러므로 각각의 차들에서 각각의 주차공간까지 최단거리를 계산해야 합니다. 이때 계산은 BFS로 진행합니다. 그리고 계산한 최단경로 값을 노드와 엣지로 정리합니다. 왼쪽이 차량이며 오른쪽이 주차공간입니다. 다음 그래프에서는 2가지 경우의 이분매칭을 만들 수 있습니다. 1 ..

문제소개 1637날카로운 눈은 이분 탐색 문제입니다. 문제 분류가 DFS로 분류되어 있어서 어떻게 하면 DFS로 풀 수 있을까를 생각하느라 조금 오래 걸렸습니다. (DFS로 풀진 못했습니다.) 문제의 입력값이 20억 이므로 O(N)이 아닌 O(logN)의 알고리즘을 생각해야 하며 O(logN)에 어울리는 탐색 방법으로 이분 탐색을 생각할 수 있습니다. log2(2,000,000,000) ≒ 602,059,991 그러면 어떻게 생각해야 '1637날카로운 눈' 문제에 이분 탐색을 적용할 수 있을까요? 그 해답의 포인트는 홀수 개수를 가진 특정 정수는 하나라는 점입니다. 문제풀이 4 1 10 1 4 4 1 1 5 1 6 10 1 다음과 같은 입력값을 아래와 같이 표로 정리했습니다. 1 2 3 4 5 6 7 8..

문제소개 1253좋다 문제는 투 포인터 알고리즘 문제입니다. 배열에서 다른 두 개의 숫자를 더하여 배열 내의 다른 숫자를 만드는 문제입니다. 예를 들어 (idx:숫자) 아래와 같이 숫자 배열이 있습니다. idx 1 2 3 4 5 숫자 0 -10 -2 4 2 3: -2와 4: 4를 합하여 5: 2를 만들 수 있습니다. 이렇게 만들 수 있는 숫자의 개수를 구하는 문제입니다. 숫자는 정수인 점을 유의하세요. 문제 풀이 이 문제를 러프(rough)하게 풀면 O(N^3)으로 풀 수 있습니다. 그런데 2000개의 입력값을 가지므로 1초 내에 풀기는 어렵기 때문에 O(N^2)로 풀 수있는 투 포인터 알고리즘으로 풀어야 합니다. 그러니깐 배열을 먼저 정렬해야 합니다. idx 1 2 3 4 5 숫자 -10 -2 0 2 ..

문제소개 7344나무막대 문제는 LIS 문제이며 해당 문제는 2001년 ACM-ICPC 대전 기출 문제입니다. 나무 막대기 가공 순서를 비교하는 문제로 비교 값은 길이와 무게 2개 입니다. 길이를 I, 무게를 W라고 하면 I 2:(3,5) -> 3(4:9) 순서로 한 번의 준비 작업으로 처리할 수 있습니다. 그리디한 해결방법이네요. 소스보기

문제소개 8979올림픽 문제는 올림픽에 참가하는 국가 간의 순위를 정하는 문제입니다. 특정 국가를 입력 받고 그 국가의 순위를 출력하는 문제로 금,은,동 개수를 비교하여 순위를 정해야합니다. 금 > 은 > 동를 획득한 개수가 많은 순으로 순위가 결정 됩니다. 문제 해결 비교를 조금더 쉽게 하기 위해서 금 은 동을 점수화 했습니다. 금 : 100,000점 은 : 1 점 동 : 0.000,001점 점수화 후 우선순위 큐에 넣어 순서대로 순위를 정해줬습니다. 소스보기

문제소개 3108 로고는 DFS문제 입니다. 5가지 명령을 수행하는 거북이가 있습니다. "5개의 명령을 수행한다"라고 되어 있기 때문에 복잡해 보이지만 우리가 생각할 것은 PU(연필을 올리는 명령)를 최소화하는 방법입니다. PU의 용도는 직사각형을 그릴 필요가 없는 좌표에서 PU명령어를 수행합니다. 문제에 주어진 직사각형 N개를 제외한 직사각형은 그릴 수 없다라고 명시되어 있기 때문입니다. 그렇다고 하면 직사각형을 그릴 때 교차되는 선분이 있거나 겹쳐지는 선분이 있는 경우는 PU명령을 수행하지 않고 연결된 직사각형을 그릴 수 있습니다. 문제풀이 10 9 8 7 6 2 2 2 2 5 2 3 3 2 4 1 1 2 3 3 2 3 1 2 2 4 4 4 4 2 1 1 4 5 5 4 1 1 1 1 1 4 5 5 4..

문제소개 1199 오일러 회로 문제는 오일러 경로 문제입니다. ㅎ,ㅎ; 오일러 경로란 그래프에 존재하는 모든 간선을 한번씩만 사용하여 연결하는 경로이며 그래프에서 오일러 경로가 존재하기 위해서는 그래프 내의 모든 노드는 2배수의 차수를 가져야합니다. 여기서 차수란 노드에 인접한 간선을 의미합니다. 이러한 조건을 이용해서 그래프 내에서 오일러 경로의 존재 유무를 파악할 수 있습니다. 자세한 설명은 링크를 참조해주세요. 문제풀이 오일러 경로는 Hierholzer's algorithm을 이용하여 해결할 수 있으며 알고리즘 순서는 다음과 같습니다. 0. 해당 그래프에 오일러 경로가 존재 1. 적당한 시작 노드를 선택합니다. 2. 노드에 연결되어 있는 간선들 중 사용하지 않은 간선을 따라 다음 노드로 이동합니다...

문제소개 5721 사탕 줍기 대회 복잡한 부분을 어떻게 하면 간단하게 정리할 수 있을까를 생각하는게 중요한 것 같습니다. 아래 그림과 같이 3 X 3 칸에서 11개의 사탕을 줍는다면 윗 줄,아랫 줄, 좌, 우의 사탕은 먹지 못합니다. 못 먹는 사탕을 0으로 바꾸는 작업을 하게 된다면.. 문제는 미궁 속으로 빠집니다. 이러한 복잡한 부분을 어떻게 간단하게 바꿀 수 있을까요? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 문제풀이 1 8 2 1 9 1 7 3 5 2 1 2 10 3 10 8 4 7 9 1 7 1 3 1 6 다음과 같은 그림이 있습니다. 3 X 3 칸에서 10개의 사탕을 줍는다면 윗 줄, 아랫 줄은 못 먹습니다. 그러나 3 X 3이 속한 3행의 1, 10은 먹을 수 있습..