일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 세그먼트트리
- 다익스트라
- 완전탐색
- 게더타운시작
- DFS
- java
- 01BFS
- GatherTown
- 우선순위큐
- 재귀함수
- 자바PS
- 알고리즘
- 구현
- deque
- 백준
- PS
- QUICKSTARTGUIDE
- 시뮬레이션
- COSPROJAVA1급
- 엘라스틱서치
- YBMCOS
- 백준코딩테스트
- 네트워크플로우
- 취득후기
- COSPRO
- 다이나믹프로그래밍
- BFS
- dp
- spring
- 이젠 골드구현도 어렵네..
- Today
- Total
목록전체 글 (235)
공부공간
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번의..
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050 JUNGOL | 냉장고 > 문제은행 N개의 화학 물질 C1, C2, …, Cn이 있다. 이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다. 이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 이를 해결하는 프로그램을 작성하시오. jungol.co.kr PriorityQueue 연습문제로 class의 특정 인스턴스를 기준으로 정렬하였다. 냉장고 문제는 최고 보관온도와 최저 보관온도를 각..
문제 해결 접근 별로 어렵지 않은 형태의 기본적인 동적 프로그래밍의 문제로 보인다. 입력받은 점수 행렬은 3개의 열을 가지며 항상 최대, 최소 값을 갱신하도록 알고리즘을 설계하여 준다. 해당 문제의 점화식은 다음과 같다. minDP[i][0] = min(minDP[i-1][0] , minDP[i-1][1]) + map[i][0] minDP[i][1] = min(minDP[i-1][0], min(minDP[i-1][1], minDP[i-1][2])) + map[i][1] minDP[i][2] = min(minDP[i-1][1] , minDP[i-1][2]) + map[i][2] 한 행이 진행 될때마다, 이전 행렬의 합산 값을 비교하여 최소 혹은 최대의 값과 현재 행렬의 값을 더해준다. 따라서 다음과 같이 ..
3중 for 문을 활용하여 풀어야 하는 동적 프로그래밍 문제이다. 파일은 연속되는 것들만 합치기가 가능하며, 파일을 계속 합치며 도출 되는 비용이 최소가 되도록 알고리즘을 구성해야 한다. 알고리즘 풀이에 쓰이는 배열 1. dp[i][j] 배열은 i 부터 j 장까지 최소 비용이라고 정의하고, 첫 번째 장부터 마지막 장까지 최소 비용의 값을 갱신하며 값을 도출한다. 이러한 정의로 다음과 같은 점화식을 도출할 수 있다. 2. cost[i] 배열은 주어진 파일을 합치는 비용을 저장하는 배열이다. 3. sum[i] 배열은 i 까지의 파일을 합하는데 필요한 비용을 나타낸다. 예를 들어, 첫 번째 경우 예제 입력에서 주어진 값을 사용한다면, sum[2] = 70 이고 sum[i] = sum[i-1] + cost[i]..
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로 일..
본 포스트에서는 JAVA에서 Problem Solving을 위한 자료구조를 다룬다. 다룰 항목은 1. ArrayDeque 2. PriorityQueue 3. HashMap 4. HashSet 이다. 사용빈도는 각각 다르지만 적절한 자료구조를 선택함에따라서, 시간을 크게 단축할수 있다. ArrayDeque ArrayDeque는 Queue를 상속받아 구현한 것이다. 양방향 큐와 Stack을 동시에 사용할수있는 자료구조이다. 입/출력의 속도가 빠르고 동기화의 부분을 줄이므로 시간을 단축하였다. Java Tip #2 : 큐(Queue) 성능 테스트 출처 : http://yjacket.tistory.com/48 한글 api : http://www.designonex.com/bbs/board.php?bo_table..
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..