알고리즘41

• 

  [백준 Java] 수들의 합2 🔗 문제링크 🔗 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🌟 생각 흐름 🌟 이런 비슷한 문제를 기업코테에서 한번 본적이 있다. 부분합을 이용한 문제여서 해당 아이디어만 알고 있다면 쉽게 해결 할 수 있다. index 1 2 3 4 5 갑 1 2 3 1️⃣ (현재값) 2 1 연속된 수의 합 1 3 2️⃣ (이전 값까지의 합) 6 1️⃣ + 2️⃣ = 3️⃣ 8 9 부분적인 합을 구하는방법 arr[1] - arr[0] =1 arr[2]-arr[1]=2 arr[3]-.. 알고리즘 2023. 5. 9.

• 

  [백준 java] 소가 길을 건너간 이유 14466 🔗 문제링크 🔗 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 🌟 생각 흐름 🌟 먼저 가지 못하는 길을 저장해야 한다고 생각했습니다. 만약 리스트 형태로 저장하게 된다면 탐색에 너무 많은 시간이 걸리고 map의 사이즈가 100*100이므로 배열의 형태로 저장하는 것이 이득이라 생각하였습니다. 문제는 길의 startx, starty, endx, endy 형태로 주어지기 때문에 어느방향으로 길이 있는지 저장해야 합니다. 따라서 direction 방향에 따라 확인해보면서 .. 알고리즘/백준 2023. 5. 5.

• 

  [백준 1939] 중량제한, 크루스칼 풀이 🔗 문제링크 🔗 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 🌟 생각 흐름 🌟 기존의 크루스칼 문제에서는 최단 경로를 계산하기 위해서 최단 경로를 기준으로 정렬을 하였다 하지만 해당 문제에서는 다리를 건널 때 가장 많이 적재할 수 있는 양을 물어보는 것이므로 가장 높은 값을 기준으로 정렬한다(내림차순) 만약 시작 지점과 끝지점이 한사이클안에 있다고 판단되는 순간 현재 적재량을 싫고 나를 수 있다는 소리이므로 멈추고 리턴한다. -- 이진탐색을 이용한.. 알고리즘/백준 2023. 5. 4.

• 

  [백준 Java] 1253 좋다 🔗 문제링크 🔗 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🌟 1번 풀이 ❯❯ 해시를 이용한 풀이 🌟 그냥 해시만 이용해도 풀리긴 한다 (꽤나 비효율적인 방법으로) 해당 방법에서 체크할 포인트는 0인경우에 대한 반례 체크이다. 0 0 0과 같은 경우 '0' 3개가 모두 만들어질 수 있다. (더해도 값을 유지한다) 🍳 코드(시간이 더 오래 걸리는 코드) 🍳 package 백준.hash; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 알고리즘 2023. 4. 29.

• 

  [백준 Java]1105_팔_greedy(실버1) 🔗 문제링크 🔗 1953번: 팀배분 첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속 www.acmicpc.net 🌟 생각 흐름 🌟 이 문제 완탐으로 해도 풀린다(0인 경우 바로 리턴하도록 하는 경우, 시간은 아주 별로로 나오지만) 처음에는 완탐으로 풀고 그리디 힌트를 얻어 그리디 방법을 생각해 봤다. 뭔가 숫자로 조합하는 느낌 이어서 푸는데 꽤나 신경쓸게 많은 구현 느낌이었다 1280 1281 -> 1개 , 숫자가 같은 경우 넘어가지만 숫자를 체크하지 않는다. 이후에 값이 다른 경우에만 브레이크 한다. 8756 12345 -> 길이가 다른 경우 비교하지 않아도 된다... 알고리즘 2023. 4. 28.

• 

  [Java 백준] 2887 행성터널 플래티넘5 🔗 문제링크 🔗 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 🌟 생각 흐름 🌟 오랜만에 그래프 문제 푸니까 재미있었다. 1. 모든 행성의 경우에 대해서 계산하기 -> 100,000 * 99,999 /2 하니까 메모리 에러가 났다. 2. 고민을 하다가 메모리 초과가 난경우에 대해서 생각을 해봤다. 문제를 다시 읽다 보니 터널생성에는 x, y, z 중 제일 작은 차를 이용한다. 즉 x, y, z의 제일 작은 값들만 비교하면 다른 값들은 의미가 없다는 생각이 들었다. 따라서 x,.. 알고리즘 2023. 4. 20.

• 

  [백준 java] 1941 소문난 칠공주, 조합, bfs 🔗 문제링크 🔗 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 🌟 생각 흐름 🌟 25자리의 자리 중 7개의 자리를 선택하고 해당 자리들끼리 연결되어 있는지, 이다솜 편이 4명 이상인지 확인한다. 🍳 코드 🍳 package 백준.구현; import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.. 알고리즘 2023. 4. 18.

• 

  [백준, JAVA] 17281 공 ⚾️ (골드 4, 구현) 🔗 문제링크 🔗 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 🌟 생각 흐름 🌟 모든 가능한 선수들의 번호수를 깊이 우선탐색을 이용해서 구한다 ( 4번 타자는 1번으로 정해져 있다 ) 선수들이 정해지면 점수를 매긴다. 쓰리아웃이면 다음 이닝으로 넘어가고 그다음 플레이어(타자? 투수?)가 이어서 진행한다. 만약 0점이면 바로 아웃점수를 체크하고 넘어간다. 점수가 있는 경우 홈런인 경우는 1,2,3루수에 사람이 있는 경우 모두 점수로 체크한다. 1,2.. 알고리즘 2023. 4. 6.

• 

  [백준 Java] 17472 다리만들기2 구현, 골드 1 🔗 문제링크 🔗 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 🌟 생각 흐름 🌟 모든 섬을 분리해 낸다. 몇 개의 섬이 있는지 파악하고 섬을 각각 다른 색으로 색칠한다. 추가로 연결된 섬을 모두 탐색하면서 4방위로 바다가 있는 경우 해당 노드를 추가한다. 4방위로 바다가 있던 노드들만 확인한다. 4방위중 바다가 있는 방면으로 계속 진행했을 때 다른 섬이 있다면 가능한 것이다. 가능한 값이 2 이상이고, 최소 값인 경우 업데이트한다. int [][] minBridges에 각 섬에서 다른 섬.. 알고리즘 2023. 4. 5.

• 

  [백준, 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.