본문 바로가기

분류 전체보기114

[백준] 1916. 최소비용 구하기 - Java https://www.acmicpc.net/problem/1916 ⭐️ 중요 포인트1. 이전에 풀었던 "간선 이어가기 2"(https://kyxxgsoo.tistory.com/entry/%EB%B0%B1%EC%A4%80-14284-%EA%B0%84%EC%84%A0-%EC%9D%B4%EC%96%B4%EA%B0%80%EA%B8%B0-2-Java) 문제와 동일하면서도 다른 문제이다. 간선 이어가기 2에서는 한 개의 간선을 이었을 때, 두 노드 모두 간선이 연결되는 무방향 그래프인 반면에 해당 문제는 방향이 정해져있는 단방향 그래프이다. 따라서 addEdge에서 한 방향만 연결해주어야 한다.3. 내가 실수했던 부분 중 하나는 compare를 Override할 때 return시 잘못 반환해서 메모리 초과가 났었다.. 2025. 5. 21.
[백준] 14284. 간선 이어가기 2 - Java https://www.acmicpc.net/problem/14284다.시.풀.어.보.기! ⭐️ 중요 포인트1. 다익스트라로 해결하는 문제이다. 다만 인접 행렬로 풀 경우 행렬의 크기가 현재는 5000x5000이라 풀 수 있겠지만, 낭비되는 공간도 많을 뿐더러, n이 한 자릿수만 더 추가되더라도 인접 행렬로 풀 수 없기 때문에 Map에 노드의 번호와 해당 노드에 연결된 리스트를 넣는 방법으로 문제를 해결하였다.2. PritorityQueue를 사용하는 이유 : 해당 pq는 현재까지의 노드 도달 상황에서 접근할 수 있는 아직 방문하지 않는 노드 중 가장 가중치가 작은(가까운) 정점을 거리순으로 꺼내기 위해서 사용한다.3. distants라는 Map의 경우 n이 작을 때는 1번 포인트와 마찬가지로 행렬로 풀 .. 2025. 5. 20.
[백준] 14891. 톱니바퀴 - Java https://www.acmicpc.net/problem/14891 이 문제는 다 풀어놓고 삽질을 많이 했다...첫 톱니바퀴가 돌아간 후 다음 톱니바퀴와 극이 서로 다르지 않으면 전파가 되면 안되는데, 그것과는 상관없이 그 다음 톱니바퀴로 넘어가 극이 다르면 돌려버려서 이 부분을 찾느라 한참 애를 먹었다... ⭐️ 중요 포인트1. 사실 환형 배열을 사용하여 인덱스로 구해도 됐을 것 같지만, 인덱스를 계산하는게 귀찮고 머리아플 것 같아 Deque 두 개를 이어붙여 Gear를 만들었다. 이 때, highGear는 9시 방향부터 시계방향으로 4개, lowGear는 3시 방향부터 시계방향으로 4개로 선정했다.그렇게 한 이유는 윗 기어와 아랫 기어의 First와 Last를 서로 이어 순환시키며 실제 기어의 움직.. 2025. 5. 14.
[프로그래머스] 연속 부분 수열 합의 개수 - Java https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr ⭐️ 중요 포인트1. 일단 3중 포문을 사용해서 완탐으로 문제를 해결할 수 있다.2. 그러나 완탐으로 해결하게 되면 중복된 경우(startIdx가 0부터 시작해서 len이 1, 2, 3, ..., n까지라고 할 때 (1), (1+2), (1+2+3), ... 처럼)가 계산된다.3. 문제는 해결되지만 좀 더 빠른 방법으로 구현하기 위해서 elements의 길이만큼 cache를 선언하여 누적합을 구해 set에 넣으면 중복을 줄일 수 있다.(0번째.. 2025. 5. 13.
[백준] 5430. AC - Java https://www.acmicpc.net/problem/5430 ⭐️ 중요 포인트1. 문자열 파싱 -> String.split() + 정규 표현식(",|\\[|\\]")을 통해 해결(이 때, 정규 표현식은 (,) or ([) or (]')를 기준으로 나누고, 맨 앞에 공백이 있기 때문에 deque에 넣을 때는 인덱스가 0이 아니라 1부터 넣어야 한다.)2. 🔥제일 중요🔥 이 문제에서 가장 많이 틀리는 부분일 것이다. 이 부분때문에 시간초과가 많이 난다.이 문제에서 가장 많은 연산량을 차지하는 부분은 reverse() 부분이다. Java의 경우 O(N)이다.t : 100 / p : 100,000 / n : 100,000(R과 D가 번갈아 나오는 경우가 최악의 경우이다. 왜냐하면 연속된 R이 나오면 나.. 2025. 5. 13.
[백준] 15686. 치킨 배달 - Java https://www.acmicpc.net/problem/15686 ⭐️ 중요 포인트1. 처음에 city를 입력받을 때, 집(개수만 저장해도 됨)과 치킨집의 위치(추후 m개를 선택할 때 사용)를 List에 저장.2. dfs를 돌며 m개의 치킨집을 선택 후, 해당 치킨집들을 시작점으로 하는 bfs를 돌며 집을 모두 방문할 때까지 탐색.(집을 방문할 때마다 bfs를 통해 구한 최소 거리들을 누적해서 반환)3. answer과 bfs를 돌며 얻은 반환 값을 비교하며 더 작은 값을 answer로 갱신. import java.io.*;import java.util.*;public class P15686 { static class Pos { int x; int y; int .. 2025. 5. 13.

티스토리툴바