백준26 [BOJ] 백준 16637번 - 괄호 추가하기(with Java) 알고리즘 브루트포스로 접근해서 풀어보다가 못풀고 시간만 보낼것 같아서 결국 구글링했다. 문제 분류에는 브루트포스만 적혀있지만 DFS + 재귀 조합을 통해서도 풀 수 있었다. '괄호를 채워넣지 않는 경우(1)'와 '괄호를 채워넣는 경우(2)' 2가지로 나눠볼 수 있겠다. (1)의 경우에는 total로 넘겨준 값을 유지하면서 오른쪽의 숫자들을 계속 연산해준다. (2)의 경우에는 total의 바로 뒤에 오는 숫자들에 대해서 먼저 연산해주고, total을 유지한채 다음 DFS를 수행한다. 만약에 주어진 연산자들을 모두 사용하면 total과 max값을 갱신시켜준다. 이후에 다음 DFS를 수행하지 않고 함수를 빠져나오면 된다. 예시 예제로 주어진 입력1의 '3+8*7-9*2'를 살펴보자. 괄호를 추가하지 않고 이 .. 2022. 1. 5. [BOJ] 백준 9205번 - 맥주 마시면서 걸어가기(with Java) 알고리즘 아이디어를 떠올릴 수 있다면, Floyd-Warshall 알고리즘을 이용해서 간단하게 BFS로 풀 수 있는 문제이다. 설계를 잘했다면 문제를 푸는 방법은 매우 간단하다. 우선, 각각의 위치를 정의해줘야만 하는데 좌표가 음수가 될 수도 있으므로 배열을 이용한 풀이는 어렵다. 따라서 현재 위치 x, y 좌표와 해당 위치의 방문 여부 정보 및 시작점과의 거리 정보를 담고 있는 클래스를 만들어준다. 또한, 모든 편의점과 목적지는 시작점과의 거리 정보를 무한대로 설정해주고 각각의 객체들을 리스트에 넣어준다. 이제부터 각각의 정점들에 대해서 BFS를 수행하면 되지만, 여기서 고려해줘야할 사항이 하나 있다. 문제에서 주어진 '맥주 한 박스에는 맥주가 20개 들어있다', '50미터를 가려면 그 직전에 맥주 한.. 2021. 12. 15. [BOJ] 백준 18310번 - 안테나(with Java) 알고리즘 잘못된 아이디어를 떠올려서 시간초과가 난 이유에 대해서 고민하다가 결국 풀지 못하고 구글링을 통해서 해결하였다. 처음에는 각각의 집에 대해서 다른 집들과의 거리의 합을 비교해서 합이 최소인 집을 구하는 방식으로 접근하였다. 하지만 입력이 최대 20만에 도달했기 때문에 시간복잡도는 O(N^2)로 시간초과가 나게 돼서 풀이에 실패하였다. 구글링을 통해서 다른 사람들이 푼 코드를 참고해보니 풀이가 의외로 간단하였다. 집들을 전부 오름차순으로 정렬시킨 후에 중간에 위치한 집을 찾는 것이 전부였다. 알고리즘을 위와 같이 짜게 되면, 어떤 테스트케이스가 주어져도 각각의 집에 대한 합이 최소값을 이루게 된다. 소스코드 문제링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200.. 2021. 12. 14. [BOJ] 백준 1874번 - 스택 수열(with Java) 알고리즘 풀이 시간이 상당히 오래걸렸다. 우선 리스트를 만들어서 입력받은 스택 수열을 하나씩 집어넣는 것으로 시작하였다. 처음에는 스택에 push, pop하는 과정을 통해서 연산을 뽑아놓고, 그 연산으로 다시 스택 수열을 만들어서 입력을 받은 리스트와 비교를 했기 때문에 과정도 번거롭고 시간복잡도가 크게 나왔다. 어떤 부분을 생략해서 시간복잡도를 줄일 수 있을까 고민한 끝에 비교하는 방식이 문제지 않을까하는 생각을 하게 됐다. 따라서 비교하는 방식을 과감하게 삭제하고 1부터 N까지의 숫자에 대해서 스택에 푸시를 하는데, 스택에 쌓인 모든 숫자에 대해서 맨 위에 있는 숫자가 현재 리스트가 가리키는 숫자와 일치하는 경우에만 스택으로부터 팝을 해주었고 리스트가 가리키는 숫자를 바꿔줘서 조건을 만족할 때까지 계.. 2021. 12. 14. [BOJ] 백준 14916번 - 거스름돈(with Java) 알고리즘 문제에서 궁극적으로 구하고자 하는 답은 거스름돈 N이 주어질 때, 거슬러주는 동전의 최소 개수이다. 따라서 다른 DP 문제들과 마찬가지로 N 이하에서의 DP 값을 모두 알아야만 한다. 이 문제에서 알아둬야할 부분은 '손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다' 이다. 다시 말해서 2원 또는 5원으로 거슬러줄 수 없는 경우가 존재한다는 뜻이며, 이 경우에는 -1을 넣어줘야만 한다. dp[0]을 구해보자. dp[0]은 거스름돈 0이 주어질 때, 거슬러주는 동전의 최소 개수이다. 하지만 거스름돈이 0이라면 거슬러줄 필요가 없으므로 거슬러주는 동전의 최소 개수는 0, 즉 dp[0] = 0이다. dp[1]은 거스름돈 1이 주어질 때, 거슬러주는 동전의 최소 개수이다. 거스름돈이 1인 경우에는 .. 2021. 12. 5. [BOJ] 백준 2293번 - 동전 1(with Java) 알고리즘 지난번에 풀었던 [BOJ] 백준 11047번 - 동전 0 문제와는 다르게 욕심쟁이 알고리즘이 아닌 '동적계획법'을 사용해야만 문제가 풀린다. 우선 K번째까지의 경우의 수를 구하는 것이 목표이므로 DP 배열의 크기를 K+1로 잡아주고 dp[0]을 1로 초기화해준다. 0이 아닌 1로 초기화를 해주는 이유는 동전을 아예 사용하지 않는 경우도 경우의 수에 포함된다고 봐야하기 때문이다. 다음으로 이중 for문을 통해서 알고리즘이 수행된다. dp[j]는 첫번째부터 j번째까지의 동전을 사용했을 때 합이 K원이 되도록 만드는 경우의 수이다. 예를 들어서, 동전 각각의 가치가 2원 3원 5원이고 가치의 합이 10원이라고 해보자. 첫번째로 dp[j]는 2원짜리 동전으로 2원부터 10원까지 만들 수 있는 경우의 수.. 2021. 8. 2. [BOJ] 백준 11047번 - 동전 0(with Java) 알고리즘 욕심쟁이 알고리즘의 대표적인 문제로 원래는 동적계획법을 사용해야 최적의 해를 도출할 수 있지만, 주어지는 동전이 특이하기 때문에 욕심쟁이 알고리즘을 사용해야만 최적의 해를 도출할 수 있다. 왜 그런지는 추후에 설명하기로 하겠다. K원보다 작거나 같은 경우에 대해서 동전의 값을 빼고 K를 업데이트하는 과정을 K가 0이 될 때까지 반복해주면 풀 수 있다. 문제에서 요구하는 것은 K원을 최소로 만드는 동전의 개수이므로, 횟수를 세기 위한 변수 cnt를 이용해서 K에서 값을 빼줄 때마다 cnt를 1씩 증가시켜주면 문제에서 요구하는 답을 도출할 수 있다. 소스코드 문제링크 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개.. 2021. 8. 1. [BOJ] 백준 11403번 - 경로 찾기(with Java) 알고리즘 다른 문제들과는 다르게 입력이 인접리스트가 아닌 인접행렬로 주어지는데, 필자는 인접행렬보다 인접리스트로 문제를 푸는 방식이 더 익숙해서 인접행렬을 입력받은 후에 인접리스트로 바꿔주었다. 여태까지 만나본 그래프 문제들은 모두 방향성이 없는 무방향 그래프였는데, 이 문제의 경우에는 방향 그래프를 사용하여 경로를 구하도록 했기 때문에 어렵게 느껴졌다. 아래에 인접리스트와 그래프를 도식화시킨 그림을 나타내보았다. 입력받은 인접행렬을 인접리스트로 바꿔주면 각각의 정점들에 대해서 DFS 알고리즘을 적용하면 된다. 일반적인 DFS 알고리즘은 현재 정점에 대해서 방문했음을 표시해주고, 인접한 정점들에 대해서 방문 여부에 따라 DFS 알고리즘을 재귀적으로 수행한다. 하지만 이 문제는 정점 i가 정점 i에 도착한.. 2021. 7. 25. [BOJ] 백준 1904번 - 01타일(with Java) 알고리즘 N=1부터 N=8까지의 각각의 경우에 대해서 만들 수 있는 가짓수를 계산해보면 아래와 같이 도출된다. 결과를 보게 되면 3번째항부터는 이전 항과 그 이전 항을 더해서 만들어지는 피보나치 수열임을 알 수 있다. 따라서 N=1, N=2일 때는 정답을 각각 1과 2로 출력해주고, N=3 이상부터는 i-2번째와 i-1번째 항을 더해서 i번째 항을 구하면 된다. N은 최대 백만까지 가능하므로 15746으로 나눠줘야만 하는데, 정답을 도출할 때 나눠주게 되면 이미 오버플로우가 발생한 상태로 결과가 나오게 된다. 이를 방지하기 위해서는 i-2번째 항과 i-1번째 항을 합해준 후에 15746을 나눈 값으로 i번째 항을 구해주면 문제가 해결된다. 소스코드 문제링크 1904번: 01타일 지원이에게 2진 수열을 가.. 2021. 7. 19. [BOJ] 백준 11724번 - 연결 요소의 개수(with Java) 알고리즘 정점과 간선을 입력받아서 인접리스트를 만들고 각각의 정점에 대해서 DFS 알고리즘을 수행하면 된다. 연결 요소의 개수를 세기 위한 변수 cnt를 생성하여 DFS 메소드를 빠져나올 때마다 cnt를 증가시키는 방식으로 연결 요소의 개수를 세면 정답이 도출된다. 소스코드 문제링크 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2021. 7. 19. 이전 1 2 3 다음
