본문 바로가기

전체 글

 (45)
백준 - 2178 미로탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 본 문제의 요구사항은 출발지점에서 도착지점으로 가는 최소 경로를 찾는 문제이며 BFS 방식으로 풀면 쉽게 해결될 수있다. 알고리즘은 아래와 같다 1. 큐를 만들고 출발지점값을 1로 세팅 ( 첫칸 방문 ) 2. 갈수 있는 인접 지점을 선택 해당 값을 이전값 +1 로 세팅 한다. 3. 2단계에서 선택된 각 인접 지점들에 대해서 2단계를 반복한다. 4. 선택된 지점이 도착된 값이 되면 그점의 값이 최소 경로 값이 된다. 이를 코드로 구현하면 아래와..
백준 1260 - DFS 와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 본 문제의 요구사항은 대표적인 그래프의 탐색 방법인 깊이우선 탐색 ( DFS ) 과 너비 우선 탐색( BFS ) 을 구현하여 방문 노드를 순서대로 출력하는 것이다. 단 방문할수 있는 정점이 여러개인 경우 오름차순으로 방문해야 한다. DFS 와 BFS 의 정의는 아래 위키폐이지에 잘 설명되어있다. DFS : https://ko.wikipedia.org/wiki/..
백준 1149 - RGB 거리 본문제의 요구사항은 다음과 같다. 거리에 N 개의 집을 색칠해야 하는데 R,G,B 중 하나의 색으로 칠해야 한다. 단 모든 연속되는 집들은 서로 다른 색으로 색칠되어야 한다. 각 집별로 색깔별로 칠하는비용이 주어졌을때 가장 최소 비용이 드는 경우의 비용이 얼마인지 구해야 한다. 집이 최대 1000 개 이므로 단순히 완전 탐색 ( 모든 경우를 일일이 다 따져보는것 ) 으로는 해를 구할 수 없다. 적절한 점화식을 유도하고 재귀호출을 통해 계산하되 중복 계산이 발생하지 않도록 메모제이션을 하는 방식으로 답을 구할수 있다. 1번째부터 N 번 째까지 최소 비용을 구하는 함수를 F(1,N) 이라고 정의한다면 다음과 같이 표현할 수 있다. F(1,N) = min ( R[1] + F(2,N) , G[1] + F(2,N..
백준 - 2579 계단 오르기 본 문제의 요구사항은 아래와 같다. 주어진 계단이 있고 각 계단별로 점수가 있다. 계단을 오르는 규칙은 다음과 같다 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 2. 연속된 3개의 계단을 밟아서는 안된다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 이러한 규칙들을 준수하면서 밟을수 있는 경우의 수를 따져서 가장 높은 점수를 출력해야 한다. 본문제를 풀기위해서 완전 탐색을 이용할수 없다. 완전탐색은 일반적으로 시간복잡도가 O(2^N) 이고 계단이 최대 300 개이므로 시간초과가 발생한다. 따라서 DFS 와 메모제이션 기법으로 중복 계산을 없애 계산 시간을 단축할 수 있다. 맨 마지막 계단을 반드시 밟아야 하기 때문에 출발은 제일 마지막 계단부터 내려오면서 합을 구한다. 함수 F(Ni..
백준 1003 - 피보나치 함수 본 문제의 요구사항은 다음과 같다 피보나치 수를 구하는 방법중의 하나로 재귀호출 방법을 이용할 수 있는데 기저조건 즉 재귀함수의 탈출조건이 반드시 있어야 한다. 입력되는 n 이 0 또는 1 인 경우 0 또는 1을 반환해야 한다. 이때 임의의 숫자 N 의 피보나치 수를 구하기 위해서는 0 또는 1 에 대한 피보나치수 함수 호출이 몇번 발생하는 지 계산해야 한다. 단 N 은 최대 40이다. 본 문제를 풀기위해서 피보나치 수를 구하는 함수와 동일하게 fibonacci(N) = fibonacci(N-1) + fibonacci(N-2) 라는 수식을 이용할 수있다. 예를 들어 10 에 대한 fibonacci(0) , fibonacci(1) 호출회수는 9에 대한 호출 회수 와 8 에 대한 호출회수 의 합으로 계산될수..
백준 11729 - 하노이의 탑 이동순서 본 문제는 입력으로 주어지는 n 개의 원판을 이동시키는 회수와 방법을 표시해야 하는 문제이며 이동회수가 회수가 최소가 되는 방법은 단 한가지 방법 뿐입니다. 재귀호출을 통해 풀이할수있는 가장 기본적인 형태의 문제입니다. 재귀호출은 기저조건 즉 재귀호출을 탈출할수 있는 조건 을 가장 먼저 정의해야 합니다. 그렇지 않으면 문제 풀이 중 무한 루프에 빠지다가 스텍오버플로우 로 프로그램이 죽을 것 입니다. 본 문제의 기저조건은 옮길 스톤이 1개 일 때 입니다. 출발지에서 목적으로 1회 이동 하도록 구현하면 됩니다. 스톤이 한개 이상일 때는 제일 바닥의 돌과 그위의 돌들로 분류해서 생각할 수 있고 아래와 같이 세단계를 거쳐서 이동시킵니다. step1) 1~N-1 의 스톤을 중간 막대기로 이동시킵니다. step2)..
백준 2309 - 일곱 난장이 본 문제는 전형적인 모든 조합을 찾는 완전 탐색 문제 입니다. 총 9명의 난장이 중 진짜 일곱 난장이는 누구인지 찾아내는 문제인데 그들의 키의 총합이 100 이라는 힌트를 통해 완전 탐색을 수행하면 쉽게 정답을 찾을 수 있습니다. 다만 코드의 재사용 성을 위해 완전 탐색을 수행하는 클래스를 만들겠습니다. 그리고 몇가지 입력을 통해 다양한 종류의 조합 완전 탐색을 수행할 수 있도록 구현 합니다. 구체적인 코드는 아래와 같습니다. #include #include #include #include using namespace std; class Combination { typedef function FUNC_TYPE; public: Combination(int nrData, vector &data, FUNC_T..
오르트 구름 ( Oort Cloud ) 오르트 구름(Oort Cloud) 이란 무엇입니까? 오르트 구름은 명왕성과 카이퍼 벨트 외곽에 위치해 있습니다. 태양계의 행성들은 편평한 평면에서 궤도를 돌고 있지만, 오르트 구름은 태양, 행성 및 카이퍼 벨트 를 둘러싸고있는 거대한 구형 껍질 같은 형태로 존재합니다. 오르트 구름은 얼음으로 구성된 혜성 같은 물체로 만들어진 태양계 주위의 크고 두꺼운 거품과 같은 형태로 존재합니다. 오르트 구름의 얼음 덩어리는 산만큼 클 수 있으며 때로는 그것보다 더 클 수도 있습니다. 규모와 거리 오르트 구름은 태양계에서 가장 먼 지역이며, 태양에서 가장 가까운 별(알파 센타우리) 까지 1/4에서 절반 정도의 거리까지 위치합니다. 오르트 구름 까지의 거리를 이해하기위해서 마일이나 킬로미터 단위 대신 천문 단위 중 하나..

티스토리툴바