131ms BFS 구현 경우에 따라 가지처럼 뻗어나가는 구조로 BFS 를 이용하여 구현하였다. 탈주범의 위치와 시간을 저장할 수 있는 Node 클래스를 만들어서 맨홀의 위치(시작위치)를 Queue에 넣고 반복문을 시작해준다. 터널의 모양에 따라 갈 수 있는 방향인지, 영역 내인지, 방문한 곳인지 조건문을 통해 체크한 후 지나갈 수 있는 곳이라면 방문 체크 및 한 시간을 더하여 다시 큐에 넣어주며 반복한다. 지정한 시간이 되거나 더이상 이동할 경로가 없는 경우 = Queue가 빈 경우 반복문이 종료되며 탈주범이 있을 수 있는 위치를 count한 값을 출력해준다. 여러 조건만 잘 체크하면 쉽게 풀 수 있는 문제였다. 👩🏻💻 소스코드 import java.io.BufferedReader; import jav..
13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS 최소비용을 찾는 문제로 BFS로 해결할 수 있었다. 수빈이의 위치와 시간을 저장하는 Node 클래스를 생성한 후, 3가지 연산(*2, +1, -1)을 수행하며 K까지 도달했을 때 최소 시간을 저장해준다. N, K의 범위는 0 ~ 100,000 으로 *2와 +1 연산을 할 때, 100,000을 초과되지 않도록 주의하고, -1 연산을 할 때, 0 미만이 되지 않도록 주의해준다. 👩🏻💻 소스코드 import java.io...
11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 누적합 2차원 배열에 대해 누적합을 저장하는 경우 O(N*N)의 시간 복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어든다. prefixSum[a][b] 를 (1,1)부터 (a,b) 까지의 합이라고 하자 왼쪽이 주어진 배열이고 오른쪽이 누적합을 저장한 이차원 배열이다. (1,1)에서 (2,3)까지의 누적합을 구하고자 하면 왼쪽 누적합과 위쪽 누적합을 더한 값에 교집합으로 두 번 더해지는 구간을 한 번 빼준 후 (2..
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 알고리즘 이 문제는 DP를 대표하는 배낭 문제로 냅색 알고리즘(knapsack)로 풀이하는 문제이다. 배낭이 수용할 수 있는 최대 무게가 정해지고 배낭에 넣은 물건들의 가치의 최대합을 구하는 문제이다. 냅색 알고리즘은 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있다. Fraction Knapsack : 짐을 쪼갤 수 있는 배낭문제로 탐욕 알고리즘(greedy)로 풀이 0/1..
자꾸 까먹어서 써놓는 이미 push한 commit message 수정하기 🙄 git rebase HEAD~1 -i : 바로 직전 commit 수정 에디터에서 pick을 reword로 변경 후 :wq! commit message 수정 후 esc :wq! git push -f 주의⚠️ 내 레포에서만 사용하기
개미전사 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 식량창고가 일직선상일 때 최대한 많은 식량을 얻기를 원한다.개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을..
12907번: 동물원 동물원에 동물이 N마리 있고, 1번부터 N번가지 번호가 매겨져 있다. 이 동물원에 동물은 토끼나 고양이밖에 없고, 모든 동물의 키는 다 다르다. 수빈이는 토끼와 고양이를 구분할 수 없지만, 토끼 www.acmicpc.net 해당 문제는 동물들이 자신보다 키가 큰 고양이 or 토끼 수 를 말할 때, 각 대답이 어떤 동물이 했는지 가능한 경우의 수를 구하면 되는 문제이다. 이 문제의 핵심은 모든 동물의 키는 서로 다르다로 다음과 같은 특징을 알 수 있다. 1. 동물의 대답(입력값) 중 같은 값이 최대 2번 나올 수 있다. 예시) 자신보다 키가 큰 동물이 한 마리 있다고 토끼가 말한 경우와 고양이가 말한 경우로 최대 2번 2. 동물의 대답은 토끼 및 고양이 각각 연속된 수열로 이루어져 있..
동적계획법(DP)은 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 기법이다. 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하여 시간복잡도를 획기적으로 줄일 수 있다. DP 문제 조건 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 호출하여 해결해야 할 경우 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn..
XML 은 태그 등을 이용하여 문서나 데이터를 구조화하는 언어이다. xml 태그는 자유롭게 생성하기 때문에 최초 작성자의 의도대로 작성되는지 확인할 필요가 있으며 DTD 또는 Schema를 이용해서 문서의 규칙을 작성한다. 이러한 DTD, Schema를 잘 따른 문서를 "valid 하다" 라고한다. 파싱이란 문서에서 필요한 정보를 얻기 위해 태그를 구별하고 내용을 추출하는 과정이다. 문서의 파싱에는 대표적으로 3가지 방식이 있다 SAX(Simple API for XML) parser 문서를 읽으면서 태그의 시작, 종료 등 이벤트 기반으로 처리하는 방식 빠르고 한 번에 처리하기 때문에 다양한 탐색이 어렵다 DOM(Document Object Model) parser 문서를 전부 로딩한 후 문서 구조 전체를..
1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 💡 DP (Top-Down) 오른쪽 방향 또는 아래 방향으로 탐색하며 도착지점까지 가는 경로의 개수를 찾는 문제로 처음은 DFS로 해결하였지만 시간초과로 인해 DP를 활용하여 특정 경로에서 도착지점까지 가는 경로 개수를 저장해두고 방문한 경로이면 저장한 경로 개수를 return하며 해결할 수 있었다. DFS로 구현했을 때 시간초과가 난다면 DP 로 해결하기 해당 좌표에서 도착지점까지 가는 경로의 개수가 0인 좌표와 처음 방문하는 좌표를 구분하기 위해 ..
12018번: Yonsei TOTO 첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어 www.acmicpc.net 💡 Priority Queue 가장 적은 마일리지로 가장 많은 과목을 수강하기 위해서는 모든 과목에 사용해야하는 최소의 마일리지를 구한 후, 가장 적게 드는 과목부터 주어진 마일리지를 초과하지 않도록 하나씩 더하면 풀 수 있는 문제이다. 1. 각 과목에 신청한 마일리지들을 높은 우선순위 큐에 넣어준다. 2. (수강인원-1)이 될 때까지 마일리지가 큰 순서대로 poll 해준다. 한 자리는 성준이자리 2-1. 신청한 사람 수보..
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 💡 DFS 비 내리는 양에 따라 나뉜 영역 개수를 찾고 그 중 가장 많은 영역을 가질 수 있는 경우를 구하면 되는 문제이다. (0,0)부터 상하좌우로 탐색하며 방문 체크하는 구조로 DFS를 이용했다. max_rain : 비가 올 수 있는 최대 ( 지역의 높이 중 가장 큰 높이 ) 비 내리는 양을 하나씩 증가시키며 나뉜 영역 중 최대 구하기 비 양에 따른 물에 잠긴 구역 체크 full() 이중 for문을 돌며 물에 잠기지 않은 구역 탐색 safe_area() 물에 잠기지..
