일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 엘라스틱서치
- COSPRO
- YBMCOS
- 완전탐색
- 다익스트라
- 시뮬레이션
- 게더타운시작
- dp
- java
- 알고리즘
- spring
- 다이나믹프로그래밍
- DFS
- 세그먼트트리
- deque
- 백준
- 이젠 골드구현도 어렵네..
- PS
- 재귀함수
- 우선순위큐
- BFS
- 백준코딩테스트
- 자바PS
- COSPROJAVA1급
- 취득후기
- 01BFS
- 네트워크플로우
- QUICKSTARTGUIDE
- GatherTown
- 구현
- Today
- Total
목록알고리즘/완전탐색(BFS,DFS) (70)
공부공간
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 상당히 쫄았던 문제이다.. Union-Find 개념을 이용하여 접근하려니 접근방법이 잘 보이지 않았고, 워스트케이스에대해서 0.5초의 시간을 넘을 것같다는 생각이 들었다. 일단한번 서브셋을 구해서 나누어보자! 라는 생각으로 접근하였는데, 단순한 2번의 BFS로 해결되었다. 문제에 쫄면 안되겠다. import java.io.BufferedReader; import java.io.InputStreamReader; impo..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 익은토마토가 주변에 안익은 토마토를 전파하면서 퍼지는 문제이다. 퍼질때에 값이 일정하게 ( 시간이 + 1 ) 씩 증가하므로 BFS로 퍼지는..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 다리만들기 문제는 입력으로 들어온 맵에서 1로만이루어진곳을 섬으로 나누고, 나누어진 섬끼리 연결하는 최단경로를 찾는 문제이다. 2번의..
https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 주어진 N x M배열에서 일부를 90도 회전시켜서 행의 합의 최솟값을 구하는 문제이다. 행의 합이 최소가되기위해서 DFS로 일..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com map에서 3번 벽돌을 깰수있다 row에서 중복조합을 통해 3개의 index를 선택 (DFS) 한 후에 그 index에서 포탄을 떨어뜨려 해당 map의 수만큼 상하좌우로 연쇄적으로 포탄이 터지면서 최종 벽돌이 몇개남았는지? 최솟값을 출력하는 문제이다. 문제의 순서는 간단하다. 1. N개중에 중복을 허용해서 3개를 선택 2. 선택된 3개를 순차척으로 처리 ( ArrayList 사용 ) 3. 선택된 R..
문제 ↓ https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE 등산로를 개척하면서 단 한 경로의 높이를 낮추어서 최장거리의 경로를 구하는 문제이다. 이경우 N이 충분히 작기때문에 DFS로 해결이 가능했지만, N이 크다면 BFS + 백트래킹 + VISIT배열변경 등의 다양한 방법으로 접근해야 했었던 문제이다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이..
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 한참 시간초과가 난문제.. 색종이를 붙일수있으면 ( 5x5,4x4...) 붙이고 최소로 덮을 수 있는 개수를 출력하는 문제이다. 각 색종이는 5장씩있어..
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net N,M이 충분히 작기때문에 DFS로 상황을 만들고 정답이 될수있는지 구현하는 문제이다. 문제의 접근은 아래와 같이했다. MAP을 입력받고, MAP의 맨 마지막줄 N+1번째에 궁수를 3명 배치해야한다. 궁수는 N개중 순서상관없이 3명을 뽑는 것이므로, 비트마스크를 통해서 2중 FOR문으로 조합의 경우의 수를 뽑아낸후, MAP에 붙이고 계산하는 메소드에 넘겨준다. 입력으로 받은 D는 궁수가 공격을 할 수있는 최..