문제 난이도GOLD II (문제 링크)  풀이사칙연산에서의 연산 우선순위의 특징과 스택을 활용해서 풀 수 있다. 다들 알겠지만 리마인드하고 넘어가자면,1. 곱셈과 나눗셈은, 덧셈과 뺄셈보다 우선으로 연산된다.2. 괄호가 존재할 경우, 가장 먼저 처리된다.3. 우선순위가 같을 경우, 좌결합성의 특성에 따라 왼쪽의 수식을 우선처리한다.   또한 문제의 예제와, 그림표기된 것을 보고도 방법을 캐치할 수 있는데,   사칙 연산의 우선순위 특징을 리마인드했고, 어떻게 문제를 풀어나가야할지 통해 정리해볼 수 있다. 연산은 선출력하는 것이 아니라, 이전 연산자가 존재할 경우, 이전 연산과의 우선순위를 판별해서 출력 여부를 결정해야한다.괄호는 우선 연산이 되기때문에, 괄호 시작 부분을 만났을 경우에, 괄호가 끝나는 시..

문제 난이도GOLD II (문제 링크)   풀이두 노드 간의 최장 경로인 트리의 지름을 구하는 문제이다. 모든 경우의 수를 구해서, 가장 큰 값을 찾아야하기 때문에 DFS에 적합하다. DFS 구현은 단순하니 이를 통해 문제를 쉽게 해결할 수 있다.//dfs 호출부int max = 0;for (int i = 1; i     메모리 초과는 단순 이차원 배열을 통해 각 노드의 경우의 수를 계산했기 때문에 발생했다.이는 리스트로 구현하여 해결하였다.  하지만, 모든 경우의 수를 구하면 시간 초과가 발생하는데, 모든 경우의 수를 구하게 되면 O(V^2)이 되며, 문제 조건에서 V가 100,000까지이기 때문에 최적화할 수 있는 방법이 필요하다. 임의의 노드 x에서 최장 경로 노드를 DFS를 통해 구했고, 이를 y..

문제 난이도GOLD III  문제 링크https://www.acmicpc.net/problem/1238   풀이 [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com 위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.    문제 예시를 그림으로 표현해보았다.목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A) private static int[] dijkstra..

문제 링크 Gold 4 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 첫 풀이 크게 시간, 메모리 고려를 하지 않아도 될 것 같아보여서 뇌를 빼고 풀어보려고 했다. (사실 Union Find에 자신이..) 단순 String배열을 활용하고, List에 String배열을 저장하여 정답을 도출하려고 했고, 문제에서 제공하는 테스트케이스를 만족해서 됐다!!! 라고 생각했다. import java.io.BufferedReader; import java.io.IO..

문제 링크 Gold 5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 필자는 BFS를 이용해 풀었으며 실버 DP문제들 보다 난이도가 쉬운 것 같다. 처음에는, BFS 메서드를 통해 한 번 완전탐색을 끝낸 후 바로 결과를 도출시키려고 했고, 실패했다. 이유는 모든 결과를 고려하지 않아서 인 것 같다. 어떤 경우였냐면 //bfs메서드의 파라미터로 color을 받아 RGBCheck배열 체크 switch(color) { case 'R':..

문제 풀이 Silver 2 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 Binary Search 중 Upper Bound를 이용한 문제 [알고리즘] Upper Bound, Lower Bound [알고리즘] Upper Bound, Lower Bound 서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Bi..

문제 링크 Silver 1 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 문제에서 N은 N-1과 N+1과 색상을 중복해서는 안된다. 라고 하는 부분에서 조금 헷갈렸는데 결론은 크게 신경쓰지 않아도 된다. N일 때 N-1에서 중복만 체크한다면 어떤 상황에서도 중복이 될 일은 없다. for (int i = 0; i < N; i ++) { st = new StringTokenizer(br.readLine(), " "); ..

문제 링크 Silver 3 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 문제 티어는 낮지만 DP문제라서 냉큼 공부 처음에는 아래처럼 해당 idx의 제곱값을 구하여 greedy처럼 풀어내려고 했으나 int[] arr = new int[(int) Math.sqrt(n) + 1]; for (int i = 0; i < arr.length; i ++) { arr[i] = i * i; } 모든 상황에 만족하지 ..