조준화의 오류정정

#include #include #include int main() { std::map myMap; myMap[3] = "Three"; myMap[1] = "One"; myMap[4] = "Four"; myMap[2] = "Two"; // 맵의 모든 요소를 벡터로 옮김 std::vector myVector(myMap.begin(), myMap.end()); // 벡터 출력 for (const auto& pair : myVector) { std::cout

2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 9 3 1 3 3 3 2 2 2 1 1 ans : 1 1 1 3 3 3 2 2 2 빈도를 기준으로 정렬하되, 들어온 순서를 유지하면서 정렬해야 한다. 빈도만 기준이었다면 떠오르는 방법은 아래와 같다. 맵에 빈도를 key로 값을 value로 해서 삽입한다. pair vector에 빈도, 값으로 삽입을 한 뒤 빈도를 기준으로 sort를 한다. 두 방법에서 기존 입력의 순서를 유지할 방법을 생각해 봤는데, sort를 병합 정렬로 직접 구현하지 않는 이상 맵이나 벡터를 확장하는 방법이었다. 맵 2개 사용, 하나..

기본적인 방법은 cmp함수를 정의해서 거기에 정렬 기준을 구성하고, sort 함수나 map, priority_queue에 인자로 넣어주면 된다. 맵과 셋에서의 사용법은 똑같다. 내림차순 cmp 함수를 정의하려면 어떻게 할까? return a > b; 이것만 기억하면 된다. cmp 함수로 앞에 들어온 인자가 더 큰 것을 리턴하게 하면, 더 큰 것을 앞으로 두고 정렬하겠다는 뜻이다. 실제 사용 예시들을 보자. #include #include struct CustomCompare { bool operator()(int a, int b) const { return a > b; // 내림차순 정렬 } }; int main() { std::map myMap; myMap[3] = "Three"; myMap[1] = ..

맵과 셋, 우선순위 큐는 항상 헷갈린다. 이번에 확실히 정리해 보자. Map, multi Map 맵은 기본적으로 레드-블랙 트리를 사용한 자료구조이다. key, value쌍을 가지며 key를 기준으로 오름차순 정렬하여 저장한다. 레드-블랙 트리로 구성되어 있으므로 항상 트리의 높이가 log n을 유지한다. 또, 중복을 허용하지 않고 multi Map만 중복을 허용한다. 맵은 주로 고유한 키와 값을 연결하여 정렬할 필요가 있을 때 사용한다. 또, 모든 값에 대해 빠른 접근과 삽입/삭제를 지원한다. Set, MultiSet 셋 또한 레드-블랙 트리를 사용한 자료구조이다. value 하나의 값만을 가지며 오름차순 정렬이 디폴트이며 중복을 허용하지 않는다. 셋은 고유한 값에 대한 정렬된 자료구조가 필요할 때 사..

오늘은 시뮬레이션 1문제와 정렬 1문제를 풀었다. 둘 다 그냥저냥 쉽게 풀었다. 자바는 인터페이스 전까지 정리를 다 했다. 확실히 다시 읽으면서 정리하니까 헷갈렸던 부분이 좀 잡혔다. 내일은 자바 공부를 끝내고 인터페이스까지 정리한 후에 아마 정렬 문제를 풀 것 같은데, 2~3문제 정도 풀 것 같다. 이번주 주말즘부터는 인프런 강의도 들어야 하고 문제풀이도 dp로 들어간다. 네트워킹 책도 사둔 게 있어서 좀 읽어야겠다.

1. 다형성 다형성이란 여러 가지 형태를 가질 수 있는 능력으로, 자바에서는 한 타입의 참조변수로 여러 타입의 객체를 참조할 수 있도록 하는 기술이다. 구체적으로 말하면, 조상클래스 타입의 참조변수로 자손클래스의 인스턴스를 참조할 수 있도록 하는 것이다. 예를 들어 Tv 클래스를 조상으로 하는 CaptionTv 클래스가 있다고 생각해 보자. 다형성을 통해 Tv 타입의 참조변수로 자손 인스턴스인 new CaptionTv를 참조할 수 있다. CaptionTv c = new CaptionTv(); Tv t = new CaptionTv(); c와 t는 어떤 차이가 있을까? c와 t 모두 CaptionTv 인스턴스를 담고 있지만 t로는 CaptionTv 인스턴스의 모든 멤버를 사용할 수 없다. Tv타입의 참조변수..

