본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[c++] 백준 11650 좌표 정렬하기 백준 단계별로 풀어보기 [정렬] 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net [풀이] STL의 sort를 이용해서 풀었다. sort(begin, end, pred)의 3가지 인자를 전달하는데, pred 자리에는 특정한 조건을 추가 인자로 받는다. 여기서는 두 x좌표가 같은 경우 y 좌표가 증가하는 순서대로 정렬되게끔하고 그 외의 경우에는 x좌표의 크기에 따라 정렬하는 boo..
[c++] 백준 2750 수 정렬하기 백준 단계별로 풀어보기 [정렬] 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net [풀이] 선택정렬을 사용하여 풀이하였다. 선택정렬은 첫번째 값을 그 다음 값부터 마지막 값까지 차례로 비교하여 가장 작은 값이 맨 앞에 오도록 swap해주는 방식을 반복하며 정렬을 수행한다. [코드] #include #define SWAP(x, y, z) ((z)=(x), (x=y), (y=z)) int main() { int num, least, temp=..
[c++] 백준 2798 블랙잭 백준 단계별로 풀어보기 [브루트 포스] 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net [풀이] 주어진 n개의 카드에 대해서 그 중 세 카드의 숫자의 합이 m을 넘지않으면서 가장 큰 경우의 합을 출력해야 한다. 배열에 저장한 카드의 모든 경우의 합을 구하되 앞의 카드와 같은 카드를 뽑지 않도록 continue를 걸고, m보다 작으면서 가장 큰 max 값을 구해 출력한다. [코드] #include int m..
[c++] 백준 2232 분해합 백준 단계별로 풀어보기 [브루트 포스] 분해합 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net [풀이] 245의 분해합은 245+2+4+5 = 256. 반대로 256의 생성자는 245가 된다. 생성자는 여러개일 수도, 없을 수도 있다. 1 0) std::cout
[c++] 백준 7568 덩치 백준 단계별로 풀어보기 [브루트 포스] 덩치 https://www.acmicpc.net/problem/7568' 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net [풀이] 몸무게를 배열 x에, 키를 배열 y에 저장한다. 본인보다 몸무게와 키가 모두 큰 경우에만 덩치가 큰 것으로 인정해 count 값을 증가시키고 count + 1인 자신의 등수를 배열 level에 저장한다. [코드] #include int main() { int n, count; std::cin >> n; int* x = new in..
[c++] 백준 1085 직사각형에서 탈출 백준 단계별로 풀어보기 [기본수학 2] 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] x, y, w-x, h-y 중 가장 min 값을 구하면 된다. [코드] #include int main() { int x, y, w, h; std::cin >> x >> y >> w >> h; w -= x; h -= y; x = x >= w ? w : x; y = y >= h ? h : y; std::cout = y ?..
[c++] 백준 4948 베르트랑 공준 백준 단계별로 풀어보기 [기본수학 2] 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net [풀이] 이전에 했던 소수 판정식을 이용해서 풀면 시간초과가 나온다. 따라서 에라토스테네스의 체라는 소수판별에 최적화된 알고리즘을 이용하여 풀어야 했다. 에라토스테네스의 체는 소수를 판별할 범위까지 배열을 만든 다음, 특정 수의 배수에 해당하는 수를 계속 지워나가는 방법이다. 이때 자기자신은 제외하고 이미 지워진 수는 건너뛴다. [코드]..
[c++] 백준 2581 소수 백준 단계별로 풀어보기 [기본수학 2] 소수 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net [풀이] 소수는 1과 자기자신으로만 나누어지는 수. 따라서 2~m/2까지의 수에 대하여 나누어떨어지는 수가 있으면 소수가 아니다. [코드] #include int main() { int m, n, sum = 0; std::cin >> m; std::cin >> n; int least = 10001, check = 1; if (m == 1) m++; for (; m

티스토리툴바