c++

[C++] 객체 지향 프로그래밍 - 얕은 복사와 깊은 복사 (Heap 메모리, Stack 메모리)

객체 지향 프로그래밍 (Object Oriented Programming, 이하 OOP)에서의 데이터의 단위는 객체이다. OOP에서의 객체 복사는 기존 객체의 사본을 만드는 일이다. 복사의 방식은 얕은 복사(참조 형식)와 깊은 복사(값을 복사)가 존재하게 된다. 예시 코드 /* * OOP - 얕은 복사와 깊은 복사 */ #include using namespace std; class MyObject { public: string* name; int age; //기본 생성자 MyObject(int age, string name) { this->name = new string(name); this->age = age; } //기본 복사 생성자와 같음. 레퍼런스로 만들지 않으면 복사생 //MyObject(co..

[C++] algorithm STL의 sort()와 queue STL의 priority_queue의 정렬 방식의 차이 - less와 greater

Sort() - algorithm STL less : 오름차순 greater : 내림차순 priority_queue - queue STL less : 내림차순 greater : 오름차순

[C++] priority_queue STL 비교 구조체 comparator 사용하기

algorithm STL에 있는 sort() 메서드를 사용할 때에는, 그냥 bool형 비교 메서드 하나만 만들어주면 됐었다. queue STL에 있는 priority_queue를 사용할 때에는 less()를 써서 내름차순으로 만들거나 greater()를 써서 오림차순으로 만들 수 있다. 그러나 class 형식으로 만들어서 쓰고싶을 때에는 구조체를 만들어서 그 안에 bool형 operator()(A, B)의 형태의 메서드를 만들어 주어야 한다. bool 메서드는 return true일 때 앞 뒤를 바꾼다고 생각하면 된다. 따라서 위처럼 만들 경우 p1의 시간, type에 따라 오름차순으로 정렬된다고 생각하면 된다. pq 선언은 다음처럼 해주면 된다.

[C++] Comparator 사용시 주의사항

10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 위 문제를 풀면서 조금 헷갈리는 것이 있어서 메모기록용 글. 매개변수에서 앞에 있는 애가 배열의 앞 부분이고 뒤에 있는 애가 배열의 뒷 부분이라 생각하면 된다. 즉, 앞 뒤 라면 내림차순이다.

<algorithm> STL에서 sort의 comparator 작성 시, invalid comparator 문제

1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 백준에서 해당 문제를 푸는데 문자열을 그냥 정렬하는 문제였다. 근데 sort에서 자꾸 invalid comparator문제가 발생해서 알아보았다. Sort 메서드에서 comparator로 들어오는 매개함수는 반드시 Strict Weak Ordering을 만족해야 한다. 이게 무슨말이냐면, A == B일 경우에는 A B도 false여야 한다는 말이다. 위처럼 comparator를 작성해서 사용했는데, 이 코드에서는 str1..

[C++] 백준 2193번 이친수

DP 문제 이런 류의 DP 문제는 항상 1부터 차례대로 해 보면서 점화식을 세우는 것이 중요하다. 시도 방식 & 문제 풀이 점화식을 구해서 코드로 구현했다. 규칙성이 바로 보이므로 점화식을 찾는데는 문제가 없었다. 근데 여기서 N이 90이 되면 엄청나게 큰 수가 된다. 따라서 dp배열을 int가 아닌, long long형태의 배열로 만들어 주는 것이 중요하다. 처음 시도는 TOP DOWN방식의 재귀형태로 시도했는데, 시간초과가 났다. 그리고 위 방식대로 풀었는데, OVERFLOW가 나서 틀렸습니다 가 나왔다. 자료형을 바꾸고 나서는 바로 맞출 수 있었다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kim..

[C++] 백준 2156번 포도주 시식

다이나믹 프로그래밍 문제. 처음 문제를 보고 예전에 풀었던 계단 오르기와 비슷한 문제라고 생각했다. [C++] 백준 2579번 계단 오르기 다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수 kimyunseok.tistory.com 그런데 막상 문제를 풀어보니 엄청 많이 틀렸고, 반례들을 통해 잘못된 점을 알게됐다. 문제 접근방식 우선 조건으로 주어지는 건 간단하다. 최대한 많은 양을 먹어야 하고 3잔을 연속으로 먹는 건 불가능하다. 천국의 계단 같은 경우는 어차피 +1 아니면 +2였기 때문에 이 문제도 똑같은 방식으로 접근했다. 이 두 개 조건을 가지고 문제를 풀려..

[C++] 백준 1912번 연속합

DP 문제. 수를 연속해서 선택하는데, 어떤 경우에 해당하는 번째의 수가 최대값을 가지게 되는지 구하는 문제이다. 문제에 접근한 방식 문제를 읽어보고, DP Bottom Up 방식으로 접근을 시도했다. 값을 더했을 때 계속 양수인 경우, 계속해서 더해주면 그게 구할 수 있는 가장 큰 합이 된다. 값을 더했을 때 음수가 나오는 경우, 그 값을 더하지 않는 것이 더 큰 값이므로 더이상 더해주지 않고 새로 시작한다. 따라서 점화식은 최대값이 An이고, 현재 수가 Bn을 나타낼 때 An = max( A(n-1) + Bn, Bn)이 된다. 이렇게 두 개를 고려하고 문제를 접근하면 된다. 자세하게 고려하고 풀지는 않았는데, 지금 보니 왜 저렇게 생각했는지 풀었으면 더 좋았을 것 같다. 문제풀이 최대값을 갱신시켜 주..

[C++] std::sort 오름차순 내림차순 정렬

greater와 less를 사용한다. int형 vector를 정렬할 때는 오름차순 : sort(vec.begin(), vec.end(), less()); 내림차순 : sort(vec.begin(), vec.end(), greater()); priority_queue 선언할 때와는 다르게 끝에 () 괄호도 추가해야 한다.

[C++] 백준 1697번 숨바꼭질

그래프 탐색 문제인 줄 몰랐던 그래프 탐색 문제. 알고보니 모든 정점들이 서로 연결돼 있던 그래프였다는 것을 문제에서 설명해 주고 있었다. 이 사실을 질문 검색 게시판을 보다가 알게되었다. 처음 이문제를 보았을 때 수학 문제인 줄 알았다. 그래서 경우의 수를 나눠서 구현해야 하는 줄 알고 그렇게 시도했다. 결과는 틀렸습니다가 나왔다. 그래서 어떻게 풀어야 할까 고민하면서 질문 검색 게시판을 보았다. 두번째 시도 게시판에서 보니 사람들이 그래프 탐색으로 많이 풀었다는 사실을 알게되었다. "이 문제를 어떻게 그래프 탐색으로 풀까..?" 고민하던 찰나에 머리에 다익스트라와 비슷한 알고리즘이 스쳐지나갔다. 게시판 검색 안했다면 아마 생각 못하지 않았을까 생각한다. 정말 많은 문제를 풀어봐야 겠다고 생각했다. D..