오늘은 시뮬레이션 문제를 2개 풀고 자바 공부도 하고 정렬 공부도 했다. 이것저것 많이 한 것 같긴 한데 집중력이 완전 엉망이었다. 연말 약속에 들떠서 공부가 안된다. 지금 아직 20일 남았는데 큰일이다. 처음 푼 시뮬레이션 문제는 생각보다 너무 쉬워서 테트로미노를 하나 더 풀었다. 테트로미노라는 블록의 모든 형태를 저장하면 바로 풀 수 있는 문제인데, 모든 형태를 저장하기가 생각보다 힘들었다. 백트래킹을 응용해서 풀었는데, 경로가 4인 길이를 찾으면서도 중간에 한 번 꺾는 형태의 길도 찾게끔 구현했다. 다음에도 쓸 일이 있을 것 같아서 잘 기억해 둬야겠다. 자바는 인터페이스 부분을 공부했는데 확실히 어려웠다. 굉장히 헷갈렸는데 다시 읽어보면서 정리하고 예제도 구현하고 하면 큰 도움이 될 것 같다. 정렬..

Merge Sort 먼저 구현부터 해보자. 재귀 형태로 구현했다. 함수 정의 void merge_sort(int start, int end) : start ~ end - 1까지 병합 정렬을 실행한다. base condition if(길이가 1) return; 재귀식 배열을 반으로 쪼개서 병합정렬을 한 후 merge 함수를 써서 병합하면 된다. merge 함수는 정렬된 두 배열을 병합하는 함수이다. 배열을 반으로 쪼개서 병합정렬을 한다는 건 귀납적 사고를 통해 재귀식을 구성했다고 생각하면 된다. 길이가 4인 배열을 병합정렬 할 수 있다고 가정하면 길이가 8인 배열은 길이가 4인 배열을 합치면 끝이다. 이런 느낌으로 구현해 보자. #include #include using namespace std; int ..

오늘은 구슬탈출 2 문제를 풀었다. 골드 2 문제라 조금 긴장하고 들어갔는데 확실히 어려웠다. 내가 재귀를 잘 못해서 재귀만 계속 풀었더니 이제 문제를 재귀로 많이 풀게 됐다. 재귀가 시간 복잡도상 손해를 볼 수 있어서 그렇게 좋은 습관은 아닌 것 같다. 구슬탈출 2 문제도 재귀로 풀었는데, 사실 재귀로 구현한 부분은 상당히 깔끔했다. 그런데 판을 기울이는 과정에서 어려움을 좀 겪었다. 판 기울이기 문제는 많이 풀어봤는데 공이 2개 존재하고 구멍까지 고려해야 해서 좀 어려웠다. 두 공을 독립적으로 다룬다고 생각하면 쉽게 풀 수 있는 부분이었는데 그 부분을 놓쳤다. 슬슬 시뮬레이션 문제는 그만 풀고 다음 단원으로 넘어갈 때가 된 것 같다. 이제 dp랑 이분 탐색 정도의 큰 산만 남았다. dp가 진짜 큰 산..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 예제 5 5 1 2 3 4 5 5 4 3 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 ans : 19 문제 분석부터 해보자. 테트로미노라는 블록을 보드에 넣는데, 블록이 들어가는 칸의 합이 가장 크게 되는 숫자를 찾으면 된다. 테트로미노는 총 5 종류고, 가장 먼저 떠오르는 방법은 모든 테트로미노를 하나하나 끼워 넣는 방법이다. 보드의 크기가 2500이고 블록 단 한 개만 넣으면 되므로 모든 테트로미노를 다 끼워보는 방법으로 구현해도 될 것 같다...