전체 글

문제 https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 문제에서 명시한대로 스텝을 밞아나가면서 구현하면 풀 수 있다. (단순하지 않아서 그렇지..) 우선 나는 입력값을 배열에 저장해뒀다. 그리고 해당 위치에 특정 방향으로 바라보는 물고기가 몇개 있는지 저장해뒀다. 처음에는 물고기를 하나하나당 요소로 저장해뒀는데 이게 시간초과의 주범이었다. 그래서 [1,1] 위치에 1의 방향으로 바라보는 물고기가 몇 개 있는..

문제 https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 문제의 기능들을 본격적으로 구현하기전에, 회오리 방향으로 2차원 배열에 쉽게 접근하는 방식을 구현하고 싶었다. (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) 무슨 말이냐면, 위와같이 3*3 배열이 있을때 0이라는 키는 (1,1) 좌표를 뱉고, 1은 (1,0), 2는 (2,0) 이라는 좌표를 뱉는 딕셔너리를 구현하고 싶었..

문제 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 시뮬레이션 + 탐색 문제다. 탐색 같은 경우에는 bfs나 dfs방식으로 발판의 숫자로 체킹하면 된다. 조금 헷갈리는건 주사위를 굴리는 시뮬레이션인데, 나 같은 경우에는 우선 주사위를 임의로 배열로 선언했다. 각 위치는 내가 임의로 선정했고, 그에 따라 동서남북 회전되었을때 배열을 갱신해주는 방식으로 풀이했다. 그 외에는 조건에 따라 시계방향, 반시계방향, 반대방향으로 ..

문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 은근 까다로운 문제이다. 일반적인 bfs에 조건을 잘 걸어서 문제를 풀어야한다. 우선 나는 입력값을 조금 조정했다. 1부터 N까지가 아니라, 0부터 N-1로 설정했고, 벽은 1이 아니라 -1로, 빈칸은 0이 아니라 -9로 설정했다. 이유는 입력받은 2차원 배열에 손님들의 위치를 저장해두기 위해서이다. 해당 위치는 bfs를 돌면서 판단할 때 사용한다..

문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 풀이 python3으로는 시간초과가 나서 pypy3으로 제출했다. 우선 구름의 위치를 저장하는 배열을 선언하고, 각 구름의 이동을 수행한다. 배열의 범위를 초과하면 순환되는 구조이기에 그 부분부터 구현하면 된다. '마법사 상어와 파이어볼' 에서 처리한것과 똑같이 처리해주면 된다. (아래 참고) 파이어 볼 이동 2차원 배열을 돌면서 한개라도 파이어볼이 있다면 현재위치 + 방향 * 속도 ..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 요구사항과 조건이 굉장히 많은 구현 문제다. 풀이를 하다보면 놓치는 부분이 많을것이라고 생각하여서 우선 요구사항을 내가 이해하기 편하도록 작성했고, 그에 따른 슈도코드나 솔루션도 생각나는대로 작성했다. 해당 문제의 큰 흐름을 확인해보자. 존재하는 블록그룹을 확인한다. 우선 탐색은 bfs로 가정한다. 블록그룹은 우선 무지개블록, 검은블록이 아닌 일반블록이 하나는 있어야한다. 또한 기준..

문제 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할 수 있도록 구성했..