관광이 블로그

안녕하세요 감자코딩에 감자개발자 입니다. 벌써 일요일이 끝나고 월요일이네요. 저는 이번에 공부해볼 강의는 알고리즘중에 꽃이라고 할 수 있는 Dynamic Programming(동적계획법)에 대해서 공부하겠습니다. 1. 동적계획법이란 무엇인가? 간단히 말해서 큰문제를 작은문제로 나누어서 푸는 기법이라고 할 수 있습니다.=(유사) 분할정복방법과 비슷합니다. 2. 동적 계획법의 대표적인 예이항계수(nCr)의 계산이라고 할 수 있습니다. 3. 메모이제이션(memoization) 이란? 동적계획법에서는 중복을 막기위해서 저장된 값을 배열에 저장한 뒤, 다음 계산이 필요할때는 저장된 값을 불러와서 중복을 없애면 함수호출이 줄어들게 됩니다. 그러면, 시간복잡도도 훨씬 줄어들게 됩니다. 밑에 예제는 피보나치 수열에 관..

/* 단지번호붙이기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 19045 7136 5006 38.328% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N..

안녕하세요 감자 코딩에 감자개발자입니다. 이번에 살펴볼 문제는 DFS와 BFS의 대표적인 문제인 1260번 문제입니다. 문제 링크 https://www.acmicpc.net/problem/1260 /* 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 ..

안녕하세요 감자코딩에 감자개발자입니다. 이번에는 살펴볼 알고리즘 개념은 바로 "DFS(Depth First Search)" 입니다. * DFS(Depth First Search) 알고리즘 1. 깊이우선탐색이란 트리 및 그래프 등을 탐색하는 알고리즘이다. 2. 특정 노드를 출발하여 깊게 들어 갈 수 있을때 까지 들어가고 들어 갈 곳이 없다면 다시 나오는 알고리즘이다. 3. 깊게 들어간다해서 깊이 우선 탐색, 스택을 이용하여 구현한다.(재귀를 많이 사용함) * DFS탐색순서 DFS의 탐색순서를 보면 깊이 순서에따라서 방문하는 것이 달라지는것을 볼 수 있습니다. 그림에서 주어진 순서대로 탐색을 하게 되는것을 알고 계시면 될것같습니다. * DFS 알고리즘 구현 로직// dfs callvoid dfs(int nu..

안녕하세요 감자코딩에 감자개발자 입니다. 이번에는 제가 DFS공부하기에 앞서, Recursive call(재귀적 함수 호출)에 대해서 알아보겠습니다. 가장 기본적인 예제로 돌아가는 Recursive에 대한 예를 하나 설명하겠습니다. // // recursive_call_exam.cpp // Algorigm_Study // // Created by kgh on 2018. 8. 6.. // Copyright © 2018년 kgh. All rights reserved. // #include #include using namespace std; int Recursive(int num){ if(num == 1 ){ return 1; }else{ return num + Recursive(num - 1); } } i..

/* 숨바꼭질 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 35272 9761 6127 24.946% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정..

안녕하세요 감자코딩에 감자개발자 입니다.이번에 살펴볼 내용은 백준알고리즘에 2178번 미로 문제입니다. 문제 링크https://www.acmicpc.net/problem/2178 /* 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2≤N, ..

안녕하세요. 감자코딩에 감자 입니다. 이번에는 살펴볼것은 C++의 STL의 종류인 Pair에 대해 살펴보도록 하겠습니다. * Pair STL 컨테이너의 한 종류인 Pair은 두개의 변수를 저장할 수 있는 구조입니다.이것을 queue 자료구조의 형태인 Pair로 사용도 할 수 있는데요, BFS 를 구현하다보니 나오는 내용이라 함께 정리하겠습니다. 1. 2차원 배열의 인덱스 2. 이차원 좌표평면에서의 좌표3. 정점번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야되는 경우 (BFS 미로 문제) 단독으로 pair를 사용하기 위해서는 #include 를 해주어야합니다. 하지만, Queue의 속성으로 쓰일때는 상관없다. 예) // pair q; // Pair 선언 queue q; pair r = make_pa..

* 1주차 알고리즘 정리 안녕하세요 감자입니다. 이제 알고리즘정리를 시작하려고 합니다. 오늘알아볼 알고리즘의 종류중 하나인 BFS를 살펴볼것인데요, 많이 쓰이기도하고 중요한 알고리즘인 만큼 정리시작해보겠습니다. 1. BFS(Breadth First Search)는 그래프전체를 탐색하는 알고리즘의 방법중 하나이다.그래프 전체를 탐색하는 방법은 BFS,DFS가 있다.BFS(Breadth First Search)는 그래프 전체를 탐색,인접한 노드들을 차례대로 방문한다.동심원의 형태로 이루어져서 점차 하나씩 모든 노드들을 방문하게 된다. BFS에서 가장 중요한 것은 각 노드에 대해서 최단 경로의 길이를 구할 수 있다는것이다. 이를 구현하기 위해서는 C++ STL Queue 방법을 사용하게 될것이다. 위의 그림대..