전체 글
-
[BOJ] 캐슬 디펜스Algorithm/BOJ 2020. 9. 6. 14:01
[17135] 캐슬 디펜스 https://www.acmicpc.net/problem/17135 Solution 문제에서 주어진 조건만 고려하면서 그대로 구현했다. 입력에서 주어진 격자판에서 마지막 행에 궁수를 배치할 수 있도록 map[N+1][M] 크기로 바꾸었다. permutation() 함수로 위치를 바꿔가며 세 명의 궁수를 배치 궁수의 위치가 정해지면 N번의 턴마다 shoot() 함수를 호출해 죽은 적의 수를 count 변수에 더해 가장 큰 값만 answer 변수에 가지고 있는다. shoot() 함수에서는 각 궁수의 위치로부터 d 거리 내의 가장 가까운 적을 죽인다. 유의해야할 부분은 가장 가까운 적을 동시에 죽이다 보니 표적이 되는 적이 중복되는 경우가 있으므로 세 명의 궁수에 대해 가까운 적을 ..
-
[BOJ] 동전 1, 동전 2Algorithm/BOJ 2020. 9. 3. 18:51
[2293] 동전 1 https://www.acmicpc.net/problem/2293 소스코드 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 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(..
-
[Programmers] 호텔 방 배정Algorithm/Programmers 2020. 9. 2. 14:47
[2019 카카오 겨울 인턴십] 호텔 방 배정 https://programmers.co.kr/learn/courses/30/lessons/64063 Solution 처음에 연결리스트를 사용해서 room이 이미 선택됐을 경우 room+1 부터 순회하면서 방을 탐색하는 방식으로 구현했었는데 O(N)의 시간복잡도로는 해당 문제의 효율성 테스트를 통과할 수 없었다. 이후 다른 사람의 풀이에서 HashMap을 사용해 다음 방을 탐색하는 횟수를 최소로 하는 탐색 방법을 볼 수 있었다. map.put(선택된 방, 다음 방)으로 탐색의 시작점을 기록하는 것이다. 1. room_number 배열의 모든 원소에 대해 findEmptyRoom(int room) 함수를 호출 2. map에 room이 없는 경우는 아직 선택되지..
-
[SWEA] 차량 정비소Algorithm/SWEA 2020. 9. 1. 18:26
[2477] 차량 정비소 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy [입력] [1] 접수 창구 개수 N, 정비 창구 개수 M, 방문 고객 수 K, 지갑을 두고간 접수 창구 번호 A, 정비 창구 번호 B [2] 각 접수 창구에서의 접수 시간 ai N개 [3] 각 정비 창구에서의 정비 시간 bi M개 [4] K명의 고객이 정비소에 도착하는 시간 K개 [출력] 지갑을 두고 간 고객과 같은 접수 창구 A와 정비 창구 B를 이용한 고객들의 고객번호 합 Solution 접수 창구 대기열 q1, 정비 창구 대기열 q2, 접수 창구 배열 c1, 정비 창구 배열 c2를 만들었다. c1[0][i] ..
-
[BOJ] 영화감독 숌Algorithm/BOJ 2020. 8. 27. 01:11
[1436] 영화감독 숌 https://www.acmicpc.net/problem/1436 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int n; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int num = 0; ..
-
[BOJ] 괄호 추가하기Algorithm/BOJ 2020. 8. 26. 18:19
[16337] 괄호 추가하기 https://www.acmicpc.net/problem/16637 길이가 N인 수식이 주어진다. N은 1-9 숫자 혹은 {+, -, *} 연산자 연산자 우선순위는 모두 동일. 왼쪽부터 순서대로 계산 단 괄호를 추가했을 때는 괄호 안 수식 먼저 계산하여 중첩 괄호는 허용하지 않는다. 수식이 주어졌을 때, 괄호를 적절히 추가하여 식의 결과의 최댓값 구하는 문제 괄호의 수는 제한이 없으며 없어도 된다. 수식 길이 N(1 먼저 계산할 수식을 고르는 것 연산자는 최대 9개가 나올 수 있고, 9개를 모두 고르는 일 => 괄호가 하나도 없을 때 괄호는 중첩될 수 없으므로 ((3 ①+ 8) ②* 7) ③- 9 ④+ 2 의 ①, ② 연산자를 연속해서 뽑을 수 없다. 위 예에서는 1번 연산자..
-
[BOJ] 최단경로Algorithm/BOJ 2020. 8. 25. 19:12
[1753] 최단경로 https://www.acmicpc.net/problem/1753 방향 그래프 정보와 시작점이 주어졌을 때 다른 모든 정점으로의 최단 경로를 구하는 프로그램 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) Solution 다익스트라 알고리즘을 알고 있다면 쉽게 아이디어를 떠올릴 수 있지만 정점 V의 개수가 최대 2만개로 인접 행렬로 풀이했을 경우 메모리 초과로 틀리게 된다. 인접 리스트와 우선순위 큐로 풀이하였다. 최단경로 FAQ https://www.acmicpc.net/board/view/34516 소스코드 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 ..