'Algorithm/BOJ' 카테고리의 글 목록

Algorithm/BOJ

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

2021.08.11

그리디 알고리즘이란? "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 거스름돈을 돌려주는 문제를 생각해보자. 우리는 대부분 거스름돈을 돌려줄때 큰 단위의 동전부터 거슬러준다. ex ) 500원을 돌려줘야 한다면, 100원을 5개 주는 것보다 500원을 1개 주는 편이 더 편하다. 하지만 만약에 동전의 단위가 100, 250, 300 이라면, (300 * 1) + (100 * 2) 로 3개로 거슬러주는 것보다는 250 * 2 의 방법으로 2개로 거슬러주는 것이 더 최적의 방법이다. 따라서 그리디 알고리즘은 항상 최적의 해를 제공해주는 것은 아니다. 하지만 만약 이 상황에서 큰 단위의 수부터 거슬러줘야하는 조건이 존재할 때 그리디 알..

Algorithm/BOJ

백준(BOJ) 1931번 회의실배정 [그리디(Greedy)/알고리즘/파이썬(python)]

2021.08.07

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보..

Algorithm/BOJ

백준(BOJ) 11000번 강의실배정 [그리디(Greedy)/알고리즘/파이썬(python)/큐]

2021.08.06

11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < ..

Algorithm/BOJ

백준(BOJ) 1158번 요세푸스 [알고리즘/파이썬(python)/연결리스트]

2021.07.07

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net [문제] 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 ..

Algorithm/BOJ

백준(BOJ) 9012번 스택문제 [파이썬(python)]

2021.07.02

https://www.acmicpc.net/problem/9012 [문제] 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 ..

Algorithm/BOJ

백준(BOJ) 10828번 스택문제 [파이썬(python) / 시간초과 에러]

2021.06.28

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 백준 알고리즘 10828번 스택문제 [문제] 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수..

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Algorithm/BOJ

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

백준(BOJ) 1931번 회의실배정 [그리디(Greedy)/알고리즘/파이썬(python)]

백준(BOJ) 11000번 강의실배정 [그리디(Greedy)/알고리즘/파이썬(python)/큐]

백준(BOJ) 1158번 요세푸스 [알고리즘/파이썬(python)/연결리스트]

백준(BOJ) 9012번 스택문제 [파이썬(python)]

백준(BOJ) 10828번 스택문제 [파이썬(python) / 시간초과 에러]

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역