알고리즘/백준 문제
-
[백준] 11003 최솟값 찾기알고리즘/백준 문제 2020. 12. 25. 16:32
📘 풀이한 문제 백준 11103 최솟값 찾기 ⭐ 문제에서 주로 사용한 알고리즘 슬라이딩 윈도우 📜 대략적인 코드 설명 첫줄에 입력 숫자의 개수(N)와 인도우 크기(L)를 입력받습니다. 둘째 줄에 숫자를 입력받습니다. deque에는 숫자의 인덱스를 저장합니다. 반복문 (0~N) i번째 deque 마지막값이 입력숫자보다 큰 것을 모두 제거합니다. 제거가 끝나고, deque의 맨 앞숫자가 윈도우 안에 포함되는지 확인하고 벗어나면 지웁니다. 맨 앞 숫자를 정답 문자열에 추가합니다. 메모 컴퓨터네트워크 시간에 배운 적이 있는데, 다시는 보지말자는 마음으로 잊어버렸다. 그리고 이렇게 백준에서 만날줄 몰랐다. 다시 찾아서 정리해봐야겠다. import java.io.*; import java.util.*; public..
-
1012 유기농 배추알고리즘/백준 문제 2020. 5. 16. 14:31
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 단지번호붙이기 문제의 난이도하향 버전이라고 볼 수 있겠다. 똑같은 방법으로 푸는데, 단지번호붙이기는 단지별로 아파트 개수를 세어야 했지만, 이 문제는 그럴 필요 없이 벌레의 개수(==단지의 개수)만 구하면 된다. 이중 for문을 돌면서 배추가 심어져있고 방문한 적 없는 위치인지 확인한다. 조건을 만족하면 카운트(필요한 벌레의 수)를 1 증가 BFS 탐색 카운트 값을 출력 그리고 이 전체 과정을 테스트케이스..
-
1679 숨바꼭질알고리즘/백준 문제 2020. 5. 16. 13:43
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 이 문제 역시 최소시간(최단거리)를 구하는 문제이기 때문에 BFS를 이용해서 풀었다. 큐에 들어갈 다음 경로는 문제에 나와 있듯이 3가지가 있다. x+1 x-1 x*2 이전 BFS문제들과 같은 방식인데, 다른 문제에서 동서남북으로 움직이던 것을 이 문제에서는 위의 3 가지 경우로 움직이면 되고 일직선 상의 경로니까 1차원 배열을 사용했다. 때문에 오히려 쉬웠다. 아! 그..
-
7576 토마토알고리즘/백준 문제 2020. 5. 16. 00:16
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 기본 BFS 문제와 달라진 점은 출발점이 0,0이 아니면서 동시에 탐색을 해야하는 점 이전에는 출발점을 이중 for문으로 찾아서 한번 실행시켜주면 되었다. 이번에는 출발점이 여러개 일 수 있기 때문에 이중 for문으로 찾은 출발점들을 바로 넘겨주지 않고, 큐에 저장했다. 그 뒤로는 똑같음 딱히 어려운 점은 없었다.
-
2667 단지번호붙이기알고리즘/백준 문제 2020. 5. 15. 03:14
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 이전에 풀었던 BFS 문제들과 비슷한데, 다른점은 출발점이 정해져 있지 않다. 그렇기 때문에 이중 for문을 만들어서 모든 지점을 출발점으로 하여 BFS를 실행한다. BFS 함수 내부에서는 초반에 방문한 좌표가 들어오면 종료시켜준다. 종료되지 않았다면 단지가 형성되어 있다는 의미이므로, while문 안에 for문을 돌때마다 단지의 아파트수 (cnt)를 증가 함수를 종료하기 전에 List에 cnt값..
-
2178 미로탐색알고리즘/백준 문제 2020. 5. 14. 20:11
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 미로의 시작 [0,0] 에서 [n-1, m-1]로 빠져나가는 최단거리를 구하는 문제 - 정점간의 거리가 모두 1 이므로 BFS를 사용하여 최단거리를 구할 수 있다. 탐색중인 위치(x,y) 를 표시할 클래스 Pos를 만들었다. 반복문을 이용해 이동가능한 상하좌우 좌표를 확인하기 위해 상하좌우로 이동시켜줄 _x, _y 배열을 생성했다. 즉 각각의 배열 인덱스 0은 '상' 으로 이동하기 위한 x좌표, y좌표를 담고 있다. 위와 같..
-
1260 DFS와 BFS알고리즘/백준 문제 2020. 5. 14. 18:40
입력값 : 4 5 1 1 2 1 3 1 4 2 4 3 4 - DFS (Depth First Search 깊이우선탐색) 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3 으로 이어진다. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 모든 정점을 방문 했으므로 프로그램은 종료된다. - BFS (Breath First Search 너비우선탐색) 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다. 각 정점의 거리가 1일..