Doby's Lab

이 문제는 전제가 좀 길다. 결론적으로 다음 단어들을 입력하고, 숫자를 입력하면 이름을, 이름을 입력하면 숫자를 출력하는 문제이다. 당연히 pair형 vector배열을 선언하여 풀려고 했지만 string을 입력했을 때는 어떻게 숫자 값을 도출할지가 문제였다. 여기서 사용된 것이 C++의 STL map이다. STL map은 이라는 헤더 파일에 선언되어있다. map m; 이런 방법으로 선언하여 key값과 value에 원하는 타입형을 선언하여 사용할 수 있다. 데이터를 삽입/삭제/찾기 시간 복잡도 모두 O(log N)이다. 같은 key값에 value를 삽입할 경우 기존에 있던 value값은 삭제된다. (해시 맵과는 다른 듯하다.) 삽입하는 방식은 m.insert(make_pair(key, value)); pa..

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다. 데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문) 그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다. (+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제)..

1838번 풀이 글과 이어진다. [이전 포스팅 링크] https://draw-code-boy.tistory.com/38 [알고리즘] 백준 1838번: 버블 정렬 (C++), 더 논리적인 감각을 만들어내야 한다 https://www.acmicpc.net/problem/1838 1838번: 버블 정렬 버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개 draw-code-boy.tistory.com [주소 연산자] 포인터에 바로 들어가기 전에 주소 연산자(&)를 알아보자 주소 연산자는 말 그대로 어떤 한 변수의 주소를 가져와주는 연산자이다. 예를 들어 #include int main() { char a = 'i';..

논리적으로는 쉬운 문제였다. 하지만, 내가 짜 놓은 논리와는 계속 엇나가는 출력이 나와서 1시간 동안 정렬할 때 쓴 compare 함수를 들여다보았지만 문제가 없는 듯했다. (일부는 내가 원하는 대로 정렬하지만 일부는 논리를 엇나갔었다.) #include #include #include using namespace std; bool cmp(vector& a, vector& b) { if (a[1] != b[1]) { return a[1] > b[1]; } else { if ((a[1] == b[1]) && (a[2] != b[2])) { return a[2] < b[2]; } else { if (((a[1] == b[1]) && (a[2] == b[2])) && (a[3] != b[3])) { retur..

이번 문제는 sort함수를 이용하며 compare에 더 깊게 파고들었다. sort 할 때 compare 함수를 다음 코드로 짜서 컴파일했지만 계속 어디서 나는지도 모를 오류 Invalid Comparator가 발생한다. (Comparator라서 비교 함수 쪽에 문제가 있구나는 인식할 수 있었다.) bool cmp(string a, string b) { if (a.size() = 0) { sumA += a[i]; } if (b[i] = 0) { sumB += b..

평소 문자열 문제(특히 입력)에 취약하던 입장에서 이 문제로 문자열 입력에 대해 정리를 하려 한다. 처음에는 string 변수를 선언하여 입력 문자들을 집어넣으려 했다. >> 공백 전의 한 단어밖에 담지 못 하기 때문에 pass getline() 그래서 공백을 포함한 모든 문자열을 담을 수 있는 방법이 필요했다. >> getline(입력스트림(입력할 방법(?)), 문자를 담을 곳, 이 문자가 나오면 입력을 끝내겠다는 문자) getline은 에 선언되어있다. ex) #include int main(){ string idx; getline(cin, idx, '\n'); } >> idx라는 string 변수에 cin을 통해 '\n'이 나오기 전까지 입력을 받겠다는 뜻이다. 그밖에도 문자열 입력에 관한 함수들을..

알고리즘 문제를 풀다보면 어떠한 특정 소수점 자리를 요구한다. 그럴 때 필요한 코드가 cout.precision과 fixed이다. cout.precision(n): 전체 자릿수를 n개로 가지겠다는 뜻이다. cout

이 문제가 요구하는 바는 다음과 같다. 길이가 짧은 것부터 정렬 길이가 같으면 사전 순으로 중복을 허용하지 않음 #include #include #include using namespace std; bool compare(string a, string b) {// 정렬 기준 함수 (optional function) return a.size() > T; vector idx; for (int i = 0; i > sample; idx.push_back(sample); } //크기가 작은 순으로 정렬 sort(idx.begin(), idx.end(), compare); /* ..