■ 알고리즘 문제 풀이/BOJ (48) 썸네일형 리스트형 [BOJ] 백준 1764. 듣보잡 ▶문제설명[BOJ] 1764. 듣보잡 https://www.acmicpc.net/problem/1764 ▶Hint set을 이용하면 쉽게 풀 수 있는 문제이다. 해싱을 연습해볼 수 있는 문제이기도 하다. STL의 set은 레드블랙트리로 구현되어 있다고 알려져있는데, 레드블랙트리는 삽입/삭제/검색에 O(logN)의 시간이 걸리는 자료구조이며, 중복을 허용하지 않는다는 특징이 있다. 듣도 못한 사람의 이름을 입력 받아 set에 저장해놓은 뒤, 보도 못한 사람의 이름을 입력받아 set에서 검색했을 때, 해당 이름이 존재하면 듣도 보도 못한 사람으로 분류한다. 듣도 보도 못한 사람들의 이름을 하나의 vector에 모두 저장하고, 사전 순으로 정렬시킨 뒤 출력하면 정답이 된다. ▶시간 복잡도 [제약 사항] N :.. [BOJ] 백준 2468. 안전 영역 ▶문제설명[BOJ] 백준 2468. 안전 영역 https://www.acmicpc.net/problem/2468 ▶Hint BFS/DFS 문제이다. 1. NxN 배열에 높이 정보를 입력받으면서 가장 높은 값과 낮은 값을 구한다. 2. 1에서 구한 가장 낮은 값부터 가장 높은 값까지 모든 경우에 대하여 NxN배열의 모든 인덱스에 대해 안전 영역을 구하는 BFS를 수행하며 BFS를 수행한 횟수를 카운트하면서 카운트 값의 최대 값을 구한다. 인접한 안전 영역을 체크하는 BFS를 수행하여 visited배열에 안전 영역을 true값으로 저장하고 visited[i][j]==false인 경우에만 BFS를 수행하도록 구현한다. ▶시간 복잡도최악의 경우 O(N^6) 만에 정답을 구할 수 있다. N = 100, 최소 높이.. [BOJ] 백준 16236. 아기 상어 ▶문제설명[BOJ] 백준 16236. 아기상어 https://www.acmicpc.net/problem/16236 ▶HintBFS 알고리즘을 활용해서 먹을 수 있는 물고기를 먹으러 가는데 걸리는 시간을 구하고, 먹을 수 있는 물고기들을 vector에 담는다. - 먹으러 가는데 걸리는 시간이 동일한 물고기가 둘 이상일 경우는?BFS를 통해 먹을 수 있는 물고기를 vector에 담아서 r(행)을 기준으로 오름차순으로 정렬하고, r이 동일한 경우 c(열)를 기준으로 오름차순 정렬하여 인덱스 [0]에 있는 물고기를 먹으면 가장 상단이면서 왼쪽에 있는 물고기를 먹을 수 있게 된다. - 아기 상어의 데이터 관리는?전역변수로 관리하면 편하다. int shark_r, shark_c, shark_size, eat_num.. [BOJ] 백준 1726. 로봇 ▶문제설명[BOJ] 백준 1726. 로봇 https://www.acmicpc.net/problem/1726 ▶Hint BFS 문제이다. BFS 수행 시 모든 방향에 대해서 방문 체크를 해야한다는 점이 핵심이다. - 어떻게 해당 위치에서 모든 방향에 대해 방문 체크를 수행하나?visited[R][C][0 ~ 4] : 좌표 R,C에 방향 0, 1, 2, 3으로 방문했는지의 여부 체크 [Queue에서 꺼낸 뒤 수행해야 하는 일]1. 현재 위치와 현재 방향이 도착지점인 경우 answer 값을 현재 카운트 값으로 업데이트 2. 현재 카운트 값이 answer보다 같거나 큰 경우는 더이상 볼 필요 없으므로 무시(continue) 3. 현재 위치에서 현재 방향으로 1칸/2칸/3칸 전진하는 경우에 대해 카운트를 1 증가.. [BOJ] 백준 17140. 이차원 배열과 연산 ▶문제설명[BOJ] 백준 17140. 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 ▶Hint 시뮬레이션 문제이다. - R 연산과 C 연산1. A배열의 해당 행이나 열에 존재하는 숫자의 개수를 센다. 2. 등장한 숫자와 그 숫자의 등장 횟수를 구조체로 저장하여 벡터에 push_back한다.push_back과 동시에 A배열의 해당 위치의 값을 0으로 바꿔주어야 원하는 결과를 얻을 수 있음 3. 문제의 조건에 맞게 구조체를 정렬한다.등장 횟수가 큰 순으로 정렬하되, 등장 횟수가 같은 경우 해당 숫자의 크기가 큰 순으로 정렬함 4. 정렬된 구조체를 A배열에 순차적으로 저장한다. 5. 연산 수행시 행이나 열의 크기가 다를 수 있는데, 가장 큰 index를 구해 행과 열의.. [BOJ] 백준 17142. 연구소 3 ▶문제설명[BOJ] 백준 17142. 연구소 3 https://www.acmicpc.net/problem/17142 ▶Hint 브루트 포스 & BFS & 시뮬레이션 문제이다. M개의 바이러스를 활성화 시켜서 활성/비활성 바이러스로 가득 채우기 위해 걸리는 최소 시간을 구하는 문제다. 모든 바이러스가 활성화 되어 있지 않아도 괜찮다는 조건이 문제를 까다롭게 만드는 것 같다. 가능한 모든 경우에 대해 시뮬레이션 해야 하므로, 기존의 map을 복사하여 활용한다. 벽은 -1, 바이러스는 -2, 빈 곳은 -3으로 표시하는 것이 핵심이다. - 입력으로 주어진 바이러스들 중 M개를 선택하는 모든 경우는 어떻게 구할 것인가?next_permutation()을 활용하면 쉽게 해결할 수 있다. - 활성/비활성 바이러스로 .. [BOJ] 백준 17144. 미세먼지 안녕! ▶문제설명[BOJ] 백준 17144. 미세먼지 안녕! https://www.acmicpc.net/problem/17144 ▶Hint시뮬레이션 문제이다. 1. vector에 모든 미세먼지에 대한 정보를 저장하고, 공기 청정기의 위치 정보를 저장한다. 2. 모든 미세먼지를 확산시킨다. 3. 공기청정기 상단은 반시계 방향, 하단은 시계 방향으로 공기를 한 칸씩 필터링한다.공기 청정기 상단은 방향을 상/우/하/좌로 바꾸면서 미세먼지를 순회하며 한 칸씩 당겨주었고 공기 청정기 하단은 방향을 하/우/상/좌로 바꾸면서 미세먼지를 순회하며 한 칸씩 당겨주었다. 4. 2~3을 T번 반복한다. 5. 모든 미세먼지의 양을 답으로 출력한다. ▶Solution [BOJ] 백준 1018. 체스판 다시 칠하기 ▶문제설명[BOJ] 백준 1018. 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 ▶Hint브루트 포스 문제이다. 1. 2차원 배열로 W로 시작하는 8x8 체스판과 B로 시작하는 8x8 체스판을 미리 만든다. 2. 입력으로 주어진 판을 8x8로 자르는 모든 경우에 대해서 다시 칠해야 하는 격자의 개수를 구한다. (이미 만들어 둔 체스판과 비교했을 때 색깔이 다른 격자의 개수가 다시 칠해야 하는 격자의 개수임) 3. 가장 작은 경우를 답으로 출력한다. ▶Solution 이전 1 2 3 4 5 6 다음