본문 바로가기

Algorithm

[Algorithm] 백준 2178, 1697 BFS 자바 풀이 안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 BFS에서 비슷한 문제인 백준 2178, 1697번의 자바 풀이를 작성하고자 합니다. BFS는 Queue를 활용하기 때문에 선입 선출로 처리되며 최단 거리를 찾는데 효율적입니다. 문제 링크: https://www.acmicpc.net/problem/2178 문제 링크: https://www.acmicpc.net/problem/1697 코드와 주석으로 먼저 제시한 후, 중요한 포인트를 작성하도록 하겠습니다.! 1. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Queue; import.. 더보기
[Algorithm] 백준 2667, 1012 DFS 자바 풀이 안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 2667, 1012번의 자바 풀이를 작성하고자 합니다. 두 문제 모두 입력 처리만 다르게 하되 동일한 dfs로 해결하는 문제이므로 함께 정리하도록 하겠습니다.! 문제 링크: https://www.acmicpc.net/problem/2667 문제 링크: https://www.acmicpc.net/problem/1012 1. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Collections; import java.util.List; import java.util.ArrayList.. 더보기
[Algorithm] DP - 백준10844 안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 10844번의 계단 오르기 문제를 해결한 과정을 정리하고자 합니다. 해당 문제는 N자리 숫자의 계단 수를 구하는 문제입니다. 1. 문제 해결 과정 1) n == 1일 때, - 한자리 숫자의 경우 1 ~ 9까지 총 9개가 계단수입니다. 2) n == 2 일 때, - 두 자리 숫자의 경우, 총 17개입니다. 12, 23, 34, 45, 56, 67, 78, 89 (8개) 10, 21, 32, 43, 54, 65, 76, 87, 98 (9개) 3) n == 3일 때, - 세 자리 숫자의 경우, 총 32개입니다. 123, 234, 345, 456, 567, 678, 789 (7개) 987, 876, 765, 654, 543, 432, 3.. 더보기
[Algorithm] DP - 백준2579 계단 오르기 이번 포스팅은 백준 사이트의 2579번 계단 오르기 문제를 해결한 과정을 정리하려고 합니다. 해당 문제는 다음과 같습니다. 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.해당 문제는 DP를 활용하여 해결할 수 있습니다. 1. 문제 풀이 과정 밟은 계단은 파랑색, 안 밟은 계단은 회색으로 처리하였.. 더보기
[Algorithm] 백준 11286번 풀이 안녕하세요. 백준 11286번 문제 해결 과정을 정리하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0www.acmicpc.net 1. Priority Queue의 특징높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있습니다.내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(nlogn)PriorityQueue에 객체를 추가하는 방법은 아래 표와 같습니다. 예외 발생값 리.. 더보기

티스토리툴바