📝 알고리즘

문제 (Silver 1) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 아이디어 줄 단위로 더해줌 [ ][ ][ ][ ][ ] [ ][ ][o][o][ ] -> o 부분 합: sum(2,5) - sum(2,2) [ ][ ][o][o][ ] -> o 부분 합: sum(3,5) - sum(3,2) o의 최종 부분 합: ( sum(2,5) - sum(2,2) ) + ( sum(3,5) - sum(3,..

문제 (Silver 3) https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 풀이 문제가 어렵지는 않지만 이해를 잘 해야하는 문제! substring으로 나눌때에 반례가 많으니 이를 잘 체크해주어야 한다. 코드 더보기 package implement; import java.io.*; import java.util.*; public class Main_9996_한국이그리울땐서버에접속하지 { public static ..

문제 (Gold 3) https://www.acmicpc.net/problem/4933 4933번: 뉴턴의 사과 각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다. www.acmicpc.net 풀이 입력 받은 값을 어떻게 트리로 만드느냐를 생각하는 것이 관건. 입력은 포스트오더(후위순회)로 주어진다고 하니 stack을 활용하여 트리 구성 후위순회로 주어진 그래프의 stack 변환 로직 1. 현재 넣으려는 노드(i)가 null이 아니고, 이미 스택에 2개 이상 쌓여있다면 2. 맨 나중에 넣은 노드(stack.pop())가 오른쪽 노드 3. 그 전에 넣은 노드(stack.pop())가 왼쪽 노드 4. right와 left노드의 부모를 현재 노드(i)로 설정 5. 현재 ..

문제 (Gold 2) https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 모든 경로에 대한 최소 비용을 구해야 하므로 '플로이드-워샬 알고리즘' 사용! 최소 비용 외, 경로에 대한 내용도 저장해야 하므로 이차원배열 변수 하나 더 선언 map[i][j]: i -> j 경로의 최소 비용 저장 path[i][j]: i에서 출발해서 j까지 도착하기 직전에 들르는 도시 바로 오는 길(map[i][j])보다 경로 k를 거쳐서 오는 길(map[i][k..