Engineering Note

문제 https://www.acmicpc.net/problem/2468 문제해결방법 비의 양이 정해지지 않았으므로 비의 양을 0부터 최대높이-1로 변해갈 때 안전영역을 구하는 방식으로 코드를 구현하면 된다. 이때 비양을 최대높이-1 까지만 하는 이유는 최대높이까지하게 되면 영역이 전부다 물에 잠겨 안전영역은 0이 되므로 구할 필요가 없다. 이렇게 비의 양이 0부터 최대높이-1로 변해갈 때 주어진 2차원 배열의 위치를 (0,0) 부터 (n-1,n-1)까지 확인하면서 잠기지 않는 영역일 때 BFS로 그래프 탐색을 하면서 안전영역을 구하면된다. 코드 import sys from collections import deque def BFS(start_row, start_col, rain): global safe_..

문제 https://www.acmicpc.net/problem/4485 [4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net](https://www.acmicpc.net/problem/4485) 문제해결방법 다익스트라 알고리즘을 최소힙 자료구조를 이용해서 해결했다. (0,0)에서 (n-1,n-1)로 최소 루피를 잃으면서 이동해야하는 문제다. 매번 최소 소비 루피장소를 선택하려면 최소힙 자료구조를 사용해야한다. 현재까지 잃은 루피에서 그 다음 이동장소(현재위치에서 상하좌우인접 장소)..

문제 https://www.acmicpc.net/problem/1697 문제해결방법 문제를 해결하는 방법은 0초일 때 수빈이의 위치 1초일 때 수빈이의 위치, 2초일 때 수빈이의 위치 ... n초 일때 수빈이의 위치와 동생의 위치를 비교하면서 두 위치가 값을 때의 가장 빠른 시간을 찾아야한다. 가장 빠른 시간을 찾을 것이기 때문에 시간마다 위치를 확인하고 아니라면 다음 1초후의 시간을 확인해야한다. 이때 활용하기 좋은 자료구조는 큐이다. N초 일때 위치를 확인하고 다시 그 때의 위치가 동생의 위치와 다르면 다시 그 위치로부터 1초 후 이동가능한 세가지 위치와 시간을 N+1을 하여 큐에 넣는다. 큐를 사용하는 이유는 큐는 먼저 들어간 값이 먼저 나오는 자료구조 인데 시간과 위치 값을 넣고 빼고를 반복하면서..

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제해결방법 브루트포스 방법으로 구간합을 매번 구하면 중복되는 연산이 발생한다. N의 최대값이 100,000이고 구간 합을 구하는 횟수인 M의 최대값이 100,000이고 100,000번 모두 1부터 100,000까지의 구간합을 구하는 경우라면 100,000 제곱의 시간복잡도가 계산된다. 이러한 문제를 해결하기 위해 첫 번째 구간 부터 각 구간 까지의 합을 미리 구해 놓..

문제 https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 문제해결방법 세 변의 값을 입력 받는다. 세 변이 모두 0이면 프로그램을 종료한다. 아니면 아래의 과정을 반복한다. 두변 각각의 제곱의 합을 더해 다른 변의 제곱과 같으면 right 출력 (경우의 수 세가지 a*a + b*b == c*c or a*a + c*c == b*b or b*b + c*c == a*a: 아니면 wrong 출력 코드 import sys input = sys.stdin.readline wh..

문제 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제해결방법 1 문제에서 주어진 조건을 잘 읽어 보면 주어진 비행기 스케줄은 항상 연결 그래프를 이룬다고 했다. 연결그래프는 임의의 그래프의 두점을 모두 연결 되었으므로 아무 점이나 시작점으로 삼아 그 곳으로부터 방문하지 않은 연결된 노드를 방문하면서 방문체크를 해주고 이때 비행한 횟수를 하나씩 증가시켜 주면된다.다시 순서도를 정리해서 적으면 아래와 같다..