https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 필요한 배경지식 이분탐색, 매개 변수 탐색 : parametric search 문제 해결 방법 답으로 출력될 값(배정될 예산)을 기준으로 하여, 매개 변수 탐색을 하면 됩니다. 즉, 이분탐색으로 배정될 예산을 구하는 과정에서 그 예산이 배정될 수 있으면 예산을 늘리고 배정될 수 없다면 줄이면서 가장 큰 값을 찾아나가는 방법입니다. 이분탐색의 구현은 lower bound 방식을 활용하여 구현했..
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 처음에는 세그먼트 트리를 이용하여 풀어 보기 위해 많은 시간 고민했지만 쉽지 않았습니다. 결국은 태그에서 힌트를 얻어 유니온 파인드를 이용하여 문제를 해결했습니다. 필요한 배경지식 유니온 파인드 : Union-Find (Disjoint-set) 문제 해결 방법 g가 주어질때 들어갈 수 있는 가장 큰 번호의 게이트에 비행기를 도킹해 주면 비행기를 최대로 도킹할 수 ..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 방법 BFS를 이용한 시뮬레이션 구현문제입니다. 모든 인접한 나라와 나라사이에 국경선이 열려있는지, 즉 인접한 나라로 이동할 수 있는지 확인한 다음, 만약 이동할 수 있다면 그 나라를 시작점으로 하여 BFS를 수행하고 인구이동 결과를 업데이트 합니다. 이때 방문처리도 같이 해주어야 합니다. 노드마다 이동할 수 있는지 확인하는 코드가 chkAlly 함수에 구현되어 있고 시작..
백준 14891번 - 톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 해결 방법 나머지 연산을 잘 이용하면 문제를 쉽게 해결할 수 있습니다. 아래의 그림은 톱니바퀴의 시계방향 회전과 그 상태정보를 0~7인덱스로 나타낸 그림입니다. 위 그림과 같이 톱니바퀴의 상태정보를 0~7로 인덱싱하고 12시방향의 상태정보 인덱스를 now라고 한다면,비교해야 할 위치는 다음과 같습니다. 오른쪽과 맞닿은 톱니바퀴 인덱스 = (now+2)%8 왼쪽과 맞닿은 톱니바퀴 인덱스 ..
백준 21277번 - 짠돌이 호석
https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 문제 해결 방법 어려운 알고리즘을 필요로 하진 않지만 구현이 힘든 문제였습니다. 퍼즐의 최대 크기가 50x50으로 작기 때문에 완전탐색으로도 충분히 풀어낼 수 있습니다. 완전탐색을 위해서 회전된 퍼즐마다 위와 같은 상황들을 모두 비교해야 하는데 그러기 위해선 최대 150*150 크기의 배열이 필요합니다. 여기서 수행시간을 줄이기 위해서는 N,M의 크기마다 정확한 인..
https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제 해결 방법 단순한 너비 우선 탐색(BFS) 문제입니다. 오른쪽과 아래로만 이동할 수 있다는 것과 한 번에 이동할 수 있는 칸의 수는 현재 밟고 있는 칸에 쓰여 있는 수라는 것만 잘 처리해 주면 주면 됩니다. C++ 전체 코드 #include #define xx first #define yy second using namespace std; using pii = pair; int N; int m[..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제 해결 방법 스택2개 또는 리스트를 이용하여 해결 할 수 있는 문제입니다. 리스트를 이용하여 원소를 삽입, 삭제하는것 보다 스택2개를 이용하여 해결하는 것이 더 빠른 방법이지만 리스트를 활용해 봤습니다. 리스트의 erase를 사용할때 반복자가 가리키는 원소가 없어지기 때문에 반복자가 참조할 위치를 변경해 주어야 합니다. C++ 전체 코드 #include using namespace st..
백준 15806번 - 영우의 기숙사 청소
https://www.acmicpc.net/problem/15806 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 큐와 간단한 규칙을 이용한 구현문제였습니다. 문제 해결 방법 곰팡이는 1일이 지나면 위와 같이 8개로 증식합니다. 단순한 풀이 방법으로 1일마다 곰팡이 하나하나 8개로 나누어 저장하는 방법을 생각해 봅시다. N이 최대 300이고 t가 최대 10000이므로 최악의 경우 초기 곰팡이가 90000개이고 10000일 후의 결과를 알아야 할때 대충 (90000 * 8 * 10000) 만큼의 수행시간이..