투투

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 접근 다음 칸으로 이동했을 때 해당 칸의 모래의 양은 없어지고 미리 정해진 위치로 비율만큼 흩어지게 된다. 그리고 방향에 따라 특정 위치의 비율도 달라진다. 따라서 미리 방향에 따라 특정 위치로 이동했을 때의 비율을 저장해둔 후에 사용하도록 하였다. 아래와 같이 현재 위치와 방향을 기준으로 흩어지는 모래의 비율을 저장하였다. 행의 번호는 현재 방향을 가리키고 있는 ..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 접근 4개의 말로 10개의 턴이 진행된다. 주사위에 나오는 숫자는 미리 알고있다. 그렇다면 매 턴마다 어떤 말을 이동할지 선택해야 한다. 이를 비트시프트를 활용하여 모든 경우의 수를 구하여 말을 선택한다. 0부터 1

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 접근 사이클이 완성되기 위해서는 최소 세 개의 점이 연결되어야 한다. 이를 유니온 파인드 알고리즘을 활용하여 해결할 수 있다. 입력되는 두 개의 점이 있을 때 한 쪽 점을 다른 쪽에 속한 집합으로 합친다. 이후에 두 개의 점을 입력받았을 때 루트 노드가 같다면 사이클이 완성되었다고 판단할 수 있다. 구현 - 아래와 같이 union와 find 연산을 함수로 만든다. def find(a): if..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 접근 이번 문제에는 상어들의 step 크기가 최대 1000이다. 따라서 최대 RxC 마리의 상어들의 모두 1000의 크기만큼 이동할 때 한 칸씩 이동하도록 구현하면 시간초과가 발생한다. 따라서 상어들의 step 크기를 줄여야했다. 이를 위해 규칙을 찾아보면 상하로 움직이는 상어들은 (R-1) x 2배, 좌우로 움직이는 상어들은 (C - 1) x 2배일 때 같은 자리로 돌아오게 ..

접근 사각형을 그리기위해 시작 위치를 기준으로 (1, -1), (1, 1), (-1, 1), (-1, -1)로 순서대로 이동하도록 구현하였다. DFS로 탐색을 진행하고 범위를 벗어나거나 이미 방문한 카페라면 return을 하고 그렇지 않을 때는 현재 방향을 그대로 이동하거나 방향을 증가시켜 이동한다. 방향을 증가시켜 이동할 때는 (-1, 1)로 이동하다가 (1, 1) 방향에 목적지가 있을 때 방향을 바꾼다. 또한 (1, -1)이거나 (1, 1)일 때는 현재 방향으로도 이동하고 다음 방향으로도 이동할 수 있도록 재귀호출한다. 구현 - 주어진 입력을 모두 받은 후에 - board를 탐색하면서 각 위치에서 dfs를 진행한다. N = int(input()) board = [list(map(int, input()..

https://programmers.co.kr/learn/courses/30/lessons/12949 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 접근 행렬을 곱하기 위해서는 행렬 A와 B가 있을 때 행렬 A의 열 개수와 행렬 B의 행 개수가 같아야 한다. 그리고 행렬의 곱을 그대로 코드로 구현하였다. 구현 - arr2의 행과 열의 개수를 N과 M에 저장했다. - 이제 arr1에서 하나의 리스트를 꺼낸다. - arr2를 탐색하면서 arr1에서 꺼낸 리스트의 숫자들을 행렬 곱을 해주고 이를 ..

https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 접근 이런 문제를 규칙을 잘 찾아야할 필요가 있다. 규칙은 다음과 같다. 짝수일 때는 맨 뒤에 있는 0을 1로 변경한다. 홀수일 때는 맨 뒤에 있는 0을 1로 변경하고 그 다음을 0으로 변경한다. 이를 통해 해를 구할 수 있다. 구현 - 7을 bin으로 변경하면 0b111이 되어 0을 찾을 수 없다. 따라서 이러한 경우를 대비하여 미리 앞에 0을 추가한다. - 이어서 문자열로 변경하고 rfind()를 사용하여 '0'의 위치를 idx에 넣는다. - 이후 number가 홀수일 때는 idx+1을 0으로 변경한다. - 위의 과정이 모두 ..

https://programmers.co.kr/learn/courses/30/lessons/17684?language=python3 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 접근 딕셔너리에 A ~ Z 까지를 Key로 각각 1 ~ 26까지의 Value를 짝지어서 저장하여 활용한다. msg를 탐색하면서 각각의 문자를 연결해 새로운 문자를 만들어내고 해당 문자가 딕셔너리에 존재하면 다음 문자도 이어붙인다. 하지만 딕셔너리에 존재하지 않는다면 현재 문자 중에 마지막 문자를 제외한 것을 딕셔너리에 찾아 해당 값을 answer에 저장하..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 접근 이번 문제에서는 특정 범위를 90도로 회전시키는 것을 구현하는 것이 가장 큰 문제였다. 먼저 board라는 원본 맵을 탐색하면서 입력받은 범위만큼 나누고 90도로 회전시키는 함수에 회전한 board를 다른 2차원 리스트에 저장하였다. 일단 1이 들어왔다고 가정하고 몇몇 범위를 예시로 어떻게 인덱스가 변하는지 파악하였다. 예를 들어 (0, 0)을 시작으로 2x2크기는 (0,..

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 접근 쿼드 트리를 구현해보았다. 만약 행과 열의 개수가 같은 2차원 리스트에서 행의 개수가 4라고 가정해보자. (0, 0)부터 시작해서 4x4를 모두 탐색했을 때 같은 숫자로..