알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2445 2445번: 별 찍기 - 8 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 반복문을 사용한 별 찍기 문제입니다. 먼저 한줄에는 별과 띄어쓰기를 합해서 N*2개가 존재하는 것을 확인할 수 있습니다. 그리고 1~N / (N+1) ~ (N*2 - 1)로 줄을 나눠서 생각해보면 쉽습니다. 1번 줄에는 별이 1개씩 2번 나오고, 띄어쓰기는 N*2 -2개가 나옵니다. 2번 줄에는 별이 2개씩 2번 나오고, 띄어쓰기는 N*2 -4개가 나옵니다. 3번 줄에는 별이 3개씩 2번 나오고, 띄어쓰기는 N*2 -6개가 나옵니다. 4번 줄에는 별이 4개씩 2번 나오고, 띄어쓰기는 N*2 -8개가 나옵니다..

문제 링크입니다. https://www.acmicpc.net/problem/2523 2523번: 별 찍기 - 13 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 반복문을 사용한 별 찍기 문제입니다. 예제를 1~N과 N+1 ~ N*2-1로 나누어 생각하면 쉽게 구할 수 있습니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace std; int N; int main(){ cin.tie(0); cout.tie(0); cin..

문제 링크입니다. https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 반복문을 사용하는 별찍기 문제입니다. 첫줄에는 (N*2) - 1개의 별과 0개의 띄어쓰기가, 둘째 줄에서는 (N-1)*2-1개의 별과 1개의 띄어쓰기가, 세번째 줄에서는 (N-2)*2-1개의 별과 2개의 띄어쓰기가 있습니다. 이를 봤을 때, 1~N개까지의 줄에는 (N-i)*2-1개의 별과, 0~N-1개의 띄어쓰기가 나옴을 알 수 있습니다. N+1 ~ N*2-1개의 줄에는 이를 반대로 뒤집어 놓은 것음으로 반대로만 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/2443 2443번: 별 찍기 - 6 첫째 줄에는 별 2×N-1개, 둘째 줄에는 별 2×N-3개, ..., N번째 줄에는 별 1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. www.acmicpc.net 별 찍기 문제입니다. https://junseok.tistory.com/375 해당 문제를 거꾸로 만들었습니다. 참고해주세요 백준 2442 - 별 찍기 - 5(C++) 문제 링크입니다. https://www.acmicpc.net/problem/2442 2442번: 별 찍기 - 5 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. ww..

문제 링크입니다. https://www.acmicpc.net/problem/2442 2442번: 별 찍기 - 5 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. www.acmicpc.net 유명한 별찍기 문제입니다. 띄어쓰기와 별을 이용해 원하는 출력을 만들면 됩니다. 첫째 줄은 N-1개의 띄어쓰기와 1개의 별이 출력됩니다. 둘째 줄은 N-2개의 띄어쓰기와 3개의 별이 출력됩니다. 셋째 줄은 N-3개의 띄어쓰기와 5개의 별이 출력됩니다. 이와 같은 규칙을 찾아 반복문을 사용해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include..

문제 링크입니다. https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 구현 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace std; int N; int main(){ cin.tie(0); cout.tie(0); cin >> N; int cnt = 0, sum = 0; while(1){ if(N

문제 링크입니다. https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net DFS를 이용한 문제입니다. 첫번째 열이 다른 빵집, 마지막 열이 자신의 열일 때, 파이프라인을 최대 몇개까지 이을 수 있는지 구하는 문제입니다. 파이프 라인을 이을 수 있는 방법은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선인 총 3개입니다. 파이프라인을 최대로 짓는 수를 구하는 문제이기에, 첫째 열에서 모든 행의 값을 전부 DFS로 확인해봐야합니다. X번째 행에서 시작한 파이프가 마지막 ..

문제 링크입니다. https://www.acmicpc.net/problem/25304 25304번: 영수증 준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 준원이는 영수증을 보면서 정확하게 계산된 것 www.acmicpc.net 사칙연산을 이용한 간단한 문제였습니다. 영수증과 금액이 주어지고, 둘의 값이 맞는지를 확인하는 문제입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using n..

문제 링크입니다. https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 중위 순회를 이용해 푸는 문제였습니다. 1부터 N까지 열이 존재할 때, 트리의 노드를 적정하게 배치하여 하나씩만 위치하게 합니다. 이때, 최대 길이를 가지는 행을 구해주면 되는 문제입니다. 이 문제를 트리를 탐색하는 3가지 방법 중에, 중위 순회 방법이 가장 적당합니다. 왜냐하면, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식의 순서로 탐색을 진행하는데 1..

문제 링크입니다. https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 문자열과 배열을 이용해 푸는 문제입니다. 문자열이 주어진 뒤, 주어진 문자열에서 알파벳이 각각 몇개가 들어있는지를 구하는 문제입니다. 알파벳 갯수를 저장하는 배열을 만들어서, 해당 알파벳이 나올 때마다 값을 1씩 증가해줍니다. 마지막에 값을 전부 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #defin..

문제 링크입니다. https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 윗 줄의 숫자를 하나씩 선택할 때마다, 밑에 붙어 있는 숫자도 같이 선택됩니다. 윗 줄의 숫자를 선택해, 밑의 줄의 숫자와 같게 뽑으려고 할 때 몇 개, 어떤 숫자를 뽑아야하는지 구하는 문제입니다. 이 문제를 푸는 핵심은 윗 줄과 아랫 줄의 숫자를 연결해주는 겁니다. 만약 윗 줄이 1, 아랫 줄이 3이라면, connect[1] = 3..

문제 링크입니다. https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 공통 조상을 찾는 문제입니다. 두 노드가 주어지고 서로의 가까운 공통 조상을 찾는 문제입니다. 이 문제를 푸는 방법은 두 노드 중 하나의 노드를 선택해 해당 노드의 부모를 찾아준 뒤, 찾은 부모들의 값을 1로 바꿔줍니다. 남은 노드 하나를 탐색해, 해당 노드의 부모를 찾아줍니다. 이때, 노드의 값이 1인 것이 있다면, 해당 노드..