본문 바로가기

PS818

[자바] 백준 17616 - 등수 찾기 (java) 목차 문제 : boj17616 필요 알고리즘 그래프 이론, 그래프 탐색 (bfs, dfs) A와 B의 관계를 단방향 그래프로 볼 수 있는 직관이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 너비 우선 탐색(BFS)을 모른다면 '이 글'을 참고해보자. 문제로 주어진 부분을 그래프로 변경해 생각해보는 아이디어가 필요한 문제로, 교육적으로도 상당히 좋은 문제라 생각된다. 우선 'A가 학생 B보다 더 잘했다.. 2023. 8. 11.
[자바] 백준 11912 - 격자 보존하기 (java) 목차 문제 : boj11912 필요 알고리즘 그리디 알고리즘 규칙만 찾으면 쉽게 접근 가능하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어만 떠오르면 어렵지 않은 문제이다. 말이 있을 때, 격자를 놓을 수 있는 경우의 수를 생각해보자. 사실 이것만 생각나면 끝인 문제이다. 1. 첫 번째 말 앞에 1개의 격자를 두는 경우 -> 문제 내에서 1번만 가능 2. 마지막 말 뒤에 1개의 격자를 두는 경우 -> 문제 내에서.. 2023. 8. 11.
[자바] 백준 2138 - 전구와 스위치 (java) 목차 문제 : boj2138 필요 알고리즘 그리디 (탐욕법, greedy) 하나의 규칙을 적용해 최선의 답을 도출해낼 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 만약 i번 스위치를 누르면 i번 스위치만 변경된다고 해보자. 이 경우 000 에서 010 으로 만들려면 어떻게 해야 할까? 자명하게도 그냥 좌측부터 서로 비교해보면서 서로 다른걸 누르면 되므로 1번만 누르면 된다. 그럼 i번 스위치를 누르면 i.. 2023. 8. 11.
[자바] 백준 11066 - 파일 합치기 (java) 목차 문제 : boj11066 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법), 누적합 분할정복 느낌으로 생각해보면 풀이법을 찾을 수 있다. 그리고 구현을 위해 DP와 누적합을 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선, 이 문제의 경우 연속된 파일끼리만 합칠 수 있다는 점을 주의해야 한다. 만약 아무 파일이나 합칠 수 있었다면 그리디로 매번 합쳐진 파일들 중 가장 가중치가 낮은 2개를 합치.. 2023. 8. 10.
[자바] 백준 14550 - 마리오 파티 (java) 목차 문제 : boj14550 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법) 동적 계획법으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 '여러 줄에 걸쳐 N개의 정수가 주어진다.' 부분 때문에 입력 받는게 상당히 까다로울 수 있다. 자바로 어떻게 입력받아야할지 모르겠다면 이하 코드의 main 함수를 참고해보자. 내 경우 main에서 알아서 입력받은 뒤 solution 함수에 n, s.. 2023. 8. 9.
[자바] 백준 14938 - 서강그라운드 (java) 목차 문제 : boj14938 필요 알고리즘 플로이드-워셜 (floyd-warshall) 플로이드 워셜을 안다면 쉽게 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 플로이드 워셜은 O(N^3)인 알고리즘이지만, 모든 정점에서 모든 정점으로의 최단거리를 알 수 있어서 아주 강력한 알고리즘이다. 심지어 코드도 엄청나게 간단하고 이해하기도 직관적이라 익히기도 쉽다! 모른다면 이번 기회에 익혀보자. 물론 다익.. 2023. 8. 8.
[자바] 백준 1311 - 할 일 정하기 1 (java) 목차 문제 : boj1311 필요 알고리즘 bit DP (비트 필드를 이용한 다이나믹 프로그래밍) 비트 단위 DP로 푼 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 좀 더 간소화시켜서, N이 항상 3이라고 해보자. 이 때 dp[A][B] 를 A번 사람을 B라는 일의 조합으로 진행한 경우 비용의 최솟값이라고 정의하자. 이 경우 B는 3개의 일을 가지고 할 수 있는 모든 경우를 나타낼 수 있으면 된다. 0. .. 2023. 8. 3.
[자바] 백준 1956 - 운동 (java) 목차 문제 : boj1956 필요 알고리즘 플로이드-워셜 (floyd-warshall) 다른 그래프 탐색 알고리즘으로 되긴 하겠지만, 이 문제는 플로이드 워셜이 매우 편하긴 하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단방향 그래프에서 '1번 마을에서 1번 마을로 가는 최소 거리, 2번 마을에서 2번 마을로 가는 최소 거리, ... , V번 마을에서 V번 마을로 가는 최소 거리' 중 최소값을 출력하면 되는 문제이다... 2023. 8. 3.
[자바] 백준 11812 - K진 트리 (java) 목차 문제 : boj11812 필요 알고리즘 최소 공통 조상 (LCA) LCA 문제이다. 근데 몰라도 푸는데 딱히 지장은 없다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 LCA를 안다면 그걸로 바로 접근 가능하고, 몰라도 딱히 상관은 없다. 어차피 첫 깊이엔 1개, 두번째 깊이엔 K개, 세번째 깊이엔 K^2개, ... 의 노드가 존재할꺼다. 그러므로 x와 y를 입력받을 시, K로 나누다보면 점점 부모 노드의 번호를 알 .. 2023. 8. 3.
[자바] 백준 1103 - 게임 (java) 목차 문제 : boj1103 필요 알고리즘 깊이 우선 탐색, DP, 사이클 판정 memoization을 통해 연산 횟수를 줄이면서 DFS를 진행하는 문제이다. 또한 사이클 판정하는 방법도 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 로직을 말로 하면 간단하다. 1. 가장 왼쪽 위부터 DFS를 진행한다. 2. 사이클이 한번이라도 생기는 경우 -1을 출력하고 끝낸다. 3. 사이클 없이 가장 멀리 간 거리를 .. 2023. 7. 26.

티스토리툴바