알고리즘,PS

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [문제] [풀이] 치킨 집 - 가정 집 사이의 거리를 최소로 하는 치킨 집들을 구해서 거리 합을 구하는 문제이다. 주어진 map 상태를 보면 중간에 벽이 없이 거리는 (x2-x1)+(y2-y1) 으로 구하면 되기 때문에 그래프를 탐색 하지 않고 모든 치킨 집과 가정 집 사이의 거리를 다 구해서 최소를 찾는 완전탐색을 하면 된다. 탐색의 크기는 치킨 집 좌표의 갯수를 기준으로 ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [문제] [풀이] 주어진 조건을 만족할 때 까지 반복하여 BFS를 돌려야 하는 문제이다. 주어진 조건의 종결조건 => 더 이상 인구 이동을 하지 않을 때 따라서 BFS를 돌리며 연합 가능한 국가들의 인구를 계속해서 구한 평균치로 새로 설정하고 더 이상 이동할 필요가 없을 경우엔 break를 걸어 빠져 나오면 된다 import java.util.*; import java.io.*; i..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [문제] [풀이] 기본적으로 좌표 Map 에서 BFS를 시행하면 최단경로로 가기때문에 다익스트라랑 유사한 알고리즘으로 동작한다. 일반적인 BFS로 풀이하되 벽을 부수는 경우가 추가로 생겼기 때문에 이에 대한 check를 나타내야함 visit 방문확인 배열을 3차원으로 하여 크기는 k+1로 둔다. (벽을 안 부쉬는 경우도 있기 때문) 벽을 부술때마다 +1 씩하여 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net [문제] [풀이] 왼쪽에서 오른쪽으로 파이프를 쭉 연결해야 하는데 , 최대한 많이 연결해야 한다. 그러기위해선 2가지의 조건을 생각해야한다. 1. [오른쪽위 , 오른쪽, 오른쪽아래] 순서대로 연결해야함 => 만약 y좌표가 0번째에서 출발해서 맨 오른쪽 아래에 꽂히면 다른 1~n 번째에서는 절대 연결이 불가능 2. 이 문제는 백트래킹문제가 아니라 그리디 문제이기 때문에 모든 경우를 따지면 안된다 => 종결조건에 다..

https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr [문제] [풀이] 완전탐색 + 그리디 문제이다. 1. 맞출 수 있는 모든 과녁을 중복을 포함하게 탐색할 것 2. 누군가 득점을하면 나머지 하나는 득점을 하지 못함 3. 가장 낮은 점수를 많이 맞춘 순 으로 리턴할 것 이 세가지만 만족하면서 탐색하여 depth 가 주어진 n 만큼 진행하고 정산한 결과를 리턴해주면 된다. import java.util.*; import ..

https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr [문제] [풀이] 처음엔 트리 DP 문제인줄 알고 접근했었다가 다시 돌아올 수 있다는 조건때문에 풀지 못했었다. 이 문제는 오히려 중복체크를 하지 않아도 되기때문에 그리디+탐색으로 충분히 풀 수 있었다. 1. 탐색..

https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr [문제] [풀이] 입력이 IN 이면 주차를 시켜야하고 OUT이면 출차시키고 주차된 시간을 누적시킨다음 요금을 계산해야한다. 현재 주차 상태를 나타내는 HashMap 총 시간누적을 나타내..

https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr [문제] [풀이] 1. 진수 변환하기 2. "0"을 기준으로 나누기 3. 소수 판별해서 카운트하기 이렇게 진행하면 쉽게 풀리는 문제이다. 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 import java.u..