본문 바로가기

PS832

[자바] 백준 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (java) 문제 : boj18251 필요 알고리즘 개념 스위핑 문제를 단순화 시키면 사실 여러번의 스위핑을 통해 풀 수 있는 문제이다. 다만 이건 내 경우이고, 이 문제는 DP 등 다른 풀이들도 있다. 내가 푼 방식은 스위핑을 이용한 풀이이므로 그걸로 해설을 진행한다. bfs (너비 우선 탐색) 내 경우 트리의 루트부터 주어진 가중치들을 스위핑을 하기 위해 위치 순서대로 정렬하려고 bfs를 사용했다. 꼭 필요한 방식은 아니고, 이 역시 다양한 방식으로 가능하다. 혹시 bfs를 모른다면 이 글을 참고하자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백.. 2022. 9. 6.
[자바] 백준 24498 - blobnom (java) 문제 : boj24498 필요 알고리즘 개념 그리디 좀 생각해보면 그럴 수 밖에 없는 규칙이 보인다. 그 규칙대로 답을 구하면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음과 마지막이 아닌것 중 하나를 선택한다. 그럼 그 좌우는 -1, 중간은 +1이 된다. 그렇다면 각 위치가 서로 연관관계가 있을 수 있을까? 즉, 예를들어 1번째에 대해 문제에서 제시된 '행동'을 하고나서 2번째나 3번째에 대해 '행동'을 하는 .. 2022. 9. 6.
[자바, C++] 백준 2118 - 두 개의 탑 (java cpp) 문제 : boj2118 필요 알고리즘 개념 투 포인터 (두 포인터) 두 개의 가상의 포인터를 두고, 그 두 포인터를 적절한 규칙으로 이동시키다보면 효율적으로 답이 나오게 되는 문제이다. 다만 원형 연결을 끼얹은.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 난 개인적으로 문제 지문 자체가 잘 이해가 안되서 해맸었다. 혹시 그런분이 있을 수 있으니 적어보면, 아래처럼 지점 번호는 중요하지 않고 아무튼 지점 N개가 있는데(녹.. 2022. 9. 6.
[자바] 백준 1174 - 줄어드는 수 (java) 문제 : boj1174 필요 알고리즘 개념 브루트포스 모든 경우의 수를 살펴보는 브루트포스 개념을 알고 있어야 한다. 브루트포스 글 백트래킹 브루트포스에서 모든 경우를 볼 때, 중간에 답이 될 가능성이 없는 부분을 제외시켜 시간복잡도를 낮추는 백트래킹 개념에 대해 알고 있어야 한다. 백트래킹 글 ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이거.. 완전히 동일한 문제가 있다. 그러니 백준 1038 - 감소하는 수 문제 풀이.. 2022. 9. 5.
[자바] 백준 25418 - 정수 a를 k로 만들기 (java) 문제 : boj25418 필요 알고리즘 개념 동적계획법(DP), 너비 우선 탐색(BFS), 탐욕법(greedy) DP, BFS, 그리디 정도가 풀이로 생각나는 문제이다. 셋 다 알아야 하는건 아니고, 셋 중 하나만 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - DP 풀이 dp[x]를 x를 만들기 위한 최소 횟수로 정의하자. 그리고 dp[x]를 모두 무한대로(이 문제의 경우 나올 수 있는 최대수치가 .. 2022. 9. 4.
[자바] 백준 15232 - Rectangles (java) 문제 : boj15232 필요 알고리즘 개념 구현 입출력, 반복문만 알면 풀 수 있는 기본 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 R과 C를 입력받아, C줄에 걸쳐 각각 한줄에 R개의 '*'을 출력해주면 된다. 알고리즘 문제라기보단 단순 구현문제로, 입출력을 어떻게 하는지 한번 생각해보자. 위 '자바로 백준 풀 때의 팁 및 주의점' 링크를 보면 좀 더 효율적으로 입출력을 해볼 수 있다. 코드 : github.. 2022. 9. 3.
[자바] 백준 1214 - 쿨한 물건 구매 (java) 문제 : boj1214 필요 알고리즘 개념 수학, 정수론, 브루트포스 브루트포스로 풀 수 있긴한데, 수학적으로 시간복잡도를 줄여야한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기전에, 혹시 개념이 잘 떠오르지 않는다면 '백준 14916번 : 거스름돈' 을 먼저 풀어보자. dp로도 풀 수도 있겠지만, 브루트포스로 푸는 경우를 생각해보자. 내 경우엔 이와 비슷한 문제를 풀었던 기억이 나서 거기서 시간을 깎아내.. 2022. 9. 2.
[자바] 백준 25516 - 거리가 k이하인 트리 노드에서 사과 수확하기 (java) 문제 : boj25516 필요 알고리즘 개념 bfs(너비 우선 탐색), dfs(깊이 우선 탐색) 기본형태의 탐색문제이다. 이 문제의 경우 거리를 따져야 하므로 일반적으로 생각했을 때 bfs가 기본이지만, dfs로도 가능하다. 아무튼 둘 중 하나만 잘 구현할 줄 안다면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 딱히 뭐 설명이 필요없는 bfs 기본형태의 문제이다. bfs 혹은 dfs에 대해 모른다면 bfs 글.. 2022. 9. 2.
[자바] 백준 2224 - 명제 증명 (java) 문제 : boj2224 필요 알고리즘 개념 플로이드 와샬 (Floyd Warshall) O(N^3)이라 자주 못쓰지만, 쓸 수만 있으면 모든 정점에서 모든 정점으로의 최단경로 파악 혹은 길이 존재하는지 파악이 한방에 가능한 가장 강력한 탐색 알고리즘(대신 느림ㅋ) 플로이드 와샬을 쓸 수 있는 문제이다!! 구현도 엄청 간단하므로 플로이드 와샬을 써보자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a => b 형태일 경우, .. 2022. 9. 2.
[자바] 백준 1647 - 도시 분할 계획 (java) 문제 : boj1000 필요 알고리즘 개념 최소 스패닝 트리 (MST; minimum spanning tree) 너무 대놓고 최소 스패닝 트리 문제이다. MST에 대한 개념이 문제를 푸는데 필요하다. 크루스칼, 프림 MST를 구하기 위한 알고리즘이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 너무 대놓고 MST 구하고, 그 중 가장 큰 간선 하나 제거하라는게 느껴지는 문제라 좀 아쉬웠다. 우선 스패닝 트리란, 모든 정점.. 2022. 9. 2.

티스토리툴바