Toolofv 님의 블로그

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 문제해결..

부분의 합은 전체가 아니다. 전체가 부분을 결정한다.    수학은 과학을 서술하는 매우 정확한 언어이지만, 거기에는 이미 합의되어 있는 많은 부분들이 있다.이 것을 자연 및 현실에 적용할 때, 이미 전제되어있는 부분들을 살피지 않아 엔트로피를 무시하고 환원주의에 빠지기도 한다. 라디오나 컴퓨터를 분해한 후, 부품의 집합만 갖고 있다고 작동이 되지는 않는다.부품의 집합에 더해 부품조립의 질서가 필요하다. 여기에는 인간의 관측과 예상과는 다른 비용이 생긴다. 예를 들면, 조립하는 인간의 노동력이다.  세상 만사 모든 것에는 묶어주는 질서의 비용이 있다. 하지만 사실 이 것은 자연을 관측대상으로 하여 역추적하는 인간의 방법상의 순서와 관점일 뿐,  실제 존재하는 자연으로는 그 반대다. 엔트로피란 질서해체의 에..

문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.사람들이 서 있는 순서대로 입력이 주어진다.출력서로 볼 수 있는 쌍의 수를 출력한다.  문제해결방법- 서칭 참고 이 문제는..

문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는..

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.  문제 해결 방법 - (서칭으로 참고후 해결) 이해는 되는데 떠올리기는 어려운 듯;;  1. 1원의 경우 1+1+1-> 1씩 계속 더해나갈 수 밖에 없기 때문에 dp에 1..

문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.  와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.추들의 무게와 확인할 구슬들의 무게가 입력되었..

문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.  지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.  입력첫..

감자, 고구마의 보급과 이중의 역설    신대륙발견 이후 감자, 고구마, 옥수수 등이 전 지구에 보급되는 것은 필연적인 방향이었다.감자는 춥고, 거친 환경에서도 잘자라며 토지 당 생산력이 매우 높다. 고구마 또한 마찬가지.가지과에 속하는 덩이줄기 작물이며, 남아메리카 페루와 에콰도르 등 안데스 산맥 일대가 원산지라고 한다. 감자는 보관이 쉽지 않아, 세금으로 낼 수 있는 품목이 아니었으며, 재배기간도 짧기 때문에 정기적으로 찾아오는 기근 때마다 소중한 먹거리가 되었다. 1847년 아일랜드 대기근은 당시 영국이 밀, 옥수수 등 작물을 가혹하게 수탈(?)하는 가운데, 아일랜드인들이 주식으로 삼던 감자의 '역병'으로 인해 벌어졌다. 무려 100만 이상의 사람이 감자의 전멸로 인해 굶어죽었다고 한다. 이후 18..