본문 바로가기

Algorithm

 (129)
올바른 괄호의 갯수 (12929번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 올바른 괄호의 갯수 (12929번) 난이도 : Lv 4 Time Complexity : O( N^2 ) def solution(n): memo = [0] * (n+1) memo[0] = memo[1] = 1 for i in range(2, n+1): memo[i] = sum(memo[j] * memo[i-1-j] for j in range(i)) return memo[n] ★ 괄호..
이항 계수 3 (11401번) - 백준 (BOJ) https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 - 이항 계수 3 (11401번) 난이도 : Gold 1 알고리즘&자료구조 : Mathematics (수학) & Fertmat's little Theorem (페르마의 소정리) & Exponentiation by Squaring (빠른 거듭제곱) 페르마의 소정리를 알아야 풀 수 있는 문제이다. def factorial(s, e, val, mod): for i in range(s, e): val =..
Contact (1013번) - 백준 (BOJ) https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 백준 - Concat (1013번) 난이도 : Gold 5 알고리즘&자료구조 : Simulation (구현) 패턴 탐지 및 예외처리를 코드로 잘 구현해야 하는 문제이다. 이 문제는 본문의 코드처럼 풀 수도 있지만, 아래 링크와 같이 정규표현식 (Regular Expression) 을 활용해서, 아주 간단하게 해결할 수 있기도 하다. < 참고 : https://nerogarret.tist..
오아시스 재결합 (3015번) - 백준 (BOJ) https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 백준 - 오아시스 재결 (PATRIK) (3015번) 난이도 : Platinum 5 알고리즘&자료구조 : Stack (스택) 스택을 활용해서 풀 수 있는 문제이다. Stack으로 오름차순의 순열을 유지하며 해결할 수 있는 전형적인 스택 문제였다. import sys input = sys.stdin.readline class Waitings(): def __..
거의 최단 경로 (5719번) - 백준 (BOJ) https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 백준 - 거의 최단 경로 (Almost Shortest Path) (5719번) 난이도 : Platinum 5 알고리즘&자료구조 : Dijkstra (다익스트라) 다익스트라를 응용해서 풀 수 있는 문제이다. 일반적인 다익스트라 문제와는 조금 다르게, 가장 빠른 최단거리가 아닌 두 번째로 빠른 최단거리를 구해야 한다. import sys input =..
철로 (13334번) - 백준 (BOJ) https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 백준 - 철로 (Railway) (13334번) 난이도 : Gold 2 알고리즘&자료구조 : Priority Queue (우선순위 큐) & Sorting (정렬) import sys input = sys.stdin.readline from heapq import heappush, heappop class Railway(): def __init__..
약수의 합 (17425번) - 백준 (BOJ) https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 백준 - 약수의 합 (17425번) 난이도 : Gold 4 알고리즘&자료구조 : Mathematics & Prefix Sum (누적합) import sys input = sys.stdin.readline class Divisor(): def __init__(self, T): arr = [int(input()) for _ in range(T)]..
풍선 터트리기 (68646번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 풍선 터트리기 (68646번) 난이도 : Lv 3 Time Complexity : O( N ) 월간 코드 챌린지 시즌1 기출문제이다. def solution(a): n = len(a) if n rmin[i+1] and a[i] > lmin[i-1] else 1 for i in range(1, n-1)) + 2 ★ 문제 입출력 예 [-16, 27, 65, -2, 58, -92, -7..

티스토리툴바