안녕하세요. 그래프 이론에서 functional graph는 생각보다 많이 다뤄지는 주제입니다. 이 사이트를 보셔도 좋을 듯 싶군요. 울프람 알파에도 정의가 되어 있습니다. 이 그래프에서 어떻게 사이클을 찾을까요? 예전에, scc (강한 연결 요소)를 모르던 시절에 풀었던 문제들이 몇 개 있었습니다. 그 문제들을 풀 때 써먹을 수 있는 흥미로운 것들은 2개 입니다. 여기서 노드 i와 노드 j가 같은 덩어리에 속해있다면 i에서 j로 갈 수 있는 방법이 있거나, j에서 i로 갈 수 있는 방법이 있다는 것을 의미합니다. 이 둘을 보이도록 하겠습니다. 상대적으로 보이기 쉬운 2번부터 보여봅시다. 그래프에서 cycle은 시작점 s가 있다고 해 봅시다. 여기서 출발해서 다른 노드들을 거쳐서, s로 도착하는 경로가 ..
백준 검색 결과
5002번째로 푼 문제는 이 문제였습니다. 문제 상황을 간단하게 요약하면 아래와 같습니다. 1순위가 같으면 2순위를 처리하는 것은 나중에 생각해 보도록 합시다. 우리가 원하는 것은 '탑승 비용', 문제에서 설명하는 route cost를 최소화 하는 방법부터 고민해 보겠습니다. 비행기 1이 도시1에서 3을 거쳐서 목적지인 7로 간다고 해 봅시다. 대충 1에서 7로 가는데 3을 경유한다고 보시면 됩니다. 이 경로를 선택하는 비용이 10이라고 해 보겠습니다. 문제에서 설명하는 것에 따르면 1에서 3으로 가는 탑승 비용, 3에서 7로 가는 탑승 비용, 1에서 7로 가는 탑승 비용이 10으로 같습니다. 이 세 경우는 경로 1을 선택해서 갈 수 있는 경우이기 때문입니다. 문제는, 비용 10을 어느 간선에 줄 것이냐..
약 5개월 전에, define 전처리문에 대해서 썼습니다. 이번 시간에는 조건부 컴파일을 할 때 많이 써먹는, #if와 #ifdef에 대한 글을 써보도록 하겠습니다. 당연하게도, 백준 사이트에서도 많이 볼 수 있는 코드이기도 합니다. 먼저 위 코드를 보겠습니다. 이상한 va_list라던지 va_start, vprintf, va_end가 나오지만, 여기에서는 중요하지 않습니다. 단지, 가변 인자를 처리하기 위해서 저런 것들을 썼다 정도만 보시면 되고요. 여기서 중요한 것은 13번째 줄의 #ifdef입니다. 이것은 무엇을 하는 것일까요? 위에 보니까 DEBUG라는 것이 정의가 되어 있지 않아요. 아무 결과도 나타나지 않았습니다. 반면에, 이 코드는 위에서 DEBUG라는 필드가 정의되어 있었습니다. 이 경우에..
귀납법은 이산 수학 시간에 들어보셨을 증명 방법입니다. 어떻게 쓰는지, 백준에 있는 문제를 풀어보도록 하겠습니다. 최근 USACO 실버에 나온 문제라고 하는데, 실버 같지 않습니다. 문제를 요약하면, 길이가 n인 순열이 주어집니다. 1부터 n까지의 수가 1번 등장합니다. 그리고 m개의 웜홀 정보가 (a, b, c)로 주어지는데, 너비가 c인 웜홀을 열면 a번째 원소와 b번째 원소를 바꿀 수 있다는 의미입니다. 어떻게 잘 배치해서 순열을 오름차순으로 정렬하려고 할 때, 연 웜홀들의 최소 너비를 최대화 시키는 문제입니다. 이걸 보면, 일단 이분 탐색임을 알 수 있는데, 정렬이 되어야 하는 조건이 상당히 어렵습니다. 어떻게 해 볼 것인가. 작은 집합부터 보면서, 큰 집합에서 성립하는지 보아야 겠습니다. 귀납법..
1년 6개월 전에 질문 글에 답변한 내용입니다. 그렇지만, java로 1325번 문제를 푸는 것과도 연관이 있으니, 잠깐 언급을 하도록 하겠습니다. 질문 글의 문제는, 많이 아시는 에라스토스 테네스 체의 구현체로 구현한 코드를 예제로 분석해 보겠습니다. 이 글의 흐름을 따라오기 위해서, 이 3가지만 쫓아오시면 충분합니다. (1) - (2)번은 링크의 Type of locality에 언급이 되어 있고, (3)은 spatical and temporal locality usage에 언급이 되어 있습니다. 그리고 그 주제의 2번째 단락에는, 해당 위치에 있는 데이터 값을 가지고 오면, 주변에 있는 것들도 cache에 같이 가져 온다는 언급이 되어 있습니다. 메모리의 계층도 같이 언급이 되어 있으니, 챙겨 보시면..
최근댓글