늦깎이 IT

[백준 16234번 인구 이동 URL] 우선 문제에서는 조건에 의해 모든 국경선을 연 후에, 그 다음 인구이동을 시작하라고 나와있지만 딱히 순서는상관이없다. 1) 어느 한 나라와 연합이 될 수 있는 모든 나라를 찾는다.2) 연합이 될 수 있는 나라들을 모두 찾았으면 인구이동을 시작한다.3) 인구이동이 끝났으면 다시 1)번을 수행한다. 즉, 다음과 같은 나라들이 있다면 (L=20, R=50)인구가 50인 나라부터 탐색을 시작해서 연합될 수 있는 나라들을 찾는다. 어느 한 나라로부터(인구 50인 나라) 연합할 수 있는 모든 나라들을 찾았으면 인구이동을 시작한다.여기서 하나의 연합으로 묶여진 나라들은 방문 여부를 나타내는 2차원 배열에 표시를 해 둔다.아래와 같이 인구이동이 끝나면, 다시 방문하지 않은 나라부..

[백준 16236번 아기상어 URL] 1. 종료 조건- N x N 배열을 모두 탐색했는데도 잡아먹을 수 있는 물고기가 없는 경우- 탐색을 진행하면서 잡아먹을 수 있는 물고기를 찾지 못했는데 모든 방향이 막혀있는 경우 2. 탐색 조건- 아기상어의 크기보다 작거나 같을 경우 이동할 수 있다. (아기상어의 크기 >= 물고기의 크기) 3. 비교 조건 - 아기상어가 잡아먹을 수 있는 물고기를 최초로 만난 경우, 그 물고기를 만나기까지의 이동거리를 저장해야한다. - 최초로 물고기를 만났다고 해서 탐색을 종료하는 것이 아니라, 그 이동거리만큼의 모든 위치를 탐색해야한다. - 예를 들어, 아래 그림을 보자. 아기상어의 위치로부터 왼쪽에 있는 물고기를 먼저 발견했다고 해서, 바로 그 물고기를 먹은 후에 탐색을 종료하면 ..

[백준 16235번 나무재테크 URL]https://www.acmicpc.net/problem/16235 [기본 로직]1. 1년(봄~겨울)이 지난 후 추가되는 영양분을 저장하는 배열 A를 선언합니다.2. 각 계절마다 참고(?)해야할 현재의 영양분을 저장하는 배열 map을 선언합니다.3. 각 위치(row, col)마다 나무의 갯수를 저장하기 위해 List 배열을 선언합니다. [구체적인 로직]1. doSpringAndSummer() 메소드이 메소드에서는 봄, 여름에 일어나는 일을 함께 처리합니다.각 위치(row, col)마다 저장된 나무를 순회하기 전에 나무의 나이를 기반으로 오름차순으로 정렬한 뒤,나무의 나이와 그 위치에 있는 영양분을 비교하여 나무의 나이를 +1 증가시킬것인지 죽일것인지 결정합니다.여기서..

[백준 2583번 영역 구하기 URL] [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include #include #include using namespace std; #define MAX 100 int N, M, K;int map[MAX][MAX];int num[MAX];bool visited[MAX][MAX];int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0}}; typedef stru..

[백준 1012번 유기농 배추 URL]https://www.acmicpc.net/problem/1012 [유사 문제]2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2667번] 단지번호붙이기 이 문제는 [백준 2667번 단지번호 붙이기]와 거의 똑같은 문제라고 볼 수 있습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109#include #inc..

[백준 2206번 벽 부수고 이동하기 URL]https://www.acmicpc.net/problem/2206 [비슷한 유형의 문제]2019/02/14 - [알고리즘 문제/백준(BOJ)] - [백준 1194번] 달이 차오른다, 가자. 이 문제를 풀기위해서 고려해야할 사항은 다음과 같습니다. 1. 벽을 한번도 부수지 않고 이동하는 경우와 벽을 한번 부수고 이동하는 경로를 따로 체크해야합니다. 2. 2차원 배열 visited가 아닌 3차원 배열 visited[2][row][col]을 선언하여 벽을 부수지 않고 이동하는 경우는 visited[0][row][col]에 방문체크를 하고 벽 하나를 부수고 이동하는 경우에는 visited[1][row][col]에 방문체크를 해줍니다. 3. Node 클래스의 jump ..

[백준 1194번 달이 차오른다, 가자. URL]https://www.acmicpc.net/problem/1194 이 문제를 풀기위해 생각해야 하는 것은 크게 2가지가 있습니다.1. 획득하는 열쇠 정보를 어떻게 update하고, 문을 만날때마다 어떻게 확인할 것인가??2. 다른 탐색문제들과는 달리 이미 지나온 길을 다시 되돌아가야하는 경우가 발생합니다. [열쇠정보 저장하기]a부터 f까지의 열쇠는 A부터 F까지의 문을 열 수 있습니다.열쇠를 획득할 때마다 획득한 열쇠정보를 저장할 수 있어야합니다. 열쇠정보를 저장하는 방법은 "비트 마스크"로 표현하는 방법이 있습니다. 각각의 열쇠를 비트와 십진수로 표현하면 아래와 같습니다. 열쇠 비트 표현 십진수 a0 0 0 0 0 1 1 b 0 0 0 0 1 0 2 c ..

[백준 11559번 Puyo Puyo URL]https://www.acmicpc.net/problem/11559 문제를 풀기위해 생각해야할 것은 다음과 같습니다. 1. 상하좌우 인접한 뿌요가 4개 이상일 경우 터진다.이 조건으로 인해 BFS탐색을 하면서 각 뿌요의 좌표를 저장해야 합니다. 뿌요의 수가 4개 이상일 경우에는해당 뿌요들의 자리를 '.' 으로 교체하는 것이 뿌요를 터뜨리는 행위입니다.그렇기 때문에 뿌요의 좌표와 갯수를 파악하기 쉬운 자료구조는 List입니다. 2. 한 라운드에 4개 이상인 뿌요가 여러 개 있다하더라도 연쇄반응은 1회로 간주한다.이 조건으로 인해 반복문을 돌릴 때 연쇄반응을 카운트하는 ans 변수의 증가 타이밍을 잘 잡아야 합니다. 3. 한 라운드가 끝난 뒤에 남아있는 모든 뿌요..