알고리즘

[python] 프로그래머스 - 빛의 경로 사이클(월간 코드 챌린지 시즌3)

🤔문제 해결 💨 문제에서 시키는대로 그대로 풀었다. (구현) 💫 visited 라는 3차원 배열을 만든다. 제일 안쪽의 원소에는 'U','D','R','L' 이 들어갈 수 있는데 해당 위치(i, j) 에서 이동한 방향을 담고 있다. 싸이클이 다르면 절대로 이동경로가 하나라도 똑같은게 나올 수 없기 때문에. 이동할 때 UDRL 이 있는지 확인을 하고 이동한다. 💻소스 코드 def solution(grid): answer = [] N, M = len(grid), len(grid[0]) visited = [[set() for _ in range(M)] for _ in range(N)] # U, D, L, R for i in range(N): for j in range(M): for k in 'UDLR': cn..

[python] 프로그래머스 - n^2 배열 자르기(월간 코드 챌린지 시즌3)

🤔문제 해결 💨 규칙을 찾아내는 수학문제? 같은 느낌, 문제의 설명대로 풀면 10^7 이므로 시간초과 발생.... 좌표를 활용하여 문제풀이 💫 빈 배열에 숫자를 넣는 공식은 행(i), 열(j) 의 최대값 + 1 💫 ex) 0행 2열의 값은 3, 1행 0열의 값은 2 💫 그림(4 x 4 행렬)에서 left(7) 부터 right(14) 는 [1,3] 부터 [3,2] 💫 좌표를 구하는 방법은 left = [7//4, 7%4] = [1, 3] 💫 결국 풀이는 좌표를 구해서 그 지점의 숫자를 결과 배열에 넣어주면 된다. 💻소스 코드 def solution(n, left, right): answer = [] for i in range(left, right + 1): answer.append(max(i // n, i..

[python] 백준 - 20055. 컨베이어 벨트 위의 로봇

🤔문제 해결 회전은 deque 의 rotate 메소드 이용 내구도 리스트, 벨트 위의 로봇 리스트 주어진 지문대로 구현하면 된다. 시간초과 때문에 고생했던 문제 벨트의 맨 끝에 로봇이 오면 항상 내려줘야한다. 💻소스 코드 import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) belt = deque(map(int, input().split())) robots = deque([0]*N) cnt = 0 while True: cnt += 1 # 1. 벨트 회전 belt.rotate() robots.rotate() # 내리는 위치에 로봇이 있다면 내린다. robots[-1] = 0 # 2..

[python] 백준 - 1018. 체스판 다시 칠하기

🤔문제 해결 짝수칸((i + j) % 2 == 0)과 홀수칸을 구분하여 색의 개수를 구한다. 예를 들어 짝수칸에 흰색 30, 검은색 2 홀수간에 검은색 32, 흰색 0 이 있다면 짝수칸의 검은색 2 를 흰색으로 칠하면 완벽한 체스판이 만들어진다. 반대로 짝수칸 흰색 30 을 검은색으로, 홀수칸 검은색 32 를 흰색으로 만들어도 완벽한 체스판이 되지만 62 개를 칠해야 하므로 전자가 더 최소인 경우이다. 짝수칸의 흰색 + 홀수칸의 검은색, 짝수칸의 검은색 + 홀수칸의 흰색 중 최소인 값을 계속 갱신해준다. 💻소스 코드 import sys def paint(x, y): color = [ [0, 0], [0, 0] ] for i in range(x, x + 8): for j in range(y, y + 8):..

[python] 백준 - 2485. 가로수

🤔문제 해결 수학 - 유클리드호제법 GCD 나무들의 간격을 구한다. 간격들의 최대 공약수를 구한다. 간격을 최대공약수로 나누고 1을 빼주면 각각의 간격 사이에 심을 나무의 숫자가 나온다. 💻소스 코드 import sys def gcd_func(a, b): while b != 0: a, b = b, a % b return a input = sys.stdin.readline N = int(input()) trees = [int(input()) for _ in range(N)] gaps = [] for i in range(1, N): # 가로수의 간격 gaps.append(trees[i] - trees[i - 1]) gaps_set = list(set(gaps)) # 간격 중복 제거 gcd = gaps_set..

[python] 백준 - 21608. 상어 초등학교

🤔문제 해결 시뮬레이션 학생: *친구들 딕셔너리를 만든다. 문제의 크기가 크지 않기 때문에 이중 포문으로 교실 전체를 탐색 좋아하는 사람 옆자리와 빈자리 개수를 각각 체크해준다. 좋아하는 사람 옆자리 수 빈자리 수 순서로 체크해가며 큰 값을 업데이트 해준다. 인덱스가 작은 값부터 탐색하기 때문에 같다면 행번호, 열번호가 작은 자리가 선택되게 된다. 다 찾았으면 교실 전체를 돌며 만족도 조사 끝 💻소스 코드 import sys input = sys.stdin.readline def is_in(ix, iy, n): if 0 max_blank): # 1. 좋아하는 사람 옆자리, 2. 같으면 빈자리 max_blank = blank max_like = like loc = i, j x, y = loc classro..