📝 알고리즘/Implementation

문제 (Silver 1) https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 길이가 k인 슬라이딩 윈도우로 구현하였다. 이 때, 매번 i번째에 대해서 k개를 탐색하는 것이 아니라 ( → 시간초과! ) 초기의 window를 셋팅하고 start와 end 인덱스에 대해서만 처리하였다. 슬라이딩 할 때, eat[start] 값을 -1하고, 그 값이 0이라면 cnt를 하나 감소시킨다. → 윈도우 안에 해당 종류의..

문제 (Gold 4) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 배열의 값들을 하나씩 돌며, 투 포인터를 사용하여 해당 수가 좋은지 판별하였다. 문제에 나와있는 예시가 너무 자명하기 때문에 아래 예시로 생각하고 문제를 풀었다. 5 -2 0 1 2 3 기본적으로 정렬을 진행해야 한다. 그렇지 않으면, 투포인터의 움직임에 따른 로직을 작성할 수 없다! left, right 값을 설정해주는데, 정렬을 해주었다고 right값을 i-1로 해서는 안된다! -> 음수가 있어..

문제 (Gold 1) https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 숫자와 연산자를 한번에 저장할 수 있는 Expression 클래스 생성 -> 숫자를 char로 한번에 저장했더니, 9 이상의 숫자는 제대로 작동하지 않음 ㅠㅠ 연산 리스트에서 숫자가 나오는 짝수 인덱스를 돌며 연산 수행 후, 남은 연산 리스트를 재귀 돌림 기저조건: 리스트에 원소 하나만 남아있을 때 ( == 숫자 하나가 남아있을 때 ) 짝수 idx( ..

문제 (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,..