알고리즘49

• 

  [백준 Java] 3055 탈출 🔗 문제링크 🔗 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🌟 생각 흐름 - 개인적 풀이 방법 🌟 물이 이동하는 경로와, 고슴도치가 이동하는 경로를 생각한다. 한 턴을 기준으로 BFS를 이용하여 먼저 물을 이동시키고, 고슴도치가 이동하는 방식으로 알고리즘을 구현하였다. 쉽게 물을 이동시키기 위해 물의 좌표를 입력당시 큐에 넣어두고 고슴도치의 시작 위치 또한 큐에 넣어준다. 이후에 물을 이동시키면서 기존 BFS와 같이 큐에 추가하면서 이동시킨다. ㄴ 차이점은 visit배열을 따로 선언하는것이 아닌 map에서 물이 이동.. 알고리즘/백준 2023. 5. 12.

• 

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

• 

  code up 기초 100문제 풀이 (JAVA) 1001 문제 링크 : [🔗🔗code up 문제 #1001] 문제 풀이 : [🔗🔗code up 풀이 #1001 ] 1002 문제 링크 : [🔗🔗code up 문제 #1002] 문제 풀이 : [🔗🔗code up 풀이 #1002 ] 1003 문제 링크 : [🔗🔗code up 문제 #1003] 문제 풀이 : [🔗🔗code up 풀이 #1003 ] 1004 문제 링크 : [🔗🔗code up 문제 #1004] 문제 풀이 : [🔗🔗code up 풀이 #1004 ] 1005 문제 링크 : [🔗🔗code up 문제 #1005] 문제 풀이 : [🔗🔗code up 풀이 #1005 ] 1007 문제 링크 : [🔗🔗code up 문제 #1007] 문제 풀이 : [🔗🔗code up 풀이 #1007 ] 1008 문제 링크 : [.. 알고리즘/코드업 2023. 5. 4.

• 

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

• 

  스택 두개로 큐 만들기 큐: FIFO(First in first out) 1,2 차례로 push하면 1,2 순서로 출력 스택 : LIFO(Last in first out) 1,2 차례로 push하면 2,1 순서로 출력 스택은 마치 하노이탑과 같이 물건을 쌓아 올린 후에 빼는 것과 같고, 큐는 빨대에 구슬을 넣었을 때 나오는 순서와 같다. 두개의 스택으로 큐 만들기 stack 1은 push용 stack2는 pop용이라 생각하는 것이 편하다. 스택 두 개를 활용해서 큐를 만들 수 있다. 1. 스택에 enqueue 하는 경우 스택 1에 데이터를 넣는다. 2. 스택 2에서 dequeue 한다(pop 한다) 2-1. 만약 스택 2가 비워져 있는 경우 스택 1에 있는 모든 데이터를 스택 2로 옮긴다. (이 과정에서 stack의 값이 re.. 알고리즘 2023. 4. 25.

• 

  [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.