본문 바로가기

취업과 기본기 튼튼

 (76)
[BOJ] 17135. 캐슬 디펜스 문제 캐슬 디펜스 (https://www.acmicpc.net/problem/17135) 풀이 1. 초기접근 문제조건 해석 판이 주어지고, 각 턴에 따라 판의 형태가 달라진다. 문제에서 이야기 했 듯, 궁수의 위치가 중요하다. 궁수의 위치에 따라, 진행되는 판의 모양이 달라진다. N, M BFS다. 가장 왼쪽에 있는 -> 방향 순서를 고려해줘야 한다. 같은 적이 여러 궁수에게 공격당할 수 있다는 말은, 각 궁수가 없애고자하는 좌표가 겹칠 수 있다는 말이다. 없앨 좌표를 일괄적을 처리해야 한다. 알고리즘 먼저, 각 궁수가 위치할 수 있는 모든 경우를 구한다음, 각 경우를 탐색한다. itertools.combination 을 이용하면 된다. 각 경우에서, 3명의 궁수가 이번 스텝에 없앨 적의 좌표(targe..
[BOJ] 14891. 톱니바퀴 문제 톱니바퀴 (https://www.acmicpc.net/problem/14891) 풀이 1. 초기 접근 문제조건 해석 각 스텝에 따라, 기존 자료구조의 값이 바뀌는데, 바뀌는게 연쇄적이다. 시뮬레이션 + DFS 문제다. 알고리즘 문제 조건에서, 많은걸 알려주는데, 일단 톱니바퀴를 리스트로 표현할 수 있음을 알 수 있다. 그리고 톱니바퀴의 회전은 리스트 요소들을 왼쪽 혹은 오른쪽으로 시프트하는 것임을 알 수 있다. deque 의 .rotate() 가 있다! 회전 조건은, 정해진 인덱스를 비교하면 된다. 코드 from collections import deque from sys import setrecursionlimit setrecursionlimit(10**8) def dfs(no, di, visit..
[BOJ] 12100. 2048 (Easy) 문제 2048 (Easy) (https://www.acmicpc.net/problem/2048) 풀이 1. 초기 접근 문제조건 해석 판이 주어지고, 각 스텝마다 판 전체의 값이 달라진다. 움직이는 방향은 4가지 이므로, 바뀌는 판도 4가지 경우가 생긴다. 특정 스텝에서 멈추고, 가장 큰 값을 반환해야 한다. BFS 문제다. 알고리즘 전체적인 BFS 문제, 바뀌는 것은 전체 판이니, BFS queue 에 전체 판을 넣어주면 된다. 한 번에 4가지 경우의 판이 생기고, 총 5번까지 해야하니, 최대 경우의 수는 4^5 = 1024개다. 각 방향에 대하여 움직이는게 좀 까다로운데, 이를 별도의 함수 move(board, di) 로 두자. 먼저 이전의 판 board 와 움직이는 방향 di 를 넘겨받아, 움직임이 ..
[BOJ] 14499. 주사위 굴리기 문제 주사위 굴리기 (https://www.acmicpc.net/problem/14499) 풀이 1. 초기 접근 문제조건 해석 역시 삼성 문제는 뭔가 글이 많다. 세세하게 잘 읽어야한다. 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자. 삼성 문제의 대표적인 시뮬레이션 문제다. 문제에서 주어진 대로 그냥 짜기만 하면 된다. 핵심은, 과연 올바른 자료구조로 잘 구현할 수 있는가? 다. 알고리즘 주사위의 각 면을 어떻게 변화시키고 어떻게 각 면에 접근해야할까? 라는 생각이 가장 먼저든다. 먼저 제일 중요해보이는 건, 윗 면과 아랫 면이다. 우리는 이 면에 지속적으로 접근하게 된다. 윗 면과 아랫 면을 고정 인덱스로 두고 접근해야, 덜 복잡할 듯하다. 주사위의 각 면을 고정 인덱스로 두자는 발상이 나오게 ..
[BOJ] 14501. 퇴사 문제 퇴사 (https://www.acmicpc.net/problem/14501) 풀이 1. 초기 접근 문제조건 해석 이 문제, 뭔가 어렵지 않아보이긴 하다. 목표 상태(n 번째 일)가 있고, 상태에 도달하는 경로들을 탐색해나가야 한다. 각 경로에 따라, 최종 상태의 값이 달라진다. n도 매우 작다. DFS 로 풀 수 있다. 한편, 점화식을 잘 세우면 DP로도 풀 수 있을 듯 하다. 알고리즘 DFS로 풀면, 다음과 같다. 오늘이 i 일이라고 하자. 경우는 2가지다. 오늘 일할 경우와 일 안할 경우다. 일 하면 i + t[i] 일에 또 위 선택을 해야한다. 일 안하면 그냥 다음 날 i+1 일에 위 선택을 하면 다시 하면 된다. 많아봐야 15일 까지니, 시간 복잡도는 O(2^15) 이다. 코드 def dfs..
[BOJ] 16234. 인구 이동 문제 인구 이동 (https://www.acmicpc.net/problem/16234) 풀이 1. 초기 접근 문제조건 해석 역시 삼성 문제는 뭔가 글이 또 많다. 세세하게 잘 읽어야한다. 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자. 삼성 문제의 대표적인 DFS, BFS 문제다. 인접한 칸으로 탐색해야 하고, 특정 조건 (인접한 칸의 값이 L 이상 R 이하) 인 경우, 더 파고들어 계속 탐색해야 한다. 여기서는 BFS 로 풀어보겠다. 알고리즘 먼저, 현재 상태에서 문제에서 말하는 연합(union) 인 좌표들을 먼저 다 찾아내야 한다. 이 과정에서 BFS를 쓴다. 연합인 좌표들은 자연스레 visited 에 들어가게 된다. BFS로 탐색하며, 연합인 좌표들의 값을 모두 더하고(total), 그 갯수(..
[BOJ] 16235. 나무 재테크 문제 나무 재테크 (https://www.acmicpc.net/problem/16235) 풀이 1. 초기 접근 문제조건 해석 역시 삼성 문제는 뭔가 글이 많다. 세세하게 잘 읽어야한다. 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자. 삼성 문제의 대표적인 시뮬레이션 문제다. 문제에서 주어진 대로 그냥 짜기만 하면 된다. 핵심은, 과연 올바른 자료구조로 잘 구현할 수 있는가? 다. 알고리즘 정말 문제에 나온대로 하나씩 코딩하면 된다. 핵심은, 나이가 어린 나무들부터 양분을 섭취해야하는데, 이를 위해 deque 를 썼다. 자세한 건 코드 주석 참조. 코드 from collections import deque dxs = [-1, -1, 0, 1, 1, 1, 0, -1] dys = [0, 1, 1, 1, ..
[BOJ] 16236. 아기 상어 문제 아기 상어 (https://www.acmicpc.net/problem/16236) 풀이 1. 초기 접근 문제조건 해석 일단 문제조건이 뭔가 되게 복잡해서, 잘 읽어야한다. 삼성 문제 특징이다. 이동할 수 있는 각 경우는 상하좌우 4가지 방향이 있고, 한 번에 1칸 이동할 수 있다. 우리는 최종 이동까지의 시간을 구해야 한다. BFS 문제다. 알고리즘 일단 진짜로 문제를 잘 하나하나 읽고, 예제로 주어진 케이스들을 손으로 풀면서, 내가 잘 이해했는지 확인해보자. 그럼 다음과 같이 차례대로 생각해볼 수 있다. 먼저 자기보다 크기가 작은 물고기들을 찾는다. 그 중, 가장 가까운 애들부터 먹으러 가서 먹는다. 지금까지 먹은 횟수가 현재 내 크기만큼 되는지 체크한다. 만약 내 크기만큼 된다면, 내 크기를 한..

티스토리툴바