본문 바로가기

C++20

프로그래머스: 알고리즘 문제 풀이(c++) 1. 해시파트1-1. 포켓몬set함수를 통해 중복 요소 제거nums.size()/2 : nums의 요소개수의 절반보다 nums_set의 요소가 더 많다면 최대 nums_set의 개수만큼 각기 다른 종류의 포켓몬이 존재한다는 것 어차피 최대 nums/2 종류의 개수만큼 고를 수 있기에 nums/2가 반환nums.size()/2 > nums_set.size(): nums.size()/2개 최대 고를 수 있는데 각기 다른 종류의 개수인 nums_set.size()가 더 작다면 어차피 nums_set.size()개만큼 골라야 다른 종류를 최대 고를 수 있음#include #include #include using namespace std;int solution(vector nums) { int ans = 0;.. 2024. 7. 23.
[C++] 백준 3085 1. 문제 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 2. 고려사항 (1) main함수 ( 편의상 2차원 배열을 NxN 행렬이라 표현하겠음 ) N 입력받으면 동적할당 이용하여 2차원 배열 생성 후 모든 요소 값 입력 NxN 행렬에서 i=0~N, j=0~N까지 반복문을 돌리면서 값이 다르면 swap을 해준다 이때, 굳이 행렬 요소의 동서남북 체크 필요 없이 오른쪽, 아래방향으로만 체크해나감(뻗어나간다고 생각) → ex.arr[0][1]과 이 요소의 오른쪽 arr[0][2]를 swap했다면 arr[0][2]일땐 왼쪽을 검사할 필요 없음 이때, 배열 int dx.. 2024. 3. 27.
[c++] 6588 백준 문제풀이(시간초과 해결) 1. 문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 2. 시간초과 코드 #include #include using namespace std; bool isPrime(int num){ for(int i=2;i>n; if(n==0){ break; } for( i=3;i 2024. 3. 27.
[C++] Merging Sort 1. 병합 정렬 : Divide Conquer 기법 이용 1-1. 병합 정렬 알고리즘 동작 과정 재귀문을 돌며 주어진 배열들을 단말노드로 될 때까지 Divide void MergeSort(int * arr, int * tmp, int start, int end) { if (start < end) { int mid = (start + end) / 2; MergeSort(arr, tmp, start, mid); MergeSort(arr, tmp, mid + 1, end); Merge(arr, tmp, start, mid, end); } } 분리된 배열들을 정렬하며 합치는 과정 void Merge(int* arr, int* tmp, int start, int mid, int end) { int idx = st.. 2023. 12. 14.
[C++] 이분 그래프(Bigraph) 1. 이분 그래프 (Bipartite Graph) : 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프 : 이때, 모든 사이클의 길이는 짝수이다 ( ⇔ odd length cycle은 존재하지 않는다 ) 1-1. 그래프 이론 If a graph has no odd cycle then it must be bigraph. 2. 이분 그래프 알고리즘 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 2-.. 2023. 12. 13.
[c++] Heap 1. 힙 : 관련 내용은 아래 글 참조 2023.11.20 - [Python/자료구조] - [python] 우선순위 큐 [python] 우선순위 큐 1. Heap(힙) : 주로 완전이진트리 기반으로 구현하며 정렬하는 용도의 이진트리이다 -> 마지막 레벨 노드 제외하고는 포화상태인 트리 cf> 힙 구현 : 완전이진트리 기반이기에 연결리스트보다 배열 growingupis.tistory.com 1-1. 힙 기본 동작 구성 swim_up : 특정 인덱스에서 위로 올라가며 조건 만족하면 swap sink_down : 특정 인덱스에서 아래로 내려가며 조건 만족하면 swap trim : 힙의 루트노드 반환 grow : 힙에 원소 삽입 swap : 노드 교환 Heap.h #pragma once #include usin.. 2023. 12. 8.

티스토리툴바