2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 예제 5 6 9 5 7 4 ans : 0 0 2 2 4 문제를 풀 때 사용할 수 있는 조건들을 생각해 보자. 1. 첫 번째 탑은 무조건 수신할 탑이 없다. 2. 두 번째 이후의 탑은 자신보다 큰 탑 중 왼쪽 방향으로 가장 가까운 탑이 수신한다. 이 조건을 보고 스택을 떠올렸다. 스택을 메인 알고리즘으로 사용한 이유는 가장 최근에 들어온 데이터 중 조건에 맞는 데이터를 빼야 하는 조건부 후입선출 문제이기 때문이다. 처음에는 자신보다 높은 탑을 스택에서 고르기 위..

24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 예제 5 7 4 5 1 3 2 ans : 3 -------------------- 5 13 4 5 1 3 2 ans : -1 병합정렬만 구하면 풀리는 문제다. K 번째 저장되는 수라는 말이 조금 헷갈리는데 간단하게 주어진 퍼수도코드대로 구현했을 때 병합 결과를 저장하는 부분에서 K 번째 저장되는 수를 구하면 된다. 병합 정렬을 공부하고 특징, 장단점을 숙지하면서 구현해 보기 좋은 문제이다. /** 정렬 24060 알..

TIL을 쓰는 걸 잊고 있었다. 굉장히 아쉬운 일이지만 이미 지난걸 다시 쓰긴 싫다. 오늘은 set, map 컨테이너 공부 후 set, map, 우선순위 큐와 관련된 문제를 하나씩 풀었다. 정렬 문제도 하나 풀었다. 정렬 문제가 제일 어려웠던 것 같다. 확통을 오랜만에 다뤄서 기억이 잘 안 났다. 정렬 문제들은 꽤 많이 풀어서 이제 다른 주제로 넘어가 볼까 한다. 정렬과 해시테이블, 기본 자료구조 문제는 꽤 다뤘으니 마지막 복습 겸 블로그에 정리하고 C++ 관련 컨테이너도 복습하는 식으로 마무리한다. 그리고 검색트리와 문자열로 넘어가야겠다. 문자열이 정말 취약한데 코테에서 여기저기 많이 나와서 이번 기회에 진짜 꼭 잡는다.

int 자료형으로 표현 가능한 숫자는 210,000,000(21억) 언저리까지이다. 그 이상의 숫자는 오버플로우가 발생하므로 long long 자료형을 사용해야 한다. 내가 코딩하다가 숫자가 21억이 넘어갈지 안 갈지 어떻게 알아??라는 의문이 들 수 있다. 1. 먼저 알고리즘을 생각해본다. 사람마다 다르지만 나는 퍼수도코드로 짜고 시작한다. 2. 시간복잡도를 생각해본다. O(N*M) 이런 식으로 나온다면 N과 M의 최댓값을 기준으로 곱해서 생각하면 된다. 얼추 21억이 넘겠다 싶으면 안전하게 long long으로 짜는 편이 좋다. 3. long long으로 코드를 바꿀 때 콤팩트하게 확실하게 안 바꿔도 되는 자료형을 제외하고는 다 바꾸는 편이 좋다. 연산 중 자동 형변환이 일어날 수 있다. 시간초과도 ..