티스토리

Geisha
검색하기

블로그 홈

Geisha

geishastory.tistory.com/m

개발 일기

구독자
5
방명록 방문하기

주요 글 목록

  • b4195. 친구네트워크 https://www.acmicpc.net/problem/4195 👥 자바로 푸는 친구 네트워크 문제 풀이 📌 문제 개요 백준 4195번 - 친구 네트워크 문제는여러 명이 친구 관계로 연결될 때,각 관계마다 현재 친구 네트워크의 크기를 출력하는 문제입니다. 친구 관계가 주어짐 (A B → A와 B가 친구)친구 관계가 생길 때마다, A와 B가 속한 전체 네트워크(연결된 집합)의 크기를 출력이름은 문자열로 주어짐 💡 예제 입력23Fred BarneyBarney BettyBetty Wilma3Fred BarneyBetty WilmaBarney Betty 예제 출력2 3 4 2 2 4 🛠 알고리즘 접근 방식 핵심은 Union-Find (Disjoint Set) 알고리즘이름이 문자열이기.. 공감수 1 댓글수 0 2025. 5. 8.
  • b1976. 여행가자 https://www.acmicpc.net/problem/1976 ✈ 자바로 푸는 여행가자 문제 풀이📌 문제 개요 여행 계획에 따라 여러 도시를 순서대로 방문할 수 있는지 판단하는 문제입니다.도시 간의 연결 여부가 주어지며, 여행 경로에 포함된 모든 도시가 **같은 네트워크(연결된 그룹)**에 있어야 합니다. 1은 도시간 연결을 의미하고 0은 연결이 없음을 의미합니다.Union-Find(Disjoint Set)를 활용하여 각 도시가 같은 그룹에 속하는지 판단하면 됩니다. 💡 예제 입력330 1 01 0 10 1 01 2 3출력:YES 🧠 알고리즘 접근 방식 Union-Find 자료구조를 사용해 도시 간 연결 정보를 하나의 집합으로 병합합니다.여행 계획에 포함된 도시들이 **모두 같은 집합.. 공감수 2 댓글수 0 2025. 5. 6.
  • b1717. 집합의 표현 https://www.acmicpc.net/problem/1717 🧩 자바로 푸는 집합의 표현 문제 풀이 📌 문제 개요 백준 1717번 집합의 표현 문제는 Disjoint Set(서로소 집합) 자료구조의 기본 동작인 Find와 Union을 구현하는 대표적인 문제입니다. 연산 종류0 a b : a와 b가 속한 집합을 합친다.1 a b : a와 b가 같은 집합에 포함되어 있는지 확인한다. 💡 예제 입력7 80 1 31 1 70 7 61 7 10 3 70 4 20 1 11 1 1예제 출력:NONOYES 🧠 알고리즘 접근 방식 핵심은 Union-Find 알고리즘입니다.각 원소는 자신이 속한 집합의 대표(parent)를 가리킵니다.find(x)를 통해 대표를 찾고, union(x, y)를 통해.. 공감수 0 댓글수 0 2025. 5. 6.
  • b4803. 트리 https://www.acmicpc.net/problem/4803 📌 자바(Java)로 푸는 트리 - 백준 4803 🌳사이클 탐지 + 연결 요소(트리) 개수 구하기 (Union-Find) 🔎 문제 개요 백준 4803 - 트리 문제는, 주어진 그래프에서 사이클이 없는 연결 요소(트리)를 찾아야 하는 문제입니다.하나의 그래프 안에 여러 개의 트리가 있을 수 있으며,사이클이 있는 연결 요소는 트리로 취급하지 않습니다. 💡 예제 입력6 31 22 35 66 52 10 0 💡 예제 출력Case 1: A forest of 2 trees.Case 2: No trees. 🛠 알고리즘 접근 방식 이 문제는 전형적인 Union-Find(Disjoint Set) 알고리즘에✔ 사이클 감지를 덧붙이는 문제입니.. 공감수 1 댓글수 0 2025. 4. 28.
  • b2263. 트리의 순회 https://www.acmicpc.net/problem/2263 📌 자바(Java)로 푸는 트리의 순회 - 백준 2263 🌲 Inorder + Postorder → Preorder 복원하기 🔎 문제 개요 백준 2263 - 트리의 순회 문제는, 이진 트리의 Inorder(중위 순회) 와 Postorder(후위 순회) 결과가 주어질 때,이진 트리의 Preorder(전위 순회) 결과를 출력하는 문제입니다.💡 예제 입력32 1 32 3 1 💡 예제 출력1 2 3 🛠 알고리즘 접근 방식 이 문제는 트리를 직접 복원하지 않고,✔ 순회 결과만을 이용해 바로 Preorder를 만들어내는 것이 핵심입니다. 📌 트리 순회의 특징 이해하기순회 방법순서Preorder(전위 순회)루트 → 왼쪽 → 오른쪽In.. 공감수 0 댓글수 0 2025. 4. 28.
  • b11780. 플로이드 2 https://www.acmicpc.net/problem/11780 📌 자바(Java)로 푸는 플로이드 2 - 백준 11780 🛣️최단 거리 + 경로 출력까지 포함한 플로이드 워셜(Floyd-Warshall) 🔎 문제 개요 백준 11780 - 플로이드 2는모든 도시 쌍에 대해 최단 경로의 거리를 구하는 것뿐만 아니라,각 최단 경로를 직접 경로로 출력하는 문제입니다. 💡 예제 입력5141 2 21 3 31 4 1... 💡 예제 출력0 2 3 1 1002 1 23 1 32 1 4... 🛠 알고리즘 접근 방식 이 문제는 전형적인 Floyd-Warshall (플로이드-워셜) 알고리즘에✔ 경로 추적까지 덧붙이는 구조입니다. costs[i][j]: 도시 i에서 j까지의 최소 비용lists[i][j.. 공감수 1 댓글수 0 2025. 4. 25.
  • b13913. 순간이동 4 📌 자바(Java)로 푸는 숨바꼭질 4 - 백준 13913🧍‍♂️➡️🧍‍♀️ 최소 시간 + 이동 경로까지 출력하는 BFS 문제! 🔎 문제 개요 백준 13913번 - 숨바꼭질 4는정수 N(수빈이 위치)에서 K(동생 위치)까지다음 세 가지 연산으로 이동해 최소 시간을 구하는 문제입니다. X - 1X + 1X * 2 뿐만 아니라,✔ 최단 시간과 함께✔ 그때의 이동 경로를 정확히 출력해야 합니다! 💡 예제 입력5 17 💡 예제 출력45 10 9 18 17 🛠 알고리즘 접근 방식 이 문제는 전형적인 최단 거리 탐색 → BFS 문제입니다.하지만 경로 추적까지 해야 하므로,✔ 이동 이전 위치를 기록하는 prev[] 배열을 활용해야 합니다. 🔹 Java 코드 설명📌 Node 클래스static clas.. 공감수 1 댓글수 0 2025. 4. 22.
  • b2618. 경찰차 https://www.acmicpc.net/problem/2618 📌 자바(Java)로 푸는 경찰차 - 백준 2618 🚓🚓두 경찰차의 최소 이동 거리 + 이동 경로까지 구하는 DP 문제 🔎 문제 개요 백준 2618 - 경찰차 문제는N × N 크기의 도시에 경찰차 2대가 배치되어 있고,여러 사건이 순차적으로 발생할 때두 경찰차가 어떻게 사건을 분담해서총 이동거리를 최소화할 수 있는지를 구하는 문제입니다. 경찰차 1: 항상 (1,1) 위치에서 시작경찰차 2: 항상 (N,N) 위치에서 시작각 사건은 정확히 한 번만 처리해야 하며,각 사건은 경찰차 1 또는 경찰차 2가 처리해야 합니다.💡 예제 입력633 55 52 3 💡 예제 출력9121 총 이동거리: 9각 사건을 처리한 경찰차 번호 출력 🛠.. 공감수 1 댓글수 0 2025. 4. 18.
  • b14003. 가장 긴 증가하는 부분수열 5 https://www.acmicpc.net/problem/14003 📌 자바(Java)로 푸는 가장 긴 증가하는 부분 수열 5 - 백준 14003 🔼LIS + 경로 추적을 O(N log N)으로 해결하는 대표 문제 🔎 문제 개요백준 14003번 - 가장 긴 증가하는 부분 수열 5 문제는수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이해당 부분 수열 자체 를 구하는 문제입니다.단, 수열의 길이가 최대 100만 개이므로 O(N²) 풀이 불가능합니다. 💡 예제 입력610 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 ✅ 핵심 전략: 이진 탐색 기반 LIS + 경로 추적 list[]: 현재까지 만든 LIS 수열 (값만 추적)dp[i]: arr.. 공감수 0 댓글수 0 2025. 4. 16.
  • b14002. 가장 긴 증가하는 부분수열 4 https://www.acmicpc.net/problem/14002 📌 자바(Java)로 푸는 가장 긴 증가하는 부분수열 4 - 백준 14002 📈최장 증가 부분 수열(LIS)을 구하고, 해당 수열을 출력하라!🔎 문제 개요 백준 14002번 - 가장 긴 증가하는 부분 수열 4 문제는기본적인 LIS(최장 증가 부분 수열) 문제에👉 “LIS 경로까지 출력”이 추가된 버전입니다.💡 예제 입력6 10 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 이 문제는 기본 LIS 문제에서“LIS의 경로를 저장”해야 하기 때문에✔ 단순한 DP 배열뿐 아니라✔ prev[] (이전 인덱스), lastIndex[] (길이별 마지막 인덱스) 추적이 필요합니다. 🔹 핵심.. 공감수 1 댓글수 0 2025. 4. 15.
  • b12852. 1로 만들기 2 https://www.acmicpc.net/problem/12852 📌 자바(Java)로 푸는 1로 만들기 2 - 백준 12852 🔢최소 연산 횟수 + 경로 추적까지 하는 DP 문제! 🔎 문제 개요 백준 12852번 - 1로 만들기 2 문제는정수 N이 주어졌을 때,1로 만들기 위해 사용할 수 있는 연산은 다음 세 가지입니다: X → X / 3 (3으로 나누어떨어질 때만)X → X / 2 (2로 나누어떨어질 때만)X → X - 1 최소 연산 횟수를 출력하고그 경로에 해당하는 숫자 순서도 출력해야 합니다. 💡 예제 입력10 💡 예제 출력310 9 3 1 🛠 알고리즘 접근 방식: Dynamic Programming (DP) ✏️ 핵심 전략 dp[i]: i를 1로 만들기 위한 최소 연산 횟수c.. 공감수 1 댓글수 0 2025. 4. 14.
  • b1450. 냅색문제 https://www.acmicpc.net/problem/1450   📌 자바(Java)로 푸는 부분 수열의 합 문제 - 백준 1450 🎒 🔎 문제 개요 백준 1450번 - 냅색 문제는최대 N = 30개의 물건이 주어질 때,각 물건의 무게를 더해 총합이 C 이하인 경우의 수를 구하는 문제입니다. 1 ≤ N ≤ 30, 1 ≤ C ≤ 1e9무작정 모든 조합을 돌리면 2³⁰ ≈ 10억 개, 시간 초과 발생❌➡ 그래서 “Meet in the Middle(중간에서 만나기)” 전략을 사용합니다. 🛠 알고리즘 접근 방식: Meet in the Middle  ✏️ 핵심 전략 배열을 반으로 나누고 각각 가능한 부분합의 조합을 모두 구함한 쪽 배열의 조합을 기준으로, 나머지에서 더해도 C 이하가 되는 조합 개수를 .. 공감수 1 댓글수 1 2025. 4. 10.
  • b3665. 최종순위 https://www.acmicpc.net/problem/3665   📌 자바(Java)로 푸는 최종 순위 문제 - 백준 3665 🏆🔁 🔎 문제 개요 백준 3665번 - 최종 순위는 위상 정렬(Topological Sort)을 응용하는 문제입니다. 작년 순위가 주어지고,올해 바뀐 순위 정보들이 입력되며,그 정보를 바탕으로 올해의 최종 순위를 결정하는 문제입니다. 단, 순위를 정확히 하나로 정할 수 없다면 ? 출력모순이 발생해서 순위를 정할 수 없다면 IMPOSSIBLE 출력 💡 예제 입력155 4 3 2 122 43 1 💡 예제 출력5 3 2 4 1  🛠 알고리즘 접근 방식 이 문제는 기본 위상 정렬에✔ 순위가 바뀐 간선을 뒤집는 작업(reverse edge)✔ 정점 진입 차수(indegre.. 공감수 1 댓글수 0 2025. 4. 9.
  • b.2696 중앙값 구하기 https://www.acmicpc.net/problem/2696   📌 자바(Java)로 푸는 중앙값 구하기 - 백준 2696 🔢 🔎 문제 개요 백준 2696번 - 중앙값 구하기 문제는여러 개의 수열이 주어졌을 때,각 수열마다 홀수 번째 수를 입력받을 때마다의 중앙값을 구하는 문제입니다. 입력 수열의 개수: T각 수열은 최대 10씩 끊어져 입력홀수 번째 수가 들어올 때마다 중앙값 출력 💡 예제 입력191 2 3 4 5 6 7 8 9 💡 예제 출력51 2 3 4 5  🛠 알고리즘 접근 방식 이 문제는 대표적인 중앙값(Median) 유지 문제로,**최대 힙(왼쪽 절반) + 최소 힙(오른쪽 절반)**을 사용하여 중앙값을 효율적으로 관리합니다.  ✏️ 핵심 아이디어 left: 최대 힙, 중앙값보다 .. 공감수 1 댓글수 0 2025. 4. 7.
  • b.2075 N번째 큰 수 https://www.acmicpc.net/problem/2075   📌 자바(Java)로 푸는 N번째 큰 수 문제 - 백준 2075 🧮 🔎 문제 개요 백준 2075번 - N번째 큰 수 문제입니다.N x N 크기의 행렬이 주어졌을 때, 모든 수를 정렬했을 때 N번째로 큰 수를 구하는 문제입니다. • 단순 정렬로 풀 수 있지만, 효율적인 풀이가 중요합니다. • 메모리 제한과 시간 제한을 고려하면 우선순위 큐 사용이 더 적절합니다. 💡 예제 입력512 7 9 15 513 8 11 19 621 10 26 31 1648 14 28 35 2552 20 32 41 49💡 예제 출력35➡ 모든 수 중 5번째로 큰 수(내림차순 정렬 기준)는 35 🛠 접근 방식 현재 코드는 모든 값을 배열에 넣고 정렬한 뒤 .. 공감수 0 댓글수 0 2025. 4. 4.
  • b.3273 두 수의 합 https://www.acmicpc.net/problem/3273   📌 자바(Java)로 푸는 두 수의 합 문제 - 백준 3273  🔎 문제 개요 백준 3273번 - 두 수의 합 문제입니다.정수 N개로 이루어진 수열이 주어질 때,서로 다른 두 수를 더해서 target이 되는 경우의 수를 구하는 문제입니다.조건은 다음과 같습니다: • 한 쌍은 한 번만 셈 • 중복 없이, 오름차순 또는 내림차순 상관없이 쌍을 구성 💡 예제 입력9 5 12 7 10 9 1 2 3 11 13💡 예제 출력3➡ 5+8, 1+12, 2+11 총 3쌍이 존재 🛠 알고리즘 접근 방식 이 문제는 대표적인 투 포인터(Two Pointer) 기법으로 해결할 수 있습니다. ✏️ 주요 고려 사항 • 배열을 정렬한 후, 왼쪽 포인터.. 공감수 0 댓글수 0 2025. 4. 1.
  • b.11657 타임머신 https://www.acmicpc.net/problem/11657   📌 자바(Java)로 푸는 타임머신 문제 - 백준 11657 ⏳ 🔎 문제 개요 백준 11657번 - 타임머신 문제입니다.N개의 도시와 M개의 버스 노선이 주어질 때,“1번 도시에서 다른 모든 도시로 가는 최단 시간” 을 구하는 문제입니다.🕰 단, 음수 가중치(시간이 감소하는 경우)도 존재할 수 있으며, 음수 사이클 여부를 판별해야 합니다. 💡 예제 입력3 41 2 41 3 32 3 -23 1 -1💡 예제 출력43-1➡ 1번 도시에서 각각 2번, 3번으로 가는 최단 거리 출력 (도달 불가능 시 -1) 🛠 알고리즘 접근 방식 이 문제를 해결하기 위해 벨만-포드 알고리즘(Bellman-Ford Algorithm) 을 사용합니다... 공감수 0 댓글수 0 2025. 3. 20.
  • b1956. 운동 https://www.acmicpc.net/problem/1956   📌 자바(Java)로 푸는 운동 문제 - 백준 1956 🚴‍♂️🔎 문제 개요 백준 1956번 - 운동 문제입니다.V개의 마을과 E개의 도로가 주어졌을 때,“한 마을에서 출발하여 다시 그 마을로 돌아오는 최소 사이클의 길이” 를 구하는 문제입니다.🚴 즉, 최단 사이클(순환 경로)의 길이를 찾는 것이 핵심입니다. 💡 예제 입력3 41 2 13 1 12 3 11 3 5💡 예제 출력3➡ 최단 사이클의 길이가 3인 경우를 찾아 출력 🛠 알고리즘 접근 방식 이 문제를 해결하기 위해 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 을 사용합니다. ✏️ 주요 고려 사항 ✔ 모든 정점 간 최단 경로를 계산해야 함✔ 각.. 공감수 0 댓글수 0 2025. 3. 20.
  • b.9370 미확인 도착지 https://www.acmicpc.net/problem/9370   📌 자바(Java)로 푸는 미확인 도착지 문제 - 백준 9370 🚗📍 🔎 문제 개요 백준 9370번 - 미확인 도착지 문제입니다.출발지(S)에서 목적지 후보들 중,특정 도로(G-H)를 반드시 지나면서 도달할 수 있는 목적지를 찾아야 합니다.다익스트라 알고리즘을 활용하여 최단 경로를 구하는 문제입니다. 💡 예제 입력26 9 21 2 31 2 11 3 22 3 23 4 33 5 54 5 44 6 15 6 256💡 예제 출력65 6➡ 목적지 후보 중 특정 도로(G-H)를 지나면서 도달할 수 있는 곳을 출력 🛠 알고리즘 접근 방식 이 문제를 해결하기 위해 다익스트라 최단 경로 알고리즘(Dijkstra) 을 활용합니다. ✏️ 주요 .. 공감수 1 댓글수 0 2025. 3. 15.
  • b.1707 이분 그래프 https://www.acmicpc.net/problem/1707   📌 자바(Java)로 푸는 이분 그래프 판별 문제 - 백준 1707 🚀 🔎 문제 개요 백준 1707번 - 이분 그래프 판별 문제입니다.주어진 무방향 그래프가 이분 그래프인지 판별하는 것이 목표입니다. 이분 그래프란? • 모든 정점을 두 개의 그룹으로 나눌 수 있는 그래프 • 같은 그룹 내 정점끼리는 서로 연결되지 않아야 함 • 즉, 인접한 정점은 항상 다른 그룹에 속해야 함 💡 예제 입력23 21 32 34 41 22 33 44 1💡 예제 출력YESNO➡ 첫 번째 그래프는 이분 그래프이며, 두 번째 그래프는 이분 그래프가 아님 🛠 알고리즘 접근 방식 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 활용한 그래프 색칠.. 공감수 1 댓글수 0 2025. 3. 12.
  • b24445. 알고리즘 수업 - 너비 우선 탐색 2 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.. 공감수 1 댓글수 1 2025. 3. 6.
  • b24444. 알고리즘 수업 - 너비 우선 탐색 1 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를 사용하여 그래프를 탐색✔ 간.. 공감수 1 댓글수 0 2025. 3. 4.
  • b24480. 알고리즘 수업 - 깊이 우선 탐색 2 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를 사용하여 그래프를 탐색✔ 간선 정보를 저장할 때 내림차순으로 .. 공감수 1 댓글수 0 2025. 3. 1.
  • b3015. 오아시스 재결합 https://www.acmicpc.net/problem/3015   📌 자바(Java)로 푸는 오아시스 재결합 문제 풀이 🚀🔎 문제 개요이 문제는 백준 3015번 - 오아시스 재결합 문제입니다.주어진 사람들의 키 정보를 기반으로 서로 볼 수 있는 쌍의 개수를 구하는 문제입니다.💡 예제 입력72412251💡 예제 출력10🛠 알고리즘 접근 방식이 문제를 해결하기 위해 스택(Stack) 을 활용한 O(N) 최적화 방법을 사용합니다.✏️ 주요 고려 사항✔ 각 사람의 키(h)를 기준으로 볼 수 있는 사람의 쌍을 계산해야 합니다.✔ 스택을 활용하여 효율적으로 볼 수 있는 쌍을 계산할 수 있습니다.✔ 스택에는 항상 오름차순으로 저장하여, 현재 키보다 작거나 같은 사람을 볼 수 있도록 합니다.✔ 같은 키를.. 공감수 0 댓글수 0 2025. 2. 25.
  • b.1725 히스토그램 https://www.acmicpc.net/problem/1725   📌 자바(Java)로 푸는 히스토그램에서 가장 큰 직사각형 문제 풀이🔎 문제 개요이 문제는 백준 "히스토그램에서 가장 큰 직사각형 (1725번)" 문제입니다.주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다.💡 예제 입력72145133💡 예제 출력8위 입력에 대한 히스토그램을 그려보면 아래와 같습니다.이때, 가장 큰 직사각형의 넓이는 8입니다.🛠 알고리즘 접근 방식이 문제를 해결하기 위해 스택(Stack) 을 활용한 O(N) 최적화 방법을 사용합니다.✏️ 주요 고려 사항각 히스토그램 막대의 높이(h)를 기준으로 만들 수 있는 가장 큰 직사각형의 넓이를 계산해야 합니다.스택을 활용하여 효율적으로 넓이를 계산할 수.. 공감수 1 댓글수 0 2025. 2. 6.
  • b.17299 오등큰수 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번 등장각 숫자에 대해 오른쪽에서 더 자주 등장한 숫자를 찾으면 위와 같은 결과가 나옵니다.🛠 알고리즘 접근 방식이 문제를 .. 공감수 1 댓글수 1 2025. 2. 4.
  • b24497. 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479   이 문제는 그래프 탐색 알고리즘인 DFS(Depth First Search)를 활용하여특정 시작 정점에서 탐색을 수행하며, 각 정점을 방문한 순서를 기록하는 문제다.아래 코드는 문제를 해결하기 위한 전체적인 흐름과 구현 방식을 포함하고 있다.우선, 입력으로는 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점 R이 주어진다.이 정보를 기반으로 그래프를 인접 리스트 형태로 표현하기 위해 list라는 배열을 생성한다.이 배열은 각 정점이 연결된 다른 정점들을 저장하는 리스트를 담고 있다.이를 통해 그래프를 효율적으로 관리하고 탐색을 수행할 수 있다.입력으로 주어진 간선을 처리하여 무방향 그래프를 구성한다.각 정점의 연결 정보를 정렬하여 .. 공감수 1 댓글수 0 2025. 1. 27.
  • b.17298 오큰수 https://www.acmicpc.net/problem/17298   이 문제는 배열의 각 원소에 대해"오큰수(오른쪽에 있는 수 중 현재 수보다 큰 수 중 가장 가까운 것)"를 구하는 문제다.먼저 main 메서드에서 프로그램 실행의 흐름을 살펴보면,사용자로부터 입력값을 받아 배열에 저장한 후 logic 메서드를 호출해오큰수를 계산한 뒤 결과를 출력한다.사용자는 먼저 배열의 크기 N을 입력하고,다음 줄에 배열의 원소를 공백으로 구분하여 입력한다.이후 logic 메서드를 호출하여 오큰수를 계산한다. logic 메서드는 스택을 사용하여 효율적으로 오큰수를 구하는 핵심 부분이다.이 알고리즘은 반복문을 통해 배열을 순회하면서현재 원소와 스택에 저장된 인덱스를 비교한다. 스택에는 아직 오큰수가 결정되지 않은 인덱.. 공감수 1 댓글수 1 2025. 1. 23.
  • b.2293 동전 1 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]) { .. 공감수 1 댓글수 0 2025. 1. 21.
  • b2629. 양팔저울 https://www.acmicpc.net/problem/2629   문제를 풀기 위해서는 dp[][] 의 규칙을 아는것이 가장 편하다.이 문제의 규칙은 다음과 같다.  1. dp[i][j] 는 boolean[N][M] 으로써 i 번째 추까지 사용했을 때 j무게를 확인할 수있는가 없는가를 나타낸다. 또한 N은 추의갯수 M은 가능한 무게측정범위 즉 15001이 된다. 2. dp[i-1][j] 가 true라면 dp[i][j] 또한 true이다. 3. dp[i-1][ K ] 에서 true가 된다면dp[i][K-i번째 추의 절댓값]과dp[i][K+i번째 추의 절댓값]은 15001을 넘지않으면 true이다. 위의 규칙을 활용하여 나는 init method를 통해 초기화 및 입력을 받았으며logic에서 N번째 추를.. 공감수 1 댓글수 0 2025. 1. 17.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.