whiporithm

문제 https://www.acmicpc.net/submit/20058/63063274 로그인 www.acmicpc.net 풀이 해당 문제는 각 격자를 l의 값에 따라 잘 나누고, 접근해서 로직만 잘 수행하면 풀 수 있는 문제이다. 그 외에 배열 회전, 얼음 감소, 가장 큰 대륙 찾기등 부가적인 요소는 간단하게 해결할 수 있다. 예시를 보자. n이 8, l이 1일때는 64 / 4 => 16개의 격자가 생긴다. n이 8, l이 2일때는 64 / 16 => 4개의 격자가 생긴다. 이 값은 (2^n)^2 / (l^2)^2 라는 공식으로 얻을 수 있다. 이후에는 각 격자에 접근한다음에, 배열을 회전해줘야한다. 위와 같이 4군데에 접근해야하고 각 격자에 해당하는 부분만 탐색해야한다. 처음에 x, y는 0으로 시작..

문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 꽤나 무식하게 풀이했다. 토네이도가 회전하는 방식 구현 단순하게 사진보고 유추했다. 1의 길이가 2번 반복, 2의 길이가 반복.. 그러다 n-1의 길이는 3번 반복되더라. 반복되면서 방향은 계속 바뀌고.. 보이는 대로 구현했다. 밑의 사진을 보면 이해가 좀 더 쉽다. 회전된 비율 배열 4방향이니까, 그냥 회전해서 좌표를 다 구하는 방식으로 했다. 사실 좀..

문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 각 칸에 파이어볼을 정보를 담고있는 리스트를 요소로 가지는 2차원 배열을 선언한다. [[ [m1, s1, d1], [m2, s2, d2] ..] ] , [ [m3, s3, d3] ] , .... ] [[ [m4, s4, d4] ], .... 와 같은 형태로 칸에 접근해서 반복문을 돌림으로써 모든 파이어볼의 정보를 알 수 있는 구조로 말이다. 이후에..

문제 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] 를 만들어야하는데 중간에 ..