https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 다각형의 면적을 구하는 문제이다. 학생 때 배웠던 신발끈 공식을 이용하면 쉽게 문제를 풀 수 있다. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def shoelace(): idx_y = 1 idx_x = 1 ans = 0 for i in range(len(locate)-1): ans += (locate[i][0] * locate[idx_y][1..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net dfs문제이다. 하나씩 다 찾아보면 10만 x 10만으로 시간초과가 발생하므로, 필요없는 경우엔 탐색하지 않아야한다. 우선 인덱스를 활용하기 위해 약간의 조작을 해주고, 방문하지 않은 인덱스에 대해서 dfs 탐색을 진행한다. dfs 탐색을 계속 하다가 이미 방문한 곳을 재방문 했다면 사이클에 속해있는지 판단 후, 만약 속해있다면 해당 부분만 정답에 추가해준다! 5 -> 1 -> 4 -> 3 -> 2 -..
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 처음 풀어본 위상정렬 문제이다! 위상정렬을 풀기 위해선 반드시 이용해야하는것이 있다. 1. 진입차수 2. 스택 또는 큐 3. 사이클 여부 각 노드를 가리키는 엣지가 몇개 인지(= 진입차수) 계산해주어야 하며, 스택 또는 큐 자료구조를 이용하고, 만약 그래프가 사이클이 존재할 경우에는 위상정렬 순서를 구할 수 없으므로 유의해주자. 또한 위상정렬을 푸는 알고..
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net DP문제이다. 여느 DP문제가 그렇듯, 탑다운이 아니라 바텀업으로 풀어야한다. 이 문제의 점화식은 아래 3가지 조건을 만족해야한다. 점화식을 f(x)라 하자. 1. f(x) = f(x-1) + 1 --> 1을 더해서 만드는 경우 2. if x % 3 == 0, f(x) = f(x/3) + 1 --> x가 3으로 나눠질 때 3. if x % 2 == 0, f(x) = f(x/2) + 1 --> x가 2로 나눠질 때 ※ 여기서 더하기 1은 경우의 수가 하나 증가함을 의미한다!! 예를 들어 설명해보자면, 우..
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 구현 + 백트래킹 + 브루트포스 문제다. 사다리의 가로줄과 세로줄을 각각 x좌표 y좌표라고 생각하고 풀면 편할 것이다. 우선 입력을 받으면서, 가로선이 그려진 좌표를 표시해준다. (가로선이 그려질 때 (x,y)와 (x,y+1)를 잇게 되는데, 이 두 좌표를 모두 1로 표시하고 푸는 방법도 있으니 참고!) 그리고나서 탐색을 시작하는데, 매 탐색마다 i번 라인에서 출발하여 도착 결과가 i번 인지 확..
https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 티어에 비해 쉽게 풀렸던 문제이다. 이 문제의 핵심 알고리즘은 "갯수 당 가격"이 가장 큰 3원을 사용하는 연산의 횟수를 최소화하고, 그 경우 중에서도 5원을 사용하는 횟수를 최소화하는 것과 arr[i+1]번째 값과 arr[i+2]번째 값의 비교이다! -> 만약 [1,2,1,1] 과 같이 주어졌다고 하자. 당연히 3개씩 묶어서 사는게 이득이므로 1번째와 2번째, 3번째에 있는 라..
