문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 구현 + 완전탐색 문제다. 처음에는 greedy로 시도해봤으나, 맞지않았고 완탐이 맞았다. 재귀로 구현했는데, 스케일이 굉장히 큰 재귀라.. 굉장히 까다로웠다. 흐름자체는 간단하다. 물고기 작은 순서대로 swap 실행 나는 dictionary를 활용하여 [물고기번호] = [좌표] 식으로 저장했고, 번호순으로 오름차순 정렬하여 작은 물고기부터 swap할 수 있도록 구성했..

문제 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 구현구현구현 문제다. 요구사항대로 구현하면 되긴하는데, 조건이 많고 섬세하게 구현해야해서 까다롭다. 나는 총 5개의 저장소를 활용했다. (1) 상어의 위치를 저장하는 2차원 배열 (2) 상어의 현재방향을 저장하는 1차원 배열 (3) 상어의 존재유무를 확인하는 set (4) 상어의 냄새를 저장하는 2차원 배열 (5) 각 상어마다 우선순위 리스트..

문제 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 풀이 해당문제는 총 3개의 큰 로직으로 나눠서 구현할 수 있다. (설명은 파란 보드를 기준으로 모두 한다.) 이동 로직 for문으로 보드를 순회하면서 블록을 설치할 수 있는지 없는지 판단한다. 특정 위치에 블록이 있다면, 그 전 위치에 블록을 위치해주면 된다. 만약 끝까지 갔는데도 없으면, 마지막 위치에 블록을 위치한다. 줄을 지우고, 앞선 줄을 당기는 로직 블록이 최종위치에 안착..

문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제 지문이 워낙 이해하기 힘들었다. 심지어 이해를 잘못한 상태로 코드를 짜다가, 영 이상한 거 같아서 질문게시판에서 지문에 대한 설명을 조금 도움 받은 후 풀이했다. pypy3으로 통과했다. 난 총3개의 저장소를 사용해서 풀이했다. (deque) location[i] = i번째 위치에 존재하는 발판 location의 i는 위치적인 면을 나타낸다. 컨베이어는 계속 ..

문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 문제를 정말 잘 읽고, 하나하나 놓치지않고 구현하면 되는 문제다. 고려할점 몇가지, 데이터를 deque vs list 어디에 저장? 덱을 사용하면 rotate 함수가 있기에 회전은 쉽게 할 수 있다. 대신 덱은 접근연산이 O(n)이다. 반대로 리스트는 접근시간이 1인 대신, 회전할 경우 시간이 덱에 비해 훨씬 걸린다. 그러나 내가 생각한 풀이는 회전횟수보다는 인덱스에 접..

문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 우선 입력값을 1차원 배열에 저장하고, 학생번호로도 접근할 수 있도록 딕셔너리에도 세팅해둔다. 그 다음은 2차원 배열을 모두 돌면서 어느자리가 적합한지를 판단해야한다. 선호하는 친구의 수, 빈칸의 공간을 매 칸마다 확인하며, 이전에 저장한 최댓값보다 크다면 갱신해주고 아니라면 넘어가면 되는 식으로 구현하면 된다. 단, 귀찮은 부분이 있는데 친구도, 빈칸도 같을때이다. 이 때는..

문제 https://www.acmicpc.net/source/62767025 로그인 www.acmicpc.net 풀이 해당 문제는 자기 위에 올라가있는 친구들을 어떻게 잘 관리하는지가 핵심인데, 덱을 사용하면 손쉽게 관리할 수 있다. 예로 다음칸이 흰색이고 순서가 3일 경우를 보자. (배열 왼쪽이 낮은 위치) [2, 3, 1, 4] , [5, 6] 이라고 할 경우 [5, 6, 3, 1, 4] 가 되어야한다. 이 과정은 덱을 활용해서 [2, 3, 1, 4] 에서 뒤에서부터 4, 1, 3 을 순서대로 pop하고, 임시 덱에 pop한 값을 왼쪽부터 넣으며 [3, 1, 4] 로 만들 수 있다. 빨간 칸은 더 쉽다. [2, 3, 1, 4], [5, 6] => [5, 6, 4, 1, 3] 를 만들어야하는데 중간에 ..

문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 풀이 구현.. 그냥 싹 다 구현인 문제다. 나처럼 풀이하는게 맞는 방법인지는 모르겠으나, 섬세하게 코드 짜지않으면 바로 틀려버리는 문제.. 문제 같은 경우에는 d1과 d2이 가질 수 있는 모든 경우의 수와, 기준점이 될 수 있는 점의 좌표를 넣어 하나씩 모두 계산해본다음 최솟값을 찾는 방식으로 접근했다. 초반에 탐색 시간을 조금이라도 더 줄여볼려고, 짜잘한 테크닉을 썼다. 조건과 예시 사진의 형..

문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 조합과 bfs로 풀이할 수 있는 문제다. 1. 우선 바이러스 있는 위치의 조합을 모두 구한다. 2. 조합을 돌면서 bfs를 수행한다. 3. 최솟값을 구한다. 대략적인 풀이는 이러한데 중요한 부분이 있다. 목표가 모든 칸의 바이러스 점령이므로, 비활성 바이러스를 꼭 활성화 해줄 필요는 없다. '비활성 바이러스' 그 자체도 바이러스기 때문에 정확한 목표는 주어진 입력값에서 0 부분이 모두 바이러스..

문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 전형적인 시뮬레이션, 구현 문제 2차원 배열을 선언해주고 상어가 있는 위치에 [크기, 방향, 시간] 을 저장했다. 1차적으로 낚시왕의 열에서 행이 가장 작은 상어를 먹는다. 그리고 상어가 이동한다. 이 때 결과값을 저장할 빈 2차원 배열을 선언해둔다. 기존의 상어가 저장된 2차원 배열을 돌면서 상어가 존재하는 위치라면 저장해놓은 방향을 통해 한칸씩 이동한다. 만약 벽..