Algorithm

https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 수학과 투 포인터 문제다. 성원이의 몸무게가 G 킬로그램 늘었다. 이 G킬로그램은 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다. 입력은 자연수로 들어오므로 모든 몸무게는 자연수다. 처음 생각한 방법은 어떤 수의 제곱에서 g를 뺀 수도 제곱수라는 점을 활용하는 것이다. 반복문으로 1부터 g까지 순회하면서 해당 수의 제곱에서 g를 빼고 그 수(tmp)가 제곱수 인지 확인했다. tmp가 ..

https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 그리디 문제다. 주어진 수열에서 최대 합을 구하는 문제다. 합을 할 수 있는 방법은 1. 한 개의 수 더하기 2. 두 수의 곱 더하기 정렬을 해서 양수와 음수를 따로 계산하는 방법을 떠올렸다. 이와 비슷한 문제를 푼 적이 있는데 https://www.acmicpc.net/problem/1461 이 문제다. 수열을 입력 받으면서 음수의 개수를 세어두고, 수열을 정렬한다. 주의해야 할 점은 1. 큰 ..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net BFS문제다. 일반 미로 문제에서 벽(검은방)을 부수고 갈 수 있는 미로로 생각하면 되는 문제다. 문제에서 구해야하는 건 미로의 최단 경로가 아닌 최대한 벽을 적게 만나는 경로를 찾는 것이다. 방문 배열을 이용해서 문제를 해결했다. 방문 배열에 지나간 검은 방의 개수를 저장하고 현재 이동하려는 방 까지의 검은 방의 개수가 이전에 방문했을 때의 검은 방의 개수보다 작다면 방문한다. 이 때 간과했던 ..

https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 스택 자료구조 문제다. 이 문제를 볼 때마다 뭘 구하라는 건지 이해가 안돼서 패스했었는데 드디어 이해하고 해결했다. 스카이라인의 높이가 바뀌는 경우 좌표가 주어진다. 모든 칸을 커버하는 최대의 직사각형 개수를 구하는 문제라고 판단했다. 스택 문제긴 하지만 스택을 이용하지 않았다. 높이가 바뀌는 지점이 순서대로 입력되므로 입력받는 대로 결과를 처..

https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net 문자열 문제다. 두 단어의 비슷한 정도를 접두사의 길이로 비교하여 가장 비슷한 두 단어를 찾는 문제다. 답으로 S와 T라는 문자열을 출력한다고 했을 때, 우선 순위는 먼저 입력된 순이다. S와 T가 될 수 있는 문자열이 여러개라면 가장 앞쪽에 위치한 단어가 S, S가 같다면 T를 기준으로 판단한다. 접두사의 공통부분을 찾기 위해 입력단에서 문자열과 인덱스를 벡터에 저장했다. 벡터에 저장한 이유는 정렬을 위해서다. 정렬을 하면 인접한 문자..

[https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net DP와 누적합 문제다. 해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다. 배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다. 검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다. 빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야..