Algorithm
-
[BOJ] 3917번 백조의 호수 (C++)Algorithm 2021. 12. 24. 15:43
3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net - 1차 접근 자료구조랑 그래프 탐색만 잘하면 풀릴 것 같다는 생각으로 접근해 아래의 로직을 구현했다. 1. 백조가 만날 때까지 아래 과정을 반복한다. 1-1. 백조가 만나는지 확인하고 만난다면 반복문을 종료한다. (bfs 활용) 1-2. 물에 닿아 있는 얼음을 물로 바꾼다. (set 활용) 1-3. day를 1만큼 증가시킨다. 이 때, 다음 얼음을 녹일 가능성이 존재하는 물의 좌표를..
-
[BOJ] 1082번 방 번호 (C++)Algorithm 2021. 12. 21. 15:48
1082번: 방 번호 (acmicpc.net) 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net - 1차 접근 다이나믹 프로그래밍 문제처럼 생겨먹어서 바텀-업으로 점화식을 도출해내기 위해 1차원 배열을 사용하고 보유한 돈(M)을 인덱스로 관리하는 식으로 접근했다. 다음은 도출해낸 점화식이다. dp[i] = max(dp[i], for max("n" + dp[i-cost[n]])) ('for max'는 숫자 가격 배열 중 가장 큰 가격 배열을 찾는 것을 의미한다.) 여기에 추가적으로, 한자리 수가 아닐 때 앞자리에 0이..
-
[BOJ] 2866번 문자열 잘라내기 (C++)Algorithm 2021. 12. 14. 01:15
2866번: 문자열 잘라내기 (acmicpc.net) 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net - 1차 접근 가장 처음 떠올린 방법은 명세를 그대로 따라 구현을 하는 것이였다. 1. 현재 제거될 행을 제거한다. 2. 행을 제거한 테이블에 중복이 있다면 종료하고 정답을 출력한다. 안될 것 같다는 약간의 의심과 함께 위 로직을 구현해보면 시간초과가 발생한다. 최악의 경우 O(R*C)의 복잡도를 가진다. - 2차 접근 다음 떠올린 방법은 이분탐색을 활용하는 것이다. 이분탐색을 활용하면 로직..
-
[BOJ] 14500번 테트로미노 (C++)Algorithm 2021. 9. 13. 00:33
14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net - 접근 첫 접근에서는 브루트포스말고 다른 방법으로 풀 수 있을까 고민을 했지만 없을 것 같다는 결론을 냈다. 모든 테트로미노의 좌상단 블록을 시작점으로 잡고 인덱스 변경값을 배열에 넣어 관리했다. 이후, 범위 초과와 대칭 및 회전 케이스를 고려하여 탐색을 하도록 구현했다. - 풀이 신경쓸 부분은 위에서 언급한 2가지 (1) 범위초과, (2) 대칭 및 회전 케이스이다. 1. 범위초과 다른 맵 탐색 문제에서 사용한 ..