본문 바로가기

전체 글

 (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 분야에서 가장 중요하게 취급되는 문제"라고 언급하고 있다. 이 문제를 해결함에 있어 깨달아야 하는 몇가지 중요한 점 중 하나는 여행을 어디에서 시작해도 상관없다는 점이다. 왜냐하면 항상 시작한 도시로 돌아와야 하기 때문..

티스토리툴바