문제풀기(63)
-
1005번 : ACM Craft
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 전형적인 위상정렬 문제이다. 다만 마지막 도착점에 대한 것이 아니라, 중간의 목표 지점에만 도달하면 되는 것이기 때문에 약간의 greedy를 포함하면 편하다. => max_times 배열 이용! import sys from collections import deque input = sys.stdin.readline t = int(input().rstrip()) for _ in range(t)..
2022.01.22 -
1806번 : 부분합
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 전형적인 투포인터 유형이다. 그동안 투포인터를 양 쪽에서 만나는 방식으로 사용했는데, 같이 출발하는 방식도 있다! import sys input = sys.stdin.readline n,s = map(int,input().rstrip().split()) numbers = list(map(int,input().rstrip().split())) prefix_sum = [0 for _ i..
2022.01.10 -
14179 : 빗물
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 해당 index까지 왼쪽에서는 높이가 몇인 벽이 가장 높은지, 오른쪽에서는 높이가 몇인 벽이 가장 높은지를 저장해놓은 후, 양쪽 벽 중 낮은 벽까지만 물이 찬다는 아이디어를 사용하면 된다. import sys input = sys.stdin.readline h,w = map(int,input().rstrip().split()) left = [0] * w right = [0] * ..
2022.01.04 -
프로그래머스 : 최솟값 만들기
https://programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 하나의 배열은 오름차순으로, 또 다른 배열은 내림차순으로 정렬 후, 같은 index에 있는 숫자들끼리 곱한게 가장 작다. 즉, 클수록 작은 수랑 곱하면 된다. def solution(A,B): answer = 0 A.sort(reverse=True) B.sort() for i in range(len(A)): answer += A[i]*B[i..
2021.11.16 -
프로그래머스 : 주식가격
https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 처음에 이중 for문으로 될까? 했는데 효율성까지 통과가 된다. def solution(prices): answer = [] for i in range(len(prices)): result = 0 for j in range(i+1,len(prices)): result += 1 if prices[j]
2021.11.16 -
프로그래머스 : 전력망을 둘로 나누기
https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 전선을 하나씩 끊어보고, 한 쪽만 BFS로 탐색하며 한 쪽 전력망에 속한 송전탑의 개수를 세어보고 남은 송전탑들과 얼마나 차이나는지 비교하면 된다. from collections import deque def bfs(start,visitied,graph): queue = deque([start]) result = 1 visitied[start] = True whi..
2021.11.03