본문 바로가기

분류 전체보기

 (84)
자바스크립트 스코프 ( scope ), 전역 객체 C++ 에서 보면 using namespace std; 라고 자주 보인다. std 네임스페이스를 쓰겠다는 뜻이다. 네임스페이스는 여러가지 정보가 저장된 공간이라고 봐야 한다. 우리가 도서관에 있다면 우리는 도서관 namespace 에 있는 것이고, 그 공간안의 정보를 활용할 수 있다. 물론 핸드폰, 노트북 등을 통해서 인터넷 검색을 할 수도 있다. 그렇다면 그것은 일종의 global namespace 일 것이다. 모든 정보를 global 에 배치해두고 써도 되겠지만, 아래와 같이 문제가 많다. 하나의 도서관에 이 세상 모든 책을 보관할 수는 없다. 공간이 부족하기 때문이다. 또한 사람들이 필요로 하지 않는 책도 많을 것이다. 하나의 책을 여러 사람이 필요로 할 때도 문제가 된다. 그 외에도 여러가지 문제..
백준 1700 멀티탭 스케쥴링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 다행히 이 문제는 아주 어려운 그리디 문제는 아니다. 그리디 문제가 어려우면 정말 어려울 때가 있다. 그리디 문제의 어려운 점은 증명이다. 가끔 어떠한 직관에 의해 풀이가 떠오르고, 그대로 구현했을 때 정답인 경우가 있다. 하지만 그 풀이의 증명이 쉽지 않다. 이 문제의 그 '직관'은 가장 마지막에 다시 사용할 기기를 가장 먼저 뺀다는 것이다. (물론 한번 사용한 기기를 다시 쓰는 일이 없다면 현..
백준 2463 비용 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸 www.acmicpc.net 좋은 문제이다. 가장 좋은 문제 몇 손가락 안에 들 정도로. 발상의 전환이 필요하고, 유니온 파인드의 의미에 대한 이해가 필요하다. (최소 스패닝 트리 알고리즘 안에 유니온 파인드가 포함된다.) 유니온 파인드에서 union 으로 연결된 정점들은 일종의 그룹을 만들게 된다. 자연히 그들은 루트(대표)를 갖는다. 그리고 그 루트 정점의 식별자가 해당 그룹의 식별자이..
백준 1102 발전소 https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 이 문제는 백준 2098 외판원 순회와 비슷하면서 다르다. 가장 큰 차이점은 외판원 순회처럼 i도시에서 j도시로 가는게 아니라, 켜져있는 어떤 발전소든지 꺼진 발전소를 재생시킬 수 있는 것이다. 즉 외판원 순회에서 방문한 도시는 다시 못가지만, 이 문제에서는 방문한 도시에서 다시 다른 도시로 또 갈 수 있는 것이다. 굳이 억지를 들자면, 다시 돌아가는 비용은 0인 상태이다. 그러면 코드에서 나타나는 가장 큰 ..
백준 2098 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 대단히 중요한 문제 중 하나라고 생각한다. 비트마스킹 + 재귀 + DP 가 어우러진 좋은 문제이다. 문제에서도 "computer science 분야에서 가장 중요하게 취급되는 문제"라고 언급하고 있다. 이 문제를 해결함에 있어 깨달아야 하는 몇가지 중요한 점 중 하나는 여행을 어디에서 시작해도 상관없다는 점이다. 왜냐하면 항상 시작한 도시로 돌아와야 하기 때문..
모노톤 스택 / 큐 / 덱 monotone 이라고 한다면 증가하고 있거나 감소하는 등의 (mono- ) 일정한 경향을 보임을 뜻한다. 그러한 형태를 띠는 스택, 큐, 덱인 것이다. 모노톤이라고 해서 한 방향을 띠긴 하지만, 모든 데이터를 담는 것은 아니다. 필요가 없어진 데이터는 버릴 수 있어야 하고, 필요가 없는 데이터는 기록조차 하지 않는다. 하지만 보통 이 방법을 통해 시간 복잡도를 O(N)으로 줄일 수 있어서 매우 강력하다고 생각한다. 다양한 활용처가 있겠지만, 이 포스트에서는 특정 범위내의 최대 / 최소를 구하는 방법에 대해 알아보고자 한다. 보통 최소값, 최대값 등을 구하기 위해 정렬을 한다. 정렬에도 다양한 방법이 있다. 하지만 정렬은 모든 데이터가 주어졌을 때 사용 가능하다. 더 이상 생성, 수정, 삭제 등의 연산이..
백준 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 이 문제는 우선순위 큐로 해결할 수도 있지만, 모노톤 덱을 이용하면 더 빠르다. 우선순위 큐를 활용하려 할 경우, 데이터가 들어왔을 때 우선순위 큐에 담고, 최솟값 찾을 때 이미 범위를 벗어났는지 여부만 확인해주면 된다. 모노톤 덱을 사용한다면, 크기가 증가하는 수열 형태로 덱을 만들어주면 된다. 차근 차근 오른쪽으로 넣어준다. 범위가 벗어났다면 왼쪽에서 버려주고,..
백준 1185 유럽여행 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 위 문제는 다양한 경우의 수가 있을 것 같지만, 문제에 걸린 제한을 통해 '자동'으로 코너 케이스가 다 사라졌다고 생각한다. 증명할 수만 있으면 자신 있게 코드를 제출할 수 있다. 가장 중요한 조건은 N-1개의 길만 남겨야한다는 것이다. 이를 통해 모든 정점들이 빠짐없이 연결되는 트리구조를 갖게 된다는 것을 알 수 있다. 사이클이 없다는 것이다. 여기서 최소 ..

티스토리툴바