Code Etc
-
그리디 알고리즘 - 백준 1931 pythonCode Etc/코딩테스트 2023. 5. 9. 20:19
그리디 알고리즘이란 동적 프로그래밍에서 지나치게 많은 일을 한다는 점을 착안하여 고안된 알고리즘으로 특정 상황에서 최적해를 구하는데 사용합니다. 특정 상황이라는 점이 키포인트이며 이를 만족하지 못하면 효과적인 알고리즘이 아닐 수 있습니다. 바로 문제부터 풀어보시죠 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 가능한 많은 회의실을 이용하는 문제였는데 회의 시간이 같거나 같은 시간에 시작해서 다르게 끝나는 경우가 많은 문제였습니다. import sys input = sys.stdin.readline n = int(input().rstrip()) cases = ..
-
누적합 - 백준 11659, 2559Code Etc/코딩테스트 2023. 4. 28. 02:22
누적합은 말그대로 합을 누적하는건데.. 어떻게 코드를 짜느냐에 따라 시간복잡도가 엄청 달라진다.. 먼저 가장 기본 중의 기본인 문제부터 풀어보자 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 하나의 배열이 주어지고 시작점과 끝 지점의 구간합을 구하는 문제이다. import sys input = sys.stdin.readline n,cases = map(int,input().rstrip().split()) li = lis..
-
큐, 덱 - 백준 5430Code Etc/코딩테스트 2023. 4. 16. 18:43
큐와 덱은 하나의 자료구조인데 큐는 First In First Out의 구조를 가진 형태이다. 먼저 들어온 게 먼저 나가는 구조이다. 덱은 이와 비슷하지만 나가는 출구가 2개인 녀석이다 보통 앞에서 뽑아내는 경우 메모리를 정렬하는 과정에서 많이 소모되는데 덱은 빠져나간 메모리 삭제까지 알아서 해주니 꽤 빠르고 좋다. 문제를 하나 풀어보자 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 입력으로 testCase와 수행할 명령어, 배열의 길이, 배열이 주어지고 이에 따라 알맞은 동작을 수행하면 알고리즘을..
-
스택 - 백준 1874Code Etc/코딩테스트 2023. 4. 11. 13:54
스택이란 Last In First Out의 구조를 갖는 자료구조의 일종이다. 이를 구현하는 문제들을 전부 풀어보았는데 가장 고난이도 문제를 가져왔다 스택은 전에 공부한 적이 있어서 꽤 수월하게 풀어냈다. 바로 문제를 보자 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net n = int(input()) #전체 숫자 갯수 stack = [] answer = [] fla..