본문 바로가기

Algorithm 🧑🏻‍💻/Note12

[C++, 템플릿] 배열 돌리기와 달팽이 배열 1. 배열 상하 반전 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → 7 4 6 2 3 1 7 4 6 2 3 1 → 1 8 3 4 2 9 9 2 3 6 1 5 → 7 2 6 9 8 2 4 2 9 3 1 8 → 1 6 2 9 8 4 void cmd1(){ // 배열 상하 반전 int temp[101][101] = {0, }; for(int i=0; i 2022. 9. 22.

비트마스크(BitMask) 비트마스크(BitMask) 비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수(0, 1)로 표현합니다. 이러한 비트의 특성을 이용한 연산을 통해 문제를 해결해 기법을 비트마스크(BitMask)라고 합니다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다. 보통 어떤 비트가 1이면 전구가 "켜져 있다", 0이면 "꺼져 있다"라고 말하며, 전구뿐만 아니라 아래처럼 두 가지 경우로 표현할 수 있는 예시는 모두 가능합니다. 의자에 앉으면 1, 서있으면 0 남자면 1, 여자면 0 정답이면 1, 오답이면 0 사용 이유 비트마스크 기법을 사용하여 문제를 해결하는 큰 이유는 다음과 같습니다. 수행 시간이 빠르다. 메모리 사용량이 적다. 비트마스크 연산은 bit 연산이기.. 2022. 9. 16.

[C++, 템플릿] 유니온 파인드 유니온 파인드 #include #define MAX 100001 using namespace std; int N, M, ans; int parent[MAX]; int find_parent(int a){ if(a == parent[a]) return a; return parent[a] = find_parent(parent[a]); } void make_parent(int a, int b){ a = find_parent(a); b = find_parent(b); if(a 2022. 9. 2.

[C++, 템플릿] map find index Get index of element in C++ map Get index of element in C++ map I have a std::map called myMap in my C++ application, and I want to get an element using either myMap.find(key) or myMap[key]. However, I would also like to get the index of that element in the map... stackoverflow.com int k = distance(mymap.begin(), mymap.find(mykey)); 2022. 8. 23.

[C++, 템플릿] 다익스트라 다익스트라 #include #include #include #define INF 1E9 using namespace std; // 노드의 개수(V), 간선의 개수(E), 시작 노드 번호(K) // 노드의 개수는 최대 20000개라고 가정 int V, E, K; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열 vectorgraph[20001]; // 최단 거리 테이블 만들기 int d[20001]; void dijkstra(int start){ priority_queuepq; // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 pq.push({0, start}); d[start] = 0; while(!pq.empty()){ int dist = pq.top().first; //.. 2022. 5. 28.

[C++, 템플릿] 플로이드-와샬 플로이드-와샬 #include #define INF 1e9 // 무한을 의미하는 값으로 10억을 설정 using namespace std; // 노드의 개수(N), 간선의 개수(M) // 노드의 개수는 최대 500개라고 가정 int n, m; // 2차원 배열(그래프 표현)를 만들기 int graph[501][501]; int main(void) { cin >> n >> m; // 최단 거리 테이블을 모두 무한으로 초기화 for (int i = 0; i > b >> c; graph[a][b] = c; } // 점화.. 2022. 5. 13.

[C++, 유용한 문법] upper_bound, lower_bound lower_bound 용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함 lower_bound의 반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면, lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 줘야함. 1. array #include #include using namespace std; int main() { int arr[6] = { 1,2,3,4,5,6 }; cout 2022. 5. 11.

[C++, 템플릿] 소수 구하기(에라토스트네스의 체) 소수 구하기(에라토스트네스의 체) #include #include #include using namespace std; int main() { int N = 10000; // 0 ~10000까지의 소수 구하기 vectorprime(N + 1, true); // 최종적으로 true일 경우 소수 prime[0] = prime[1] = false; for(int i=2; i 2022. 4. 11.

[C++, 유용한 문법] 문자열 대소문자 변환 문자열 대소문자 변환 #include #include using namespace std; int main(){ string s = "ABCD"; string s2 = "abcd"; transform(s.begin(), s.end(), s.begin(), ::tolower); // 대문자 -> 소문자 transform(s2.begin(), s2.end(), s2.begin(), ::toupper); // 소문자 -> 대문자 } 2022. 4. 10.

이전 1 2 다음

티스토리툴바