본문 바로가기

Algorithm

 (129)
보석 도둑 (1202번) - 백준 (BOJ) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 백준 - 보석 도둑 (LOPOV) (1202번) 난이도 : Gold 2 알고리즘 : Priority Queue & Sorting 풀이 소요 시간 : 90분 Time Complexity : O( O(N * log(N) ) import sys input = sys.stdin.readline from heapq import heappush, ..
내리막 길 (1520번) - 백준 (BOJ) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 백준 - 내리막 길 (1520번) 난이도 : Gold 3 알고리즘 : DFS & Dynamic Programming 풀이 소요 시간 : 50분 Time Complexity : O( N * M ) import sys input = sys.stdin.readline sys.setrecursionlimit(pow(10, 9)) def dfs(r, c): ways = 0 for dr, dc in zip(dm,..
거짓말 (1043번) - 백준 (BOJ) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 백준 - 거짓말 (1043번) 난이도 : Gold 4 알고리즘 : DFS (Graph) 풀이 소요 시간 : 40분 Time Complexity : O( 파티 참석 인원수 총 합? ) import sys input = sys.stdin.readline if __name__ == '__main__': N, M = map(int, input().split()) truth = [False] * (N+1) # 1 _..
마법사 상어와 토네이도 (20057번) - 백준 (BOJ) https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 백준 - 마법사 상어와 토네이도 (20057번) 난이도 : Gold 3 알고리즘 : Simulation 풀이 소요 시간 : 90분 Time Complexity : O( N^2 ) 문제집 : 삼성 SW 역량 테스트 기출 문제 import sys input = sys.stdin.readline def scatter(d, r, c): dr, dc = drr[d], dcc..
고고학 최고의 발견 (131702번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/131702 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 고고학 최고의 발견 (131702번) 난이도 : Lv 3 알고리즘 : Simulation 풀이 소요 시간 : 50분 Time Complexity : O( (4^N) * (N^2) ) from itertools import product from copy import deepcopy import sys def solution(clockHands): answer = sys.maxsi..
랜덤 소트 (1521번) - 백준 (BOJ) https://www.acmicpc.net/problem/1521 1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 백준 - 랜덤 소트 (1521번) 난이도 : Platinum 5 알고리즘 : Dynamic Programming (동적계획법) & Mathematics (Permutation) 풀이 소요 시간 : 검색해서 아이디어 얻음 Time Complexity : O(N! * N^2) from itertools import permutations as p from itertools import com..
컬러볼 (10800번) - 백준 (BOJ) https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 백준 - 컬러볼 (10800번) 난이도 : Gold 3 알고리즘 : Sorting (정렬) & Prefix Sum (누적합) 풀이 소요 시간 : 33분 Time Complexity : O(NlogN) import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) stack = [] si..
회전 초밥 (2531번) - 백준 (BOJ) https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 백준 - 회전 초밥 (2531번) 난이도 : Silver 1 알고리즘 : Simulation, deque 풀이 소요 시간 : 27분 import sys input = sys.stdin.readline from collections import deque, Counter if __name__ == '__main__': N, d, k, c = map(int, i..

티스토리툴바