알고리즘49

• 

  [백준, JAVA] boj 17135 캐슬디펜스 골드3 🔗 문제링크 🔗 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 🌟 생각 흐름 🌟 우선 궁수의 배치를 생각한다, 궁수는 DFS로 계산하여 3자리를 구하면 된다. DFS로 배치 후에 해당 환경에서 궁수가 죽일 수 있는 최대 적의 수를 구한다. 모든 적에 대해서 궁수와의 거리를 비교한다. 만약 거리가 D이하이고 현재 궁수의 최소 거리의 적보다 가깝다면 교체한다. 최소 값 선택 기준 만약 현재 최소 값보다 작으면 교체한다. 만약 최소 값과 같은면 더 왼쪽에 있는 걸 선택한다 값 비교가 끝난이후에는 한 칸 이동한다. ( 가로축 .. 알고리즘 2023. 3. 29.

• [백준 Java] 16397 탈출 BFS 골드 4 🔗 문제링크 🔗 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net 🌟 생각 흐름 🌟 단순 bfs방법으로 풀이했다 기존의 숨바꼭질 하고 비슷하다 2022.09.28 - [알고리즘] - [백준]12851_숨바꼭질 2 [백준]12851_숨바꼭질 2 [문제 링크] boj 12851 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 1.. 알고리즘 2023. 3. 19.

• 

  [백준 Java] 1946 신입사원 실버1 , 그리디 🔗 문제링크 🔗 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 🌟 생각 흐름 🌟 먼저 이 문제는 순위로 표기하므로 높은 점수가 아닌 낮은 점수가 우선순위가 높다. 문제는 내가 모든 지원자들보다 1,2차 점수중 하나의 순위라도 더 좋아야(낮아야) 한다는 것이다. 1 Try (시간 초과) : 단순 그리디 문제로 생각하고 접근했다. 1차 점수 기준으로 정렬을 한다. 즉 정렬된 후에 앞에 있는 사람들이 현재 자신보다 무조건 1차 점수는 높은 것(순위는 낮은 것)이다. 따라서 앞에 있는 모든 사.. 알고리즘 2023. 3. 9.

• [백준 Java] 4195번: 친구 네트워크, union-find 🔗 문제링크 🔗 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 🌟 생각 흐름 🌟 두 친구에 대한 이름에 대한 저장이 필요해서 HashMap을 이용해서 이름과 배열에 할당할 index를 저장했다. 배열의 사이즈는 n개의 라인에 모두 서로 다른 친구가 나올 수 있을 것 같아 2*n으로 할당했다. 이후에는 친구의 이름이 해시에 없다면 저장하고 있다면 찾아온다.(만약 그냥 저장하면 index번호가 꼬이므로 저장하지 않는다) 두 친구가 이미 친구 관계인 경우에는 친구의 개수를 리턴하고 친구가 아닌 경우에만.. 알고리즘 2023. 3. 1.

• [백준 Java]15711_환상의 짝궁_수학, 소수 🔗 문제링크 🔗 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 🌟 생각 흐름 🌟 처음 문제를 보고 짝수와 홀수를 나눠서 생각했다. 1. 홀수의 경우 소수이기 위해서는 한 수가 무조건 2이고 다른 수고 sum-2 이어야 한다. 홀수가 되기 위해서는 짝수 + 홀수 이기 때문에 유일한 짝수이자 소수인 2를 무조건 포함해야 한다고 생각했고 나머지만 소수 판별하면 되겠네라고 생가하고 넘어갔다. 2. 짝수인 경우에는? 여기서 한번 고민을 했다 이걸 다 확인할 수는 없을 거 같은데.. 그래서 구글에 "소수의 합"을 검색하니 .. 알고리즘 2023. 2. 25.

• [백준 Java]1459_걷기_그리디 🔗 문제링크 🔗 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 🌟 생각 흐름 🌟 완탐으로 한다면 x, y의 범위로 인해서 시간 초과가 날 것 같아 그리디로 풀었다 길을 걷는 경우는 3가지로 나눌 수 있다. 모든 블록을 하나씩 다 걸어가는 방법 대각선으로 (n, n)까지 가서 (n, m)이나 (m, n)으로 가는 방법 (n이 더 작다고 가정) 모든 블록을 지그재그로 가는 방법(합이 짝수인 경우에는 모든 경로를 지그재그로 갈 수 있지만 홀수인 경우에는 한 번은 그냥 블록을 걸어가야 한다) 위의 3가지를 계산해.. 알고리즘 2023. 2. 23.

• [백준]1953_팀배분_DFS(BFS도 가능) 🔗 문제링크 🔗 1953번: 팀배분 첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속 www.acmicpc.net 🌟 생각 흐름 🌟 우선 문제를 풀기 위해서 싫어하는 사람들과의 표기를 그래프를 통해서 진행했다 그래프를 그린 후 한 노드에서 시작한 경우 현재 노드와 다음노드만 다른 팀이면 가능하다고 생각했다 그리고 그 다음노드에서의 다음노드가 서로 다른 팀이면 가능하다는 식으로 dfs로 구현하였다 그래서 한 노드에서 시작한후 현재 깊이가 짝수이면 청팀, 홀수 이면 백팀에 넣도록 코드를 구현하였다 예를 들어 1,2가 서로를 싫어하고 2,3이 서로를 싫어하는 경우 ↔️ : .. 알고리즘 2023. 2. 22.

• 

  위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다. 방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서대로 나열하는 것이다. 2번을 풀기 전에 1번 3번을 풀기 전에 2번 ,4번 4번을 풀기전에 5번을 푸는 것이 좋다고 하는 상황이 있다면 우리는 다음과 같은 방법들로 문제를 푸는 것이 좋다면 1->2->5->4->3 1->5->2->4->3 과 같이 다양한 경우가 만들어 질수 있다(이 외에도 가능하다) 이렇게 정렬하는것이 위상정렬이다. 추가로 위에 상황에서 쉬운 문제를 먼저 푸는 것을 우선으로 한다고 하면 1->2->5->4->3 같은 순서로 답을 낼 수 있을것이다. [(숫자: 난이도, 1번이 제일 쉬운문제.. 알고리즘 2023. 2. 22.

• 

  [백준 Java] 1238 파티 (다익스트라, 데이크스트라) [문제 링크] boj 1238 자바 dijkstra graph https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net [생각 흐름] 처음에는 다익스트라 방법으로 문제를 해결하였다. n-1번 다익스트라를 동작시키고, 파티 위치부터 돌아오는 것을 더해 가장 큰 것을 구하는 방법으로 계산하면 된다. 문제에서는 시간상으로 통과하지만 더 좋은 풀이가 있을것 같아 다른 풀이도 확인해본 결과 A -> B로 가는 걸로 돌아가는 걸 계산.. 알고리즘 2023. 2. 21.

• [백준 Java] 11054 가장 긴 바이토닉 부분수열 [문제 링크] boj 11054 가장 긴 바이 토닉 부분 수열 자바 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net [생각 흐름] 전에 풀었던 11053 https://www.acmicpc.net/problem/11053 (가장 긴 증가하는 부분 수열) 문제와 유사한 풀이 방법으로 해결했다. 앞에서부터 arr [i]를 포함한다는 전제로 arr [i]보다 작고 arr [j]까지의 최대 증가 부분 수열(sum [j])가 sum [i] 보다 크다면 sum[i] =.. 알고리즘 2023. 2. 21.

• 

  [백준] 2170 선 긋기 : 스위핑(Sweeping) 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 왼쪽 부터 선형 순회 하면 한번의 탐색으로 값을 낸다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { priva.. 알고리즘 2022. 11. 25.

• [백준 Java] 2812 크게만들기 그리디 알고리즘 [링크] https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [문제풀이 방법] 가장 큰 숫자를 만들기 위해서는 앞자리가 가장 큰 숫자가 나와야 한다. 따라서 앞자리의 제일 큰 숫자가 오도록 숫자를 찾으면 된다 하지만 문제는 N개중 K개를 지우는 경우이므로 앞에서부터 k까지만 탐색을 해야 뒤에 남은 자리의 숫자를 모두 채울 수 있다 예를 들어 123456의 6자리 숫자에서 4자리를 지우는 경우에는 (0~4범위 [1,2,3,4,5])범위 안에서 탐색하여 5를 선택하고 하나를 선택하였으므로 탐색 가능 범위가 (6~6범위 [6])까.. 알고리즘 2022. 11. 10.