https://www.acmicpc.net/problem/24445   📌 자바(Java)로 푸는 너비 우선 탐색(BFS) - 백준 24445 문제 풀이 🚀🔎 문제 개요이 문제는 백준 24445번 - 알고리즘 수업 - 너비 우선 탐색 2 문제입니다.기본적인 BFS(너비 우선 탐색) 과정은 24444번과 동일하지만,이번에는 정점 방문 순서를 내림차순으로 정렬해야 합니다.💡 예제 입력5 5 11 41 22 32 43 4💡 예제 출력14325➡ BFS 탐색 시 정점을 큰 숫자부터 방문하도록 구현해야 합니다.🛠 알고리즘 접근 방식이 문제를 해결하는 방식은 24444번 문제와 동일하지만,각 정점의 인접 리스트를 내림차순(Collections.reverseOrder())으로 정렬해야 합니다.🔹 Java..

https://www.acmicpc.net/problem/24444   📌 자바(Java)로 푸는 너비 우선 탐색(BFS) - 백준 24444 문제 풀이 🚀🔎 문제 개요이 문제는 백준 24444번 - 알고리즘 수업 - 너비 우선 탐색 1 문제입니다.주어진 그래프를 너비 우선 탐색(BFS) 하면서 방문 순서를 기록해야 합니다.각 정점은 오름차순으로 방문해야 하며, 방문 순서는 result[] 배열에 저장해야 합니다.💡 예제 입력5 5 11 41 22 32 43 4💡 예제 출력12345➡ 1번 정점부터 BFS 탐색하며 방문 순서를 출력해야 합니다.🛠 알고리즘 접근 방식이 문제를 해결하기 위해 BFS(너비 우선 탐색) + 정렬을 활용합니다.✏️ 주요 고려 사항✔ BFS를 사용하여 그래프를 탐색✔ 간..

https://www.acmicpc.net/problem/24480   📌 자바(Java)로 푸는 깊이 우선 탐색(DFS) - 백준 24480 문제 풀이 🚀🔎 문제 개요이 문제는 백준 24480번 - 깊이 우선 탐색 2 문제입니다.주어진 그래프를 깊이 우선 탐색(DFS)하며 방문 순서를 기록해야 합니다.단, 내림차순(큰 숫자부터) 으로 방문해야 한다는 점이 특징입니다.💡 예제 입력5 5 11 41 22 32 43 4💡 예제 출력14320➡ 1번 정점부터 내림차순으로 DFS 탐색하며 방문 순서를 출력해야 합니다.🛠 알고리즘 접근 방식이 문제를 해결하기 위해 DFS(깊이 우선 탐색) + 정렬을 활용합니다.✏️ 주요 고려 사항✔ DFS를 사용하여 그래프를 탐색✔ 간선 정보를 저장할 때 내림차순으로 ..

https://www.acmicpc.net/problem/1725   📌 자바(Java)로 푸는 히스토그램에서 가장 큰 직사각형 문제 풀이🔎 문제 개요이 문제는 백준 "히스토그램에서 가장 큰 직사각형 (1725번)" 문제입니다.주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다.💡 예제 입력72145133💡 예제 출력8위 입력에 대한 히스토그램을 그려보면 아래와 같습니다.이때, 가장 큰 직사각형의 넓이는 8입니다.🛠 알고리즘 접근 방식이 문제를 해결하기 위해 스택(Stack) 을 활용한 O(N) 최적화 방법을 사용합니다.✏️ 주요 고려 사항각 히스토그램 막대의 높이(h)를 기준으로 만들 수 있는 가장 큰 직사각형의 넓이를 계산해야 합니다.스택을 활용하여 효율적으로 넓이를 계산할 수..

https://www.acmicpc.net/problem/17299    📌 자바(Java)로 푸는 오등큰수 문제 풀이🔎 문제 개요주어진 수열에서 각 숫자의 등장 횟수를 고려하여 오른쪽에서 가장 가까운 "더 자주 등장한 숫자"를 찾아야 하는 문제입니다.일반적인 오큰수(NGE, Next Greater Element) 문제와 달리 "숫자의 크기"가 아닌 "등장 횟수"를 기준으로 비교한다는 점이 다릅니다.💡 예제 입력71 1 2 3 4 2 1💡 예제 출력-1 -1 1 2 2 1 -1위 예제에서 각 숫자의 등장 횟수를 보면:1 → 3번 등장2 → 2번 등장3 → 1번 등장4 → 1번 등장각 숫자에 대해 오른쪽에서 더 자주 등장한 숫자를 찾으면 위와 같은 결과가 나옵니다.🛠 알고리즘 접근 방식이 문제를 ..

