Programming/Algorithm
-
[프로그래머스] 멀쩡한 사각형 (by Python)Programming/Algorithm 2021. 5. 16. 03:57
문제 https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 풀이 from math import gcd def solution(w,h): return w * h - (w + h - (gcd(w, h))) 코드는 한 줄만에 끝났지만 정말 고민을 많이 하게 만든 문제였다. 대각선상에 있는 사각형의 개수에 무슨 규칙이 있을지 발견하기가 쉽지 않았던 것 같다. 해답은 이러하다. w와 h의 최대공약..
-
[프로그래머스] 폰켓몬 (by Python)Programming/Algorithm 2021. 5. 16. 03:46
문제 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 풀이 def solution(nums): a = len(set(nums)) b = len(nums) // 2 return b if a > b else a 만약 폰켓몬의 종류가 가져갈 수 있는 폰켓몬의 수보다 적다면, 그 종류의 개수가 답이 될 것입니다. 그렇지 않다면, 가져갈 수 있는 폰켓몬의 수가 최댓값일 것입니다.
-
[프로그래머스] 음양 더하기 (by Python)Programming/Algorithm 2021. 5. 16. 03:39
문제 https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 풀이 def solution(absolutes, signs): return sum(absolutes[i] if signs[i] else -absolutes[i] for i in range(len(absolutes))) 두 리스드의 값에 따라 합을 계산하는 간단한 구현 문제. list comprehension을 이용하여 한 줄로 끝낼 ..
-
[프로그래머스] 더 맵게 (by Python)Programming/Algorithm 2021. 5. 16. 03:36
문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 풀이 import heapq def solution(scoville, K): count = 0 scoville.sort() while len(scoville) != 1: temp = heapq.heappop(scoville) + 2 * heapq.heappop(scoville) heapq.heappush(scoville, temp) count ..
-
[백준] 17086번 아기 상어 2 (by Python)Programming/Algorithm 2021. 4. 11. 18:00
문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 풀이 처음에는 각 칸에서 최소 거리를 구하는 아이디어를 떠올렸지만 computation cost가 너무 클 것 같다는 생각이 들었다. 그래서 빈칸에서 상어까지의 거리를 구할 것이 아니라 상어로부터 각 칸의 최소 거리를 propagate하는 방식으로 저장하면 보다 효율적일 것 같다고 생각했고, 다행히 시간 초과에 걸리지 않았다. import sys from coll..
-
[백준] 1303번 전쟁 - 전투 (by Python)Programming/Algorithm 2021. 4. 11. 17:40
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 전쟁터의 원소들을 하나하나 짚어나가면서 방문한 적이 없는 원소일 경우 방문해서 인접해있는 모든 같은 팀의 병사들을 BFS를 통해서 찾은 후에 병사들의 수를 제곱한 수를 해당하는 팀에 넣어준다. 그리고 나서 각 팀의 배열에 들어있는 수들을 모두 합해서 출력해주면 문제 해결~! import sys from collections import deque input = ..
-
[백준] 1038번 감소하는 수 (by Python)Programming/Algorithm 2021. 4. 8. 23:06
문제 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 def solution(n): num = 0 for _ in range(n): if num 1: str_num[i..
-
[백준] 17070번 파이프 옮기기 1 (by Python)Programming/Algorithm 2021. 4. 8. 22:52
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 처음에는 직관적으로 생각나는 대로 다음과 같이 BFS로 풀었다. import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] q = deque() q.append([(0, 0), (0..