본문 바로가기

BOJ749

[자바] 백준 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.
[자바] 백준 17081 - RPG Extreme (java) 문제 : boj17081 ... (생략) 필요 알고리즘 개념 구현 알고리즘 지식은 따로 필요없고, 제시된대로 구현하면 된다. 다만 구현만 하면 되는데 플래인.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 지문양만 봐도 풀어볼 생각을 하려면 많은 용기가 필요하다(?). 순수 구현 문제로 플래티어를 받은 전설의 문제이다. 풀이가 필요없다.. 정말 문제에 제시된대로 구현만 하면 된다. 정답 떠서 이렇게 기쁜 문젠 오랜만이.. 2022. 9. 1.
[자바] 백준 5214 - 환승 (java) 문제 : boj5214 필요 알고리즘 개념 BFS (너비 우선 탐색) 너비 우선 탐색 문제이다. 다만 간선 설정이 어려운걸 끼얹은.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 그냥 생각해보기 문제 자체는 정점과 간선이 주어지고 그냥 BFS를 돌리면 되는 간단한 문제이다. 다만 이 간선이 한번에 K개씩 주어진다는게 문제이다. 즉, 로직 자체는 BFS면 되지만 간선을 어떻게 저장해둘지가 핵심인 문제이다. BFS를 모른다면 이 글.. 2022. 8. 30.
[자바] 백준 1244 - 스위치 켜고 끄기 (java) 문제 : boj1244 필요 알고리즘 개념 시뮬레이션 (구현) 주어진 대로 구현만 가능하다면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주어진대로 구현만 해주면 된다. 로직은 다음과 같다. 1. 스위치 개수 n을 입력받아 해당하는 크기의 배열을 만든다. 그리고 n개의 현재 상태를 입력받아 배열에 넣어둔다. 이 때 어차피 스위치가 켜져있는지 꺼져있는지만 알면 되므로, int 배열로 해도 되고 bool.. 2022. 8. 30.
[자바] 백준 17554 - City of Lights (java) 문제 : boj17554 필요 알고리즘 개념 시뮬레이션 (구현) 주어진 대로 구현만 할 줄 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 영어 독해 문제이다. 영어를 잘 해석해서 그대로 구현만 해주면 되는 시뮬레이션 문제이다. 로직은 아래와 같다. 1. 크기 N을 입력받아 배열을 만들고 불빛을 모두 켠 상태로 초기화한다(boolean[]으로 하던지 int[] 로 하던지 뭘로 하던 상관 없다. 켠걸 뭘로 표.. 2022. 8. 30.
[자바] 백준 1343 - 폴리오미노 (java) 문제 : boj1343 필요 알고리즘 개념 그리디 사전순으로 가장 앞서는 답을 출력해주기 위해, 각 연속된 X 집합들의 갯수를 기준으로 최대한 AAAA를 앞에 나오도록 해야 한다. 이런식으로 일정한 규칙을 정해 적용시키다보면 답이 나오는 그리디 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '.'은 답을 구하는데 영향을 끼치지 않는다. 연속된 'X' 집합만 생각해보자. 다음을 생각해보자. ...XXXXXXXXXX... 2022. 8. 30.
[자바] 백준 23757 - 아이들과 선물 상자 (java) 문제 : boj23757 필요 알고리즘 개념 우선순위 큐 (priority queue) 또는 max heap 우선순위 큐로 시작해서 우선순위 큐로 끝나는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 대놓고 우선순위 큐(이하 pq) 문제이다. 다만, 가장 큰 값부터 꺼내져야하므로 pq 또한 최대값을 기준으로 꺼내질 수 있도록 해줘야 한다. 자바의 경우 new PriorityQueue(Collections.rever.. 2022. 8. 30.
[자바] 백준 2548 - 대표 자연수 (java) 문제 : boj2548 필요 알고리즘 개념 정렬 데이터를 정렬하는 방법을 알아야 한다. 누적합 누적합을 사용해 이 문제를 풀 수 있다. 수학 - 중앙값(median) 누적합을 사용하지 않고, 수학의 중앙값 개념으로도 이 문제를 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이1 : 누적합 + 카운팅 정렬을 이용한 풀이법 cnt[x]를 입력으로 주어진 N개의 수(1~10000)에 대해, x가 입력으로 들어온 횟수라고.. 2022. 8. 30.
[자바] 백준 12738 - 가장 긴 증가하는 부분 수열 3 (java) 문제 : boj12738 필요 알고리즘 개념 LIS (Longest Increasing Subsequence; 가장 긴 증가하는 부분 수열) LIS 알고리즘을 사용해 푸는 문제이다. 이분탐색, 매개변수 탐색법(parametric search) LIS 알고리즘 구현을 위해 가장 중요한건 이분탐색에서 그보다 큰 가장 작은 값 혹은 그보다 작은 가장 큰 값을 알 수 있는 매개변수 탐색법이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.. 2022. 8. 29.

티스토리툴바