알고리즘
-
백준 2581번 : 소수정수론(Number theory) 2018. 6. 20. 12:16
https://www.acmicpc.net/problem/2581 1. 문제자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다. 2. 알고리즘소수의 합을 저장 할 SUM 이라는 변수를 선언한다.소수 판별을 하여 소수이면 SUM 에 적산 한다. 소수 중 가장 작은 값을 찾기 위해 CAND 라는 변수를 선언 하고 987654321 로 초기화 한다.소수 판별을 하여 소수이면 CAND 보다 작다면 CAND 를 현재 값으로 치환..
-
백준 11441번 : 합 구하기다이나믹프로그래밍(DP) 2018. 6. 18. 14:50
https://www.acmicpc.net/problem/11441 1. 문제 N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 알고리즘 키워드 - 부분 합최초의 입력 받은 배열은 위 처럼 10, 20, 30, 40, 50 으로 이루어 져있는 배열이다. 배열의 부분합을 만들기 위해 0 번째 배열을 추가하고 배열[i-1] + 배열[i] 부분 합을 구한다. 문제 에서 1번과 4번 배열의 합을 구하라고 나와 있다. 1번 부터 N 까지는 모두 계산이 되어 있음으로 위와 같이 답을 도출 할 수 있다. 두번 째 예제에서는 2번 부터 4 까지의 합을 계산 해야 한다.2번 의 부분합은 30 임으로 ..
-
백준 1453번 : 피시방 알바구현(Implementation) 2018. 6. 18. 11:52
https://www.acmicpc.net/problem/1453 1. 문제세준이는 피시방에서 아르바이트를 한다. 세준이의 피시방에는 1번부터 100번까지 컴퓨터가 있다. 들어오는 손님은 모두 자기가 앉고 싶은 자리에만 앉고싶어한다. 따라서 들어오면서 번호를 말한다. 만약에 그 자리에 사람이 없으면 그 손님은 그 자리에 앉아서 컴퓨터를 할 수 있고, 사람이 있다면 거절당한다. 거절당하는 사람의 수를 출력하는 프로그램을 작성하시오. 컴퓨터는 맨 처음에 모두 비어있고, 어떤 사람이 자리에 앉으면 자리를 비우는 일은 없다. 2. 알고리즘크기 101의 정수 배열을 선언하고 모두 0 으로 초기화 한다.입력받은 N 의 값 만큼 정수를 입력 받아 배열 인덱스에 값을 증가 시킨다. 분기 1. 이미 1로 채워진 배열의 ..
-
백준 2667번 : 단지번호붙이기깊이우선탐색(DFS) 2018. 6. 18. 11:12
https://www.acmicpc.net/problem/2667 1. 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 2. 알고리즘 0, 0 부터 검색을 시작 하여 현재 위치에서 상하좌우에 값이 1이면 이동한다. 더이상 갈 곳이 없다면 현재 까지 이동한 횟수를 카운트 한..
-
백준 10156번 : 과자구현(Implementation) 2018. 6. 17. 16:17
https://www.acmicpc.net/problem/10156 1. 문제 요약 단순 구현 문제 2. 알고리즘 단순 구현 문제 3. 코드 12345678910111213141516171819202122232425#include #include #include #include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int k, n, m; cin >> k >> n >> m; int cand = n * k; if (cand > m) { cout
-
백준 1927번: 최소힙큐(Queue) 2018. 6. 17. 13:54
https://www.acmicpc.net/problem/1927 1. 문제 요약최소힙 구현 문제 2. 알고리즘priority_queue 사용 greater 사용하여 최소힙으로 사용 3. 코드12345678910111213141516171819202122232425262728293031323334#include #include #include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); priority_queue q; int n; cin >> n; while(n--) { int cand; cin >> cand; if (cand ..
-
백준 11279번 : 최대 힙큐(Queue) 2018. 6. 17. 13:45
https://www.acmicpc.net/problem/11279 1. 문제 요약 맥스 힙 이해 2. 알고리즘 STL 자료구조인 priority_queue 를 사용하여 해결 3. 코드 123456789101112131415161718192021222324252627282930313233#include #include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); priority_queue q; int n; cin >> n; while(n--) { int cand; cin >> cand; if (cand == 0) { if (q...
-
백준 2605번 : 줄 세우기리스트(List) 2018. 6. 17. 11:14
https://www.acmicpc.net/problem/2605 1. 문제 요약 입력받은 정수로 임의 접근하여 원소를 삽입 하는 문제 2. 알고리즘 자료구조 List 임의 접근을 사용하여 해결. 3. 코드 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; list arr; list::iterator iter; for(int i=1; i> cand; for(iter = arr...