본문 바로가기
728x90

알고리즘49

[백준] 19941. 햄버거 분배 (2020 정올 중등 1번) <C++> www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다린 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사�� www.acmicpc.net 나의 풀이 0 ~ N-1 까지 가면서 사람이 나온다면 사람을 기준으로 k번만큼 왼쪽 ~ k번만큼 오른쪽까지 보면서 햄버거가 있다면 먹는다. 12345678910111213141516171819202122232425#include #include using namespace std; int main() { string arr; int n, k, cnt=0, sw; cin >> n >> k; cin >> ar.. 2020. 9. 23.
[백준] 19939. 박 터뜨리기 (2020 정올 초등부 1번) <C++> www.acmicpc.net/problem/19939 19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 � www.acmicpc.net 규칙을 찾는 문제였다. 규칙만 찾는다면 구현은 금방 하는 문제이지만 규칙 찾기가 쉽지 않았다. 우선 공을 가장 적게 분배해준다. 1) k = 3이라면 1 2 3 > n >> k; for (i = 1; i 2020. 9. 22.
알고리즘의 시간복잡도 알고리즘의 성능 평가 같은 문제를 풀어도 여러 방법의 알고리즘이 나옵니다. 여러 알고리즘 중 가장 효율적인, 성능이 좋은 방법을 택하는 것이 좋겠죠. 옛날에는 메모리가 비싸 메모리를 가장 적게 사용하는 것이 최적의 알고리즘이었습니다. 그러나 요즘은 메모리의 가격이 낮아져 알고리즘의 성능을 따질 때 가장 중요하게 보는 것은 '시간'입니다. 시간 복잡도 알고리즘의 성능은 시간으로 나타낼 수 있습니다. 다만 컴퓨터의 성능에 따라 차이가 있습니다. 그래서 시간이 얼마나 걸리는지를 알 수 있는 좀 더 객관적인 지표가 필요합니다. 따라서 보통 시간복잡도(Time complexity)라는 지표를 사용합니다. 여기서 말하는 시간복잡도는 입력 값에 따른 처리에 걸리는 시간을 말합니다. 여기서 말하는 시간은 "연산의 실행.. 2020. 9. 16.
[백준] 1676. 팩토리얼 0의 개수 <C++> www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 다 곱해보면 long long으로도 표현할 수 없기 때문에 0의 개수를 알 수 있을만한 규칙이 필요하다. 우선 뒷자리에 0이 언제 나오는지 알 필요가 있다. 5! = 120 5 = 5 * 1 -> 5가 하나 (+1) 0이 1개 10! = 3,628,800 10 = 5 * 2 -> 5가 하나 (+1) 0이 2개 15! = 1,307,674,368,000 15 = 5 * 3 -> 5가 하나 (+1) 0이 3개 20! = 2,432,902,008,176,640,000 20 = 5 * 4 -> 5가 하나.. 2020. 9. 5.
[백준] 10814. 나이순 정렬 <C++> https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net pair와 정렬의 연습 문제이다. > pair 사용법 #include #include #include using namespace std; bool comp(pair a, pair b){ return a.first > n; for(int i=0; i> old >>.. 2020. 9. 4.
[백준] 11650. 좌표 정렬하기(1, 2) <C++> www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 간단한 정렬 문제이다. pair를 사용한 정렬 연습에 적절한 문제! - pair의 간단한 사용 방법 [C++] pair Pair 란? - 두 객체를 하나로 묶어주는 클래스이다. (좌표 등을 표현하기에 적절하다.) - 헤더에 존재한다. Pair의 기본 사용 방법 선언 pair p; - 묶어줄 두 값의 데이터 타.. korean-otter.tistory.com .. 2020. 9. 4.
[C++] pair Pair 란? - 두 객체를 하나로 묶어주는 클래스이다. (좌표 등을 표현하기에 적절하다.) - 헤더에 존재한다. Pair의 기본 사용 방법 선언 pair p; - 묶어줄 두 값의 데이터 타입을 넣어주고, 변수 명을 지정한다. 입력, 값 할당 cin >> x >> y; p = make_pair(x, y); make_pair(변수1, 변수2): 변수1, 변수2를 묶어준다(pair를 만들어준다). - pair로 만든 변수에는 값을 바로 입력받을 수 없다. 그래서 두 변수에 입력받고 난 후에 묶어주어야 한다. 출력 cout 나이순 정렬 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞.. 2020. 9. 4.
[NYPC] [2019 예선] 1. 최대 HP 문제 당신은 게임 "마비노기 영웅전"의 전투 로그 분석을 맡게 되었다. 이번에 분석할 전투는 마법 전문가인 이비의 전투이다. 이비는 몬스터와 전투를 했고, 이 때 전투 과정에서 발생하는 게임 로그인 전투 로그는 시작 체력과 여러 개의 턴으로 이루어져 있다. 그리고 각 턴 마다 다음의 로그가 한 줄에 하나씩 기록되어있다. 이비가 데미지를 받는다. 이 턴 이후에 체력이 h 만큼 줄어든다. 단, 데미지를 받아서 체력이 0 이하가 되는 경우는 없었다. 이 로그는 1 h 형태로 기록된다. 이비가 "회복" 스킬을 사용한다. 이 턴 이후에 체력이 h만큼 회복된다. 단, 회복을 해서 최대 체력을 넘어가는 경우는 없었다. 이 로그는 2 h 형태로 기록된다. 이비가 "최대 생명력" 스킬을 사용한다. 이 턴 이후에 체력이 .. 2020. 8. 30.
[codeground] Practice. 11. 개구리 뛰기 문제 일직선 상에 돌들이 놓여있고, 개구리가 처음에는 '좌표 0'에 위치한 돌 위에 앉아 있다. '좌표 0'에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1) [ 그림 1 ] 개구리는 점프를 통해서 돌들 사이를 이동해서 마지막 돌까지 이동해야 한다. 이 때, 개구리가 한번의 점프로 이동 가능한 최대 거리 K 가 주어진다. 개구리는 한번의 점프로 자신이 앉아 있던 돌에서 K 이하의 거리에 위치한 돌들 중 하나의 돌로 이동 할 수 있다. 여기서 문제는, '좌표 0'에 위치한 개구리가 마지막 돌까지 이동할 수 있다면, 마지막 돌까지 이동하기 위한 최소 점프 횟수를 계산하는 것이다. 예를 들어서, 위의 "그림1"의 예에서 보면, 한번의 점프로 이동 가능한 최대 거리가 K=4 로 주어질.. 2020. 8. 26.
728x90

티스토리툴바