본문 바로가기

■ 알고리즘 문제 풀이

 (74)
[BOJ] 백준 1654. 랜선 자르기 ▶문제설명[BOJ] 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 ▶Hint 이분탐색 문제이다. 이분 탐색 문제는 일반적으로 값의 범위는 넓지만 특정 값을 미리 정해놓고 시뮬레이션 해보는 것이 가능한 문제에 적용이 가능하다. ( 1
[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 증가..
[SWEA] 5658. 보물상자 비밀번호 ▶문제설명[SWEA] 5658. 보물상자 비밀번호 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE ▶Hint 브루트포스 & 시뮬레이션 문제이다. 사각형의 각 변에 적힌 16진수들을 시계방향으로 회전시키기 위해서 Queue 자료구조를 사용하는 것이 적합하다. 하지만 Queue는 저장된 데이터에 인덱스로 접근하는 것이 불가능하다. 그래서 Deque 자료구조를 활용한다. 1. 16진수들을 Deque에 모두 push_back한다. 2. 4개의 변에 있는 16진수를 각각 10진수로 변환하여 list에 저장한다.[변..
[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()을 활용하면 쉽게 해결할 수 있다. - 활성/비활성 바이러스로 ..

티스토리툴바