알고리즘 💻

[BOJ, Python] 소문난 칠공주

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 1. 먼저 25명(5X5) 중에 7명을 뽑는 경우를 구합니다. 조합(순서는 신경쓰지 않음) 으로 for문을 25만큼 돌면서 visited[i // 5][i % 5]를 방문체크해서 모든 조합을 구합니다. 2. 구한 조합이, 서로 가로세로로 붙어있는지 체크하기 위해 bfs를 돌립니다. bfs로 4방 탐색을 하면서, 방문한 적 있으면 조합에 속하는 학생이라는 의미이므로 솜파이면 som +=1, 도연파이면 doyeon += 1을 진행합니다. 3. bfs를 끝내고 솜파..

[SWEA, Python] 백만 장자 프로젝트

정답 코드 t = int(input()) for tc in range(1, t+1): ans = 0 n = int(input()) price = list(map(int, input().split())); while len(price) != 0: max_idx = price.index(max(price)) cal = price[:max_idx] for i in range(len(cal)): ans += abs(price[max_idx] - price[i]) price = price[max_idx+1:] print(f'#{tc}', ans) 풀이 과정 1. dfs 재귀로 시도 -> 실패(시간초과) def dfs(idx, benefit, cost): global n, price, ans if idx == n:..

[프로그래머스, Python] 두 원 사이의 정수 쌍

정답 코드 import math def solution(r1, r2): num = 0 for x in range(1, r2+1): y_max = math.floor(math.sqrt(r2**2 - x**2)) y_min = 0 if x >= r1 else math.ceil(math.sqrt(abs(r1**2 - x**2))) num += y_max - y_min + 1 return num * 4 풀이 먼저, 문제에서 제시해 준 그림을 보면, 작은 원(r1)이나 큰 원(r2)사이의 정수를 모두 구하는 문제라는 것을 쉽게 알 수 있습니다. 이때, 모든 정수 쌍을 구하는 것이 아닌, 같은 패턴의 반복이므로 하나의 사분면의 정수 쌍을 모두 구한 뒤 *4를 해주면 답을 더 쉽게 구할 수 있습니다. 저는 1사분면을..

[프로그래머스, Python] 등굣길

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 학교(m,n)에서 집(0,0)으로 가는 방법 def dfs(x, y, dp): if x < 0 or y < 0 or dp[y][x] == -1: return 0 if dp[y][x] == 0: dp[y][x] = dfs(x - 1, y, dp) + dfs(x, y - 1, dp) return dp[y][x] def solution(m, n, puddles): dp = [[0 for _ in range(m)] for _ in range(n)] for p in puddles: x, y = p dp[y-1][..

[프로그래머스, Python] 광물 캐기

정답 코드 def solution(picks, minerals): ans = [] tired = [[1, 1, 1], [5, 1, 1], [25, 5, 1]] tools = {"diamond" : 1, "iron": 2, "stone": 3} def dfs(minerals, picks, tired_rate): # 종료 조건 if sum(picks) == 0 or minerals == []: ans.append(tired_rate) return m = minerals[:5] # tool 을 picks에서 감소 for t in range(3): if picks[t] > 0: picks[t] -= 1 tired_rate_val = tired_rate_calculate(t, m) dfs(minerals[5:],..

[프로그래머스, Python] 게임 맵 최단거리

문제를 보자마자 전형적인 BFS 문제라고 생각했습니다. 특이할 것 없이 queue를 이용한 graph bfs문제를 풀 면 됩니다. 오타때문에 런타임 에러가 났었는데 n이랑 m 잘 확인하시길... from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x,y,n,m, maps): q = deque([(x,y)]) while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

[프로그래머스, Python] 수식 최대화

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저, permutation을 이용하여 가능한 모든 연산자의 우선순위 배열을 구합니다. operators = list(permutations(['-', '*', '+'])) #[('-', '*', '+'), ('-', '+', '*'), ('*', '-', '+'), ('*', '+', '-'), ('+', '-', '*'), ('+', '*', '-')] 모든 연산자 우선순위 배열을 순회하면서, 각 배열의 연산자들과 숫자를 연산합니다. 이때, while문으로 연산자 우선순위가 우선인 연산자들이 전부 연산 된..

[Python] 2차원 배열 돌리기

2차원 배열 돌리기는 직접 구현하거나, zip을 이용하여 간편하게 바꾸는 2가지 방법이 있습니다. 1. 직접 구현하기 [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 와 같은 배열을 한 번 돌리면, [[7, 4, 1], [8, 5, 2], [9, 6, 3]] 와 같은 결과를 얻을 수 있습니다. 180, 270도 회전을 원하면 rotate 함수를 여러 번 호출하면 됩니다. def rotate(graph): n = len(graph) m = len(graph[0]) result = [[0]* n for _ in range(m)] for i in range(n): for j in range(m): result[i][j] = graph[n-1-j][i] return result # [[7, 4, 1..