본문 바로가기

알고리즘204

[백준] 4779번 - 칸토어 집합 (C++) 문제 및 풀이 문제) 백준 - 분할 정복 - 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 큰 문제를 작은 문제로 쪼갤 수 있는 분할 정복 문제입니다. n이 0일 때 "-"를 출력하고, 0보다 클 경우 3 등분으로 쪼개어 작은 문제로 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/4779_%EC%B9%B8%ED%86%A0%EC%.. 2022. 2. 27.
[백준] 14400번 - 편의점 2 (C++) 문제 및 풀이 문제) 백준 - 정렬 - 편의점 2 https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 거리의 최소를 구하는 문제였습니다. 거리의 최소는 x 좌표와 y좌표의 중간값을 고르면 구할 수 있습니다. C++ 소스 코드) 2022. 2. 26.
[백준] 10988번 - 팰린드롬인지 확인하기 (Python) 문제 및 풀이 문제) 백준 - 문자열 - 팰린드롬인지 확인하기 https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문자열의 앞,뒤가 같은지(팰린드롬인지) 확인하는 문제였습니다. Python 소스코드) 2022. 2. 25.
[백준] 21758번 - 꿀 따기 (C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 - 꿀 따기 https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 벌과 꿀통의 위치에 따라 최대 꿀의 양을 구합니다. 각 벌과 꿀통은 양쪽 끝에 위치해야 꿀의 최대를 가질 수 있습니다. (벌 벌 꿀), (벌 꿀 벌), (꿀 벌 벌) 순서로 최대 꿀의 양을 계산하며 누적 합을 이용하여 빠르게 구할 수 있습니다. C++ 소스코드) 2022. 2. 24.
[백준] 11655번 - ROT13 (C++) 문제 및 풀이 문제) 백준 - 문자열 - ROT13 https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문자열을 입력받아 하나씩 변환하여 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11655_ROT13.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions. Contribute to Chocochip101/BOJ_Solution developmen.. 2022. 2. 24.
[백준] 21317번 - 징검다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 전형적인 동적 계획법으로 쉽게 해결할 수 있는 문제였습니다. solve(i, usedMegajump)를 통해 i 번째 돌까지 갔을때 필요한 최소 에너지의 memoization을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21317_%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0.cpp .. 2022. 2. 23.
[백준] 20495번 - 수열과 헌팅 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 수열과 헌팅 https://www.acmicpc.net/problem/20495 20495번: 수열과 헌팅 예제에서, 수열의 수들을 차례로 x1, x2, x3이라 하자. -10 ≤ x1 ≤ 30, 25 ≤ x2 ≤ 55, 55 ≤ x3 ≤ 85이다. 만약 (x1, x2, x3) = (28, 25, 70)이라면, x2가 첫번째, x1이 두번째, x3이 세 번째 수가 된다. 또, (x1, x2 www.acmicpc.net 최대, 최소를 배열과 벡터에 저장합니다. 배열에 있는 수는 탐색할 숫자이며 벡터에 있는 수는 정렬을 하여 탐색할 범위입니다. 최솟값을 최댓값이 정렬된 벡터의 lower_bound, 최댓값을 최솟값이 정렬된 벡터의 upper_bound를 통해 인덱스를 구합니다... 2022. 2. 23.
[백준] 6996번 - 애너그램 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 애너그램 https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수( 2022. 2. 23.
[백준] 20294번 - 트리의 기둥과 가지 (C++) 문제 및 풀이 문제) 백준 - DFS/트리 - 트리의 기둥과 가지 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net DFS를 통해서 기둥과 가지를 탐색합니다. 기둥의 기준은 이어진 노드가 단 하나여야 되므로 graph의 사이즈가 1인 노드가 이어질 때까지 탐색합니다. 기둥의 마지막 부분을 저장해 가장 긴 가지를 탐색해 출력합니다. C++ 소스코드).. 2022. 2. 22.
반응형

티스토리툴바