https://www.acmicpc.net/problem/24479   이 문제는 그래프 탐색 알고리즘인 DFS(Depth First Search)를 활용하여특정 시작 정점에서 탐색을 수행하며, 각 정점을 방문한 순서를 기록하는 문제다.아래 코드는 문제를 해결하기 위한 전체적인 흐름과 구현 방식을 포함하고 있다.우선, 입력으로는 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점 R이 주어진다.이 정보를 기반으로 그래프를 인접 리스트 형태로 표현하기 위해 list라는 배열을 생성한다.이 배열은 각 정점이 연결된 다른 정점들을 저장하는 리스트를 담고 있다.이를 통해 그래프를 효율적으로 관리하고 탐색을 수행할 수 있다.입력으로 주어진 간선을 처리하여 무방향 그래프를 구성한다.각 정점의 연결 정보를 정렬하여 ..

https://www.acmicpc.net/problem/17298   이 문제는 배열의 각 원소에 대해"오큰수(오른쪽에 있는 수 중 현재 수보다 큰 수 중 가장 가까운 것)"를 구하는 문제다.먼저 main 메서드에서 프로그램 실행의 흐름을 살펴보면,사용자로부터 입력값을 받아 배열에 저장한 후 logic 메서드를 호출해오큰수를 계산한 뒤 결과를 출력한다.사용자는 먼저 배열의 크기 N을 입력하고,다음 줄에 배열의 원소를 공백으로 구분하여 입력한다.이후 logic 메서드를 호출하여 오큰수를 계산한다. logic 메서드는 스택을 사용하여 효율적으로 오큰수를 구하는 핵심 부분이다.이 알고리즘은 반복문을 통해 배열을 순회하면서현재 원소와 스택에 저장된 인덱스를 비교한다. 스택에는 아직 오큰수가 결정되지 않은 인덱..

https://www.acmicpc.net/problem/2293   이 문제는 dp를 활용하여 N가짓 수의 동전이 주어졌을때K의 값을 몇가지 방법으로 나타낼 수 있는지 즉 몇가지 조합으로K값을 나타낼 수 있는지에 대한 경우의수를 묻는 문제다. k가 3이면 2,1 과 1,2 가 있는데 이는 순서만 다르기에 같은경우의 수로 취급한다. 이문제를 보자 2차원 DP 배열을 생각해 낼 수 있었다.dp [i][j] 는 i까지 동전을 사용했을 때 나타낼 수 있는 경우의 수로 정의하고dp[0][j]에서 0은 coins[0]이므로 0까지의 동전이아니라 coins[0] 동전만 사용했을때경우의 수가 된다. 이를 통해 점화식을 세워 봤을 때,  dp[i][j] = dp[i-1][j];if (j >= coins[i]) { ..

https://www.acmicpc.net/problem/2162    선분 교차 여부를 판별해 선분 그룹을 나누고,각 그룹의 크기와 전체 그룹의 개수를 계산하여 풀이했다.입력으로 주어진 선분들을 Line 객체로 저장하고,Union-Find 자료구조를 사용해 선분 교차 관계를 기반으로 그룹을 형성한다.각 선분은 시작점과 끝점을 Dot 객체로 표현하며,시작점이 항상 더 작은 값을 가지도록 정렬하여 일관성을 유지한다. 두 선분의 교차 여부는 isCross 메서드를 통해 확인하며,CCW 메서드를 사용해 세 점이 반시계 방향,시계 방향, 또는 일직선상에 있는지를 판별한다.교차하는 경우 Union-Find의 union 메서드를 통해 두 선분을 같은 그룹으로 합친다.그룹은 size 배열을 통해 크기를 관리하며,경로..

https://www.acmicpc.net/problem/1197   크루스칼 알고리즘을 활용하여 문제를 풀이하였다.최근 문제 풀이한 것 중에서 크루스칼이 있었고 간선을 가중치기준으로 정렬하여풀었던 기억이 있어 그방식대로 풀었다. 풀이과정은 비교적 간단하고이번 문제 풀이에서 기억에 남는것은  union find 를 활용할 때경로 압축이다. find() 함수에서 if(p[a] == a) 일때 return a를 하는것이아니라if(p[a]!=a) 일때 p[a] = find(a)를 해주고 return p[a] 를 하게되면 정점의갯수가 많아지고 간선이 많아지더라도 시간복잡도가 확실히 줄어든 다는점을알게되었다. 예를들어 정점이 6개고 parent 배열이 union(1, 2), union(2, 3) union(3, ..