코드플러스(4)
-
백준 알고리즘 풀이 13458번 - 시험 감독
https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net - 그냥 구현하는 문제. 문제 조건대로 풀면 된다. -시간 복잡도- O(n) - 예외 조건 - 1. 사람이 기준치에 미치지 못하여도 감독관이 들어가야 한다. -소스 코드- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std;..
2019.10.10 -
백준 알고리즘 풀이 6359번 - 만취한 상범
https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net - dp 문제. - 알고리즘 - 입력받은 방의 수에서 가장 큰 걸 골라서 그 방수까지 dp를 수행. dp 수행 식 1 2 3 if (..
2019.10.07 -
코드 플러스 중급 그리디 알고리즘
그리디 알고리즘 -결정해야 할때 그 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘. -거스름돈 문제가 대표적인 문제지만, 모든 문제가 그런것은 아니다. -그리디 알고리즘은 증명이 어렵다 관련문제 : 11047번(동전 0) a[i]가 a[i-1]의 배수이므로 그리디 알고리즘을 사용하여도 문제가 없다. 다만 배수라는 조건이 없다면 다이나믹 프로그래밍을 통해서 해결하는 것이 옳다. cost[i]= cost[i-coint[k]]+1 1931번 (회의실 배정) 정렬하는 문제. 가장 빨리 끝나고 가장 빨리 시작하는 순서대로 정렬하면 편하다 11399번 (atm) 증명으로 가능 pf ) i번째 사람이 일을 보는데 시간을 p(i)라고 하면 i번째 사람이 기다려야 하는 시간은 시그마(1 각 자리수를 ..
2019.09.03 -
코드 플러스 스타트링크 백준 알고리즘 강의 기초 2강- 스택
코드 플러스 백준알고리즘 강의 정리. 1강부터 작성하려고 했지만 1강은 솔직히 그냥 몸풀기 같은 느낌이라 2강부터 정리해보려고 합니다. 스택에 대해 알아봅시다. stack이란? 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조. 마지막에 넣은 것이 가장 먼저 나오는 구조(한쪽이 막혀있는 원통 생각하면 편할 듯 프링글스 통) stack은 c++에 STL에 있기 때문에 구현해서 쓰기보다는 가져다 쓰는 것이 편하다. c++의 경우 : stack java의 경우 : java.util.Stack STL apt 정리 push : stack에 자료를 넣는 연산. return 값이 없다 pop : stack에서 자료를 빼는 연산(자료가 스택에서 삭제된다). return 값이 없다 top : stack의 가장 위에 잇는 ..
2019.05.02