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) 만큼의 수행시간이..
https://www.acmicpc.net/problem/20549 20549번: 인덕이의 고민 오리를 좋아하는 인덕이는 오리를 바라보며 마음의 안식을 얻는다. 오리는 N×N의 정사각형 모양으로 이루어진 인경호에서 유유자적하게 헤엄을 친다. 인경호는 1×1 크기의 칸으로 나누어져 있 www.acmicpc.net 사실 비트마스킹문제를 풀고 싶어서 태그를 보고 문제를 풀었는데 비트마스킹을 몰라도 풀 수 있는 문제였습니다. 필요한 배경지식 다익스트라 문제 해결 방법 NxN 격자에서 오리가 이동할 수 있는 방법은 3가지가 있습니다. 체스룰에서 나이트, 비숍, 룩의 이동과 같은 이동방법인데 각각의 이동방법에 가중치가 존재합니다. 이것을 '오리가 받는 과부하의 양' 이라고 하여 각각 A,B,C로 입력을 받는데, 이..
www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net 필요한 배경지식 비트마스킹, 조합론에 대한 지식이 필요합니다. 문제 해결 방법 문제에서 구해야 할 테스트문장은 N개의 단어를 조합하여 만들 수 있으며 소문자'a'부터 'z'까지 26개가 문장에 모두 포함되어 있어야 합니다. 어떻게 N개의 단어를 조합하여 테스트 문장을 만들 수 있을지 생각해 보기전에, 문장안에 a~z까지의 문자가 존재하는지 확인할 방법을 먼저 생각해 봅시다. 확인할 개수가 26개밖에 되지 않기 때문에 가장..