본문 바로가기

분류 전체보기159

다이나믹 프로그래밍 (Dynamic Programming) 동빈나 유튜브 참고 www.youtube.com/watch?v=FmXZG7D8nS4 다이나믹 프로그래밍 = 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 다이나믹 프로그래밍을 사용할 수 있는 조건! 큰 문제를 작은 문제로 나눌 수 있다. (분할-정복의 개념) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (핵심!!) 예시 : 피보나치 수열 f(n) = f(n-1) + f(n+1) 이미 계산한 결과를 배열에 저장하는 메모이제이션(Memoization)이 분할-정복 기법과 다른 점이다. 어떤 조건일 때 종료되는지도 알아둬야 함! #include int dp(int x){ //언제 끝나는지 명시해주는 역할 if(x==1) return 1; if(x==2) return 1; return .. 2020. 9. 25.
[Java/백준/BFS] 1697번: 숨바꼭질 문제 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 코드 visited[start]를 처음에 1로 준 이유는, start의 위치도 아래의 if문에서 visited[~]==0의 조건에 걸릴 수 있기 때문이다. 계속 저 f-1 >=0 을 >라고 해서 틀렸다고 떴었다..... import java.util.*; import java.io.*; public class Main { static int[] visited = new in.. 2020. 9. 24.
[Java/백준/BFS, DFS] 2644번: 촌수계산 문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS 코드 adjacent라는 ArrayList[] 배열을 만들어서 각 사람들의 부모-자식 관계 사람들을 추가해준다. BFS queue 안에 알아야 할 사람 중 한명(start)를 넣고 거기서부터 BFS로 검사해 나간다. visited[사람]에는 start로부터 몇칸씩 떨어져 있는지가 입력된다. queue에서 제일 처음 것을 빼냈을 때 이것이 start와 관계를 묻는 사람(end)이면 r.. 2020. 9. 21.
[Java/백준/BFS] 7576번, 7569번: 토마토 문제 (2차원 배열) www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 코드 백준 미로 탐색 문제와 비슷한듯 다르다. 토마토 문제는 익은 토마토로부터 검사를 시작하는데, 그 갯수를 알 수 없기 때문이다. 다행히 입력할 때부터 선언한 queue 안에 익은 토마토의 좌표를 넣어주면 된다는 것을 알게 되었다.^__^ bfs 함수 queue 안에는 익은 토마토의 좌표가 들어있다. 검사할 토마토의 사방을 보았을 때, >> 안익은 토마토일 것 && 지나.. 2020. 9. 21.
[Java/백준/BFS] 2178번: 미로 탐색 문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 코드 최단거리는 BFS로 푸는 것이 좋다. 한 노드에서 연결된 각 노드들을 동시에 검사하기 때문이다. 이 문제에서의 visited는 boolean[][]이 아닌 int[][]이다. (지나갔는지 체크하는 용도가 아니라 몇칸 옮겼는지 기록하는 역할) (0,0)에서 시작해 (n-1,m-1)까지 BFS로 검사하다 제일 먼저 (n-1,m-1)에 도착하는 경로가 있으면 visited[n-1][m-1]에 입력된다. 다른 경로로 visited[n-1].. 2020. 9. 21.
[Java/백준/DFS] 1012번: 유기농 배추 문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 코드 단지번호 붙이기와 비슷하게 풀었다 아이고 속시원해 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ static int[] dx = {0,0,-1,1}; s.. 2020. 9. 19.
인터럽트(Interrupt) 인터럽트란? 프로그램을 실행하는 도중에 예기치 않은 상황이 발생할 경우 현재 실행 중인 작업을 즉시 중단하고, 발생된 상황을 우선 처리한 후 실행중이던 작업으로 복귀하여 계속 처리하는 것이다. 지금 수행 중인 일보다 더 중요한 일(입출력, 우산순위연산 등)이 발생하면 그 일을 먼저 처리하고 나서 하던 일을 계속해야 한다. 외부 인터럽트 → CPU의 하드웨어 신호에 의해 발생 입출력 장치, 타이밍 장치, 전원 등 외부적 요인으로 발생 ex. 전원 이상, 기계 착오, 외부 신호, 입출력 내부 인터럽트 → CPU의 하드웨어 신호에 의해 발생 Trap이라고 부르며, 잘못된 명령이나 데이터를 사용할 때 발생 ex. 0으로 나누기 발생, 오버플로우, 명령어 잘못 사용(exception) 소프트웨어 인터럽트 → 명령.. 2020. 9. 17.
[Java/백준/DFS와 BFS] 2667 - 단지번호붙이기 문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 코드 DFS가 재귀를 써도 되기 때문에 자주 사용하게 된다. 입력받은 2차원 배열은 village에 저장한다. dx, dy를 사용해서 상하좌우 좌표를 정해준다. 이중 for문을 돌면서 1인 좌표를 발견하면 dfs함수를 호출한다. 굳이 visited를 사용하지 않아도 dfs가 시작되면 village의 해당 좌표 값을 0으로 바꾸어 준다. (그럼 다음에 쓰루함) 해당 좌표에서 dx, dy로 상하좌우를 탐색하면.. 2020. 9. 17.
[Java/백준/DFS와 BFS] 2606 - 바이러스 문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 코드 그냥 BFS 이용했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class Main{ static ArrayList[] adjacent.. 2020. 9. 12.

티스토리툴바