본문 바로가기

전체 글

 (45)
[백준 2178 : JAVA] 미로탐색 / DFS BFS 특징 개요 DFS Stack 혹은 재귀함수(Recursion)으로 구현된다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) BFS Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) BFS는 다음의 경우 효과적으로 풀이할 수 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1인 경우 3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.) 이 문제는 1번째 조건과 최단거리 조건이 만족 때문에 DFS로 풀이하면 시간초과가 나게된다... DFS로 ..
[백준 1012 : JAVA] 유기농 배추 / DFS 개요 기본적인 DFS, BFS를 통해 단절된 구역의 개수를 구하는 문제이다. 이 문제는 다음 문제와 비슷하며 이 문제를 먼저 풀고 다음 문제를 풀어보길 추천한다. 이 문제에서 약간 추가된 부분이 있는 문제이다. 2020/01/30 - [알고리즘/백준] - [백준 2667 : JAVA] 단지번호붙이기 / DFS [백준 2667 : JAVA] 단지번호붙이기 / DFS 개요 dfs를 이용하여 을 의 형태의 배열로 만든다. 단절되어 있는 단지들의 집의 개수를 구하면 된다. dfs를 통해 한 노드에서 갈 수 있는 노드 모두를 탐색하면서 풀이한다. 문제 과 같.. dragon-h.tistory.com 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 ..
[백준 2667 : JAVA] 단지번호붙이기 / DFS 개요 dfs를 이용하여 을 의 형태의 배열로 만든다. 단절되어 있는 단지들의 집의 개수를 구하면 된다. dfs를 통해 한 노드에서 갈 수 있는 노드 모두를 탐색하면서 풀이한다. 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 풀이 DFS를 이용한다. dfs(int x..
[백준 2606 : JAVA] 바이러스 / BFS 개요 이 문제는 dfs와 bfs 알고리즘 둘 다 풀이가 가능하다. 두 알고리즘에 대해 기본을 익히고 싶다면 아래의 문제를 먼저 푸는 것을 추천한다. 2020/01/30 - [알고리즘/백준] - [백준 1260 : JAVA] DFS와 BFS / DFS, BFS [백준 1260 : JAVA] DFS와 BFS / DFS, BFS 개요 dfs와 bfs는 둘타 탐색을 하는데 사용된다. dfs는 깊이 우선 탐색으로 스택 또는 재귀함수를 구현한다. bfs는 너비 우선 탐색으로 큐로 구현한다. (예전에 bfs를 처음 배울 때 물에 돌을 떨어 뜨렸을 때 파장.. dragon-h.tistory.com 갈 수 있는 모든 노드의 개수를 구하면 풀이가 가능하다. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한..
[백준 1260 : JAVA] DFS와 BFS / DFS, BFS 개요 dfs와 bfs는 둘타 탐색을 하는데 사용된다. dfs는 깊이 우선 탐색으로 스택 또는 재귀함수를 구현한다. bfs는 너비 우선 탐색으로 큐로 구현한다. (예전에 bfs를 처음 배울 때 물에 돌을 떨어 뜨렸을 때 파장과 같이 점차적으로 모든 방향을 동시에 탐색하고 나간다고 배웠는데 아직도 기억에 남는다...) 뭐 삼성 코테에서 주를 이루고 있는 문제라고 할 수 있다. 물론 난이도는 이문제보다는 높은 문제들이 많다.. 이 문제는 dfs, bfs 두 가지 방식으로 풀 수 있다는 것을 보여주고 있다. 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 ..
[백준 2293 : JAVA] 동전1 / Dynamic Programming 개요 dp 문제는 이전의 구한 값을 통해 현재 원하는 값을 도출하는 방식이다. 이 문제에서는 중복만 제거한다면 풀이가 가능하다. 또한, 만들고 싶은 금액을 기준으로 한다. 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 풀이 dp[] 배열을 선언한다. dp[i] = j 라고 하면, 다음과 같다. i → 금액 j → i원을 만드는데 가능한 경우의 수 dp[i] = dp[i] + dp[i - coin]이다. 문제와 같은 입력이 주어졌을 때 1원 짜리 동전으로 1원 부터 10원..
[백준 7579 : JAVA] 앱 / Dynamic Programming 개요 전형적인 dp문제로 dp배열을 선언하여 풀이할 수 있다. 처음에 문제를 접근 할 때 메모리값을 dp[][] 배열의 인덱스로 잡으면 메모리초과가 난다는 것을 인지하고 비용을 기준으로 잡고 문제에 접근할 것이다. 문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스..
[백준 10942 : JAVA] 펠린드롬? / Dynamic Programming 개요 dp를 이용해서 풀이할 수 있다. 1 2 1 3 1 2 1 수열이 주어졌을 때 dp[][]를 선언하고 dp[i][j]에서 i → 검사하고 싶은 시작 인덱스 j → 검사하고 싶은 끝 인덱스 라고 생각하고 접근한다. dp문제는 이전에 구한 dp값을 이용해서 현재 원하는 dp값을 구하는 방식이다. 나는 처음에 문제에 접근할 때 시작 점과 끝을 기준으로 dp값을 구하였다. 하지만 이 문제는 길이가 1일 때 펠린드롬인지, 2일 때 펠린드롬인지 ... 을 통해 dp값을 구하면 쉽게 구할 수 있다. 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E..

티스토리툴바