전체 글

문제 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차원 배열을 돌면서 상어가 존재하는 위치라면 저장해놓은 방향을 통해 한칸씩 이동한다. 만약 벽..

문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 해당문제의 핵심요소는 1. 배열의 크기를 어떻게 늘리느냐 배열의 크기 같은경우에는 늘리지말고, 최대치를 선언한다음에 바운더리를 정해주는 식으로 해결하면 된다. 초기값은 3, 3이고, 연산에 따라 행이나 열의 사이즈를 늘리면 된다. 2. 정렬을 어떻게 할 것인가 정렬 같은경우에는 우선 최소힙을 사용해서 수와, 수가 카운트 된 횟수를 체크한다. ex> [2, 2, 1, 4] 면..