알고리즘27 [알고리즘] BOJ 3197 백조의 호수 (JAVA) https://www.acmicpc.net/problem/3197 백준 플레5 난이도의 문제로, 전형적인 bfs문제의 형태를 띄면서도 시간단축이 필요한 문제였다. 한 백조 위치에서 다른 백조 위치에 도달할 수 있는지 bfs 탐색 -> 실패 시 빙판이 녹는 과정 실행 이와 같은 순서로 구현했고, 물 녹는 과정을 실행할 때 전체 물 범위가 아닌 이전에 녹았던 지점들의 좌표값을 저장해두고 해당 좌표들에 한해 인접한 지역의 빙판이 녹는 식으로 시간 단축을 시켰다. import java.io.*;import java.util.*;public class boj3197 { static int R, C, time; static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 9. 16. [알고리즘] BOJ 2812 크게 만들기 (JAVA) https://www.acmicpc.net/problem/2812 백준 골드3 난이도의 문제로, 문제 지문을 읽어보면 그리디의 느낌이 많이 났던 문제였다. K개의 숫자를 지우고 새로 만든 숫자가 최대가 되게 하는 것이 문제였는데, 숫자를 재배치하지 않기 때문에 앞쪽의 위치한 숫자가 가능한 만큼 큰 숫자를 배치해야 했다. 비교하면서 최대한 큰 수들을 앞쪽에 배치하도록 하기 위해서 stack 방식으로 맨 위의 값을 비교하며 stack에 넣어주는 형태를 사용했고, 스택 방식으로 작동하지만 마지막 최종 값을 출력할때 용이하게 하기 위해서 자료구조 자체는 덱을 사용했다. import java.io.*;import java.util.*;public class boj2812 { static int N.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 6. 22. [알고리즘] A* 알고리즘(A star 알고리즘)이 뭘까? A* 알고리즘이란? 그래프의 최단 경로를 찾기 위한 알고리즘으로, 다익스트라 알고리즘(Dijkstra' algorithm)과는 달리 예상 이동 비용인 휴리스틱(Heuristic) 거리값 h(n)이 사용된다는 차이점이 있다. 휴리스틱 거리값은 사전에 임의로 설정하는 값이고, 목표 위치까지의 거리 값을 유클리드 거리 혹은 맨하탄 거리 값 등을 활용하여 사전에 설정하는 값이다. 휴리스틱 코스트 값은 다음과 같은 식이 성립된다. 휴리스틱 코스트 값 F(n) = 출발 지점부터 해당 위치까지의 비용 G(n) + 휴리스틱 거리 측정값 H(n) 해당 휴리스틱 코스트 값을 기반으로 가장 작은 값을 가지는 위치를 순차적으로 탐색하는 것이 바로 A* 알고리즘이다. 다익스트라 알고.. 알고리즘/알고리즘 이론정리 2024. 6. 14. [알고리즘] BOJ 2437 저울 (JAVA) https://www.acmicpc.net/problem/2437 백준 골드2 난이도의 문제로, 오랜만에 문제 풀면서 머리를 좀 많이 쓴 문제가 아니었나 싶다. 우선 문제를 보면, 배낭 문제와 비슷한 형태를 띄고 있다. 그래서 일단 그리디 문제라는 것은 어느 정도 유추가 가능했다. 문제를 풀기 위해 조건을 좀 찾아봤다. 우선 문제 풀면서 메모장에 적어놨던 첫번째 예시를 가져왔다. an은 무게 추가 정렬되었을 때 n번째 추를 의미하고, SN은 n번째 무게추까지의 누적 무게 합을 의미하고, 그 옆은 부분 집합을 의미한다. 위의 예시에서는 무게추가 순서대로 1,2,4,9인 순서대로 확인한다. 무게 추를 추가할때마다 누적합과 부분 집합에 해당되는 값들을 확인하면, 다음을 알 수 있다. an .. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 6. 13. [알고리즘] BOJ 16236 아기 상어 (JAVA) https://www.acmicpc.net/problem/16236 백준 골드3 난이도인 문제로, 문제를 읽으면 눈치채기 쉽겠지만 bfs 기반 구현 문제이다. 가장 가까운 거리를 기반으로 이동하면서, 해당 위치에 있는 물고기를 먹을 수 있는 경우 먹고, 성장까지 해야하므로 Pos 클래스를 만들어 위치값(x,y)와 출발 지점으로부터의 거리를 저장했고, 해당 Pos값의 거리를 비교하고 같은 경우 x값, x값도 같은 경우 y값을 비교하여 다음에 접근할 위치를 탐색할 수 있도록 클래스를 선언했고, 이를 PriorityQueue를 통해 만족하는 값을 순차적으로 탐색하면서 만약 현재 위치에 먹을 수 있는 물고기가 있는 경우, 새로운 탐색을 시작해야하므로 PriorityQueue의 값과 isVisit.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 6. 11. [알고리즘] BOJ 11780 플로이드2 (JAVA) https://www.acmicpc.net/problem/11780 백준 골드2의 문제로, 문제 이름에서부터 알 수 있듯 플로이드워셜을 활용한 문제였다. 플로이드 워셜을 통해 모든 도시 간의 최단 거리를 갱신하는 과정에서, 최단 거리의 갱신이 발생하는 경우, 경로또한 기존에 저장된 경로를 삭제하고 갱신이 발생하게 된 최단 거리 방식을 합치는 식으로 구현했다. route[i][j]는 i에서 j로 가기위한 도시를 출발지 i부터 순서대로 담은 리스트이며, 해당 리스트를 통해 경로를 출력하고, 해당되는 거리가 0이거나 초기값인 INF인 경우 갈 수 없다는 것을 의미하므로 0을 출력해주는 방식으로 구현했다. import java.io.*;import java.util.*;public class bo.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 6. 4. [알고리즘] BOJ 17182 우주 탐사선 (JAVA) https://www.acmicpc.net/problem/17182 백준 골드3으로 설정된 문제였다. 모든 행성 간의 소요 시간을 확인하기 위해 플로이드 워셜을 통해 시간을 구해두고, 백트래킹을 통해 모든 행성을 탐사하며 최단 거리를 갱신하는 방식으로 구현했다. import java.io.*;import java.util.*;public class boj17182 { static int N, K, result; static int dist[][]; static boolean isVisited[]; public static void backTracking(int src, int sum, int depth) { if (depth == N - 1) { .. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 6. 2. [알고리즘] BOJ 11265 끝나지 않는 파티 (JAVA) https://www.acmicpc.net/problem/11265 백준 골드5로 난이도가 설정된 문제였다. 문제 지문에서 잡다한 내용을 다 빼고 보자면, 결국 A -> B 이동시 C 시간 이내로 올 수 있는지 없는지 출력해주면 된다는 것이었다. 도로는 일방통행이고, A와 B는 1 이상 N 이하의 모든 값이 될 수 있기 때문에 모든 정점에 대해 최단거리를 구하는 플로이드워셜 알고리즘을 사용했다. 보통의 플로이드워셜 문제가 INF 값을 임의로 설정하고 최단거리를 구하는 방식으로 구하는 반면에, 이 문제는 모든 정점 간의 거리가 입력으로 주어져서 딱히 그럴 필요가 없었다. import java.io.*;import java.util.*;public class boj11265 { stati.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 5. 28. [알고리즘] 2022 KAKAO TECH INTERNSHIP 코딩테스트 공부 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제는 정확성과 효율성을 모두 고려해야하는 문제였다. 알고력과 코딩력을 기준치만큼 최소한의 시간 안에 도달해야하는 문제였고, 문제를 풀고 나서는 최단거리 형태로도 풀 수 있지 않을까 생각이 들긴 했지만, 우선은 전형적인 dp 문제라는 생각이 들어, dp 배열을 선언하여 문제를 해결했다. dp[i][j]는 알고력 i와 코딩력 j를 도달하기 위한 최단 시간을 나타내는 배열이고, dp 배열의 크기는 .. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 4. 25. [알고리즘] 2022 KAKAO BLIND 양과 늑대 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2진 트리 형태로 되어있고, 양의 수 > 늑대의 수를 유지하며 최대한 많은 양을 확보해야하는 문제이다. 처음에는 우선 순위 큐와 유니온 파인드를 활용하여 풀어볼라 했지만, 아이디어를 얻기 힘들어 다른 방식을 생각했다. 기본적으로 DFS 방식으로 시작 위치인 0번째 노드부터 탐색을 시작하며 양인지 늑대인지 확인 후 양인 경우 최대로 모인 양의 수와 비교하며 갱신하고, 늑대의 수가 양의 수와 같아지는 경.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 4. 17. [알고리즘] 2022 KAKAO BLIND 파괴되지 않은 건물 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명에서도 강조되어 있듯, 효율성을 강조하는 문제이다. 구간별로 공격 또는 회복하여 건물의 내구도 값의 변화가 발생하고, 이러한 형태의 문제는 아마 백준 문제를 많이 풀었다면 자주 봤을 누적합 형태의 문제였기 때문에 누적합을 활용하여 문제를 풀었다. 공격 또는 회복이 반복되는 회수는 skill 배열의 길이와 같기 때문에, 해당 길이만큼 반복문을 돌면서 각각의 skill에 맞는 값들을 합산해뒀다.. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 3. 27. [알고리즘] 2022 KAKAO BLIND k진수에서 소수 개수 구하기 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 조건에 따르면, 0을 기준으로 구분하여 만들어진 숫자 중 소수가 몇 개인지 구분해야 한다. N을 K진수 String으로 변환한 뒤, StringTokenizer를 통해 소수인지 여부를 확인하는 식으로 구현했고, N을 K진수로 변환할 때 Integer.parseInt(N,K)를 활용하는 방식 또한 있는데, 해당 문제를 풀 때 그 방식을 깜빡하여(...) K진수 변환을 직접 구현했다. 또한 소수 판정을 .. 알고리즘/알문풀(백준, 프로그래머스, 코드트리) 2024. 3. 14. 이전 1 2 3 다음