지구정복

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net -문제해설 아래 블로그를 참고했다. https://st-lab.tistory.com/148 입력되는 식에서 가장 최솟값을 만들기 위해서는 덧셈 식을 먼저 계산하고 해당 덧셈값을 빼주면 된다. 이렇게 되면 가장 큰 값을 빼게 되므로 최솟값이 나오게 된다. 따라서 먼저 -로 식을 분리한다. -로 분리된 식에서 +로 또 분리한다. +로 분리된 식을 모두 더한다. (tmp에 저장) 최종결과값이 mi..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net -문제해설 자바로는 BFS를 이용했고, 파이썬에서는 DFS를 이용했다. -자바 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.String..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net -문제해설 전형적인 BFS문제이다. 그래프 이동을 위해서 dx, dy 배열을 지정하고 반복문을 돌면서 좌표를 이동시킨다. 이때 중요한 점은 이동횟수를 큐에 같이 집어넣어줘야한다. 이를 위해서 Point 사용자 클래스를 정의하고 필드값은 x, y, ans 이다. ans는 이동횟수를 나타내는 변수이다. 자세한 내용은 아래 코드 참고 -자바 package bfs_dfs; import java.io.Buf..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net -문제해설 그냥 주어진 i와 j인덱스를 반복문으로 돌면서 구간 합을 구할 경우 시간초과가 나오게 된다. 따라서 애초에 데이터를 배열에 집어넣을 때 첫 번째 인덱스부터 삽입되는 인덱스까지의 누적 합을 구한 뒤 배열에 집어넣고 i부터 j까지의 구간합을 구하는 방법은 다음과 같다. arr[ j ] - arr[ i-1 ] 예를 들어서 배열 5 4 3 2 1 이 있을 때 2번 인덱스..