💻 Problem문제 보러 가기 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 ..

💻 Problem문제 보러 가기 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못 가는..

💻 Problem문제 보러 가기  N개의 돌이 일렬로 나열되어 있다. N개의 돌에는 왼쪽부터 차례대로 수 A1A2...Ai...AN로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.항상 오른쪽으로만 이동할 수 있다. i번째 돌에서 j(i돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자. 💡 Approach이중반복문을 통해 i번째 돌에서 j번째 돌로 이동할 때 드는 힘을 계산한다.힘이 K 이하이면 이동할 수 있다.이 정보를 바탕으로 인접 리스트를 만든다. 만든 인접 리스트를 이용해 dfs를 돌려 0번째 돌에서 N-1번째 돌까지 이동할 수 있는지 확인한다. ✏️ Solu..

💻 Problem문제 보러 가기  루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.  💡 Approach사실 처음에는 복잡하게 생각해서 코드 짜기 헷갈렸다...2번부터 n번까지의 노드를 출력하려면 2 ~ n 반복문으로 탐색 함수를 돌려서 각 결과를 출력하는 건 줄 알았다.그래서 연결된 노드 중에 루트 노드가 있으면 루트 노드가 부모 노드이고.. 연결된 노드가 하나이면 연결된 노드가 부모 노드이고.. ..

💻 Problem문제 보러 가기 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구와 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라. 💡 Approach처음에 이 문제를 봤을 때 간선에 가중치가 있으니 다익스트라 문제 아닌가? 싶었다.하지만 다익스트라는 최단 거리를 찾는 알..

💻 Problem문제 보러 가기  방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.  💡 Approach간선 정보(간선의 양 끝점)를 입력받고 있기 때문에 간선 정보를 가지고 graph를 만들어야 한다.만든 그래프를 바탕으로 정점 1부터 그래프 탐색을 시작한다. 만약 연결 요소가 하나인 그래프라면 첫 탐색에서 모든 정점에 방문 처리가 됐을 것이다.하지만 연결 요소가 2 이상인 그래프라면 첫 탐색 이후에 방문 처리가 되지 않은 정점이 있을 것이다.그렇게 방문 처리 되지 않은 정점을 찾아서 해당 정점을 기준으로 그래프 탐색을 하는 것을 반복하여 그래프 탐색을 몇 번했는지 세면 된다. 아래는 연결 요소에 대한 이해를 돕기 위한 필기이..