https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도가 조금 있는 스택문제 알고리즘 분류가 스택이라는 것만 알아내면 아이디어가 어렵다기 보다는 구현이 조금 복잡하다고 생각한다. 오등큰수를 결정하는 제일 큰 기준은 '숫자의 등장 횟수' 이다. 따라서 숫자의 등장횟수를 미리 다 저장해둔다. 주어진 수열의 왼쪽부터 차례대로 순회하면서 해당 숫자의 등장 횟수를 스택에 저장해나가다 스택의 가장 위에 있는 수의 등장횟수보다 더 많은 등장횟수를 가진 수가 나타나면 그..
https://www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 자료구조를 이용한 깡 구현 문제이다. 구현문제아니랄까 한글자 오타난 걸 디버깅하느라 애를 먹었다. (무수한 assert 문 제출 시도..) 맨 앞의 연산자 / 맨 뒤의 연산자 둘중 하나를 골라서 스택처럼 처리해야하므로 덱을 이용했다. 파이썬으로 풀 때 음수 나눗셈에 주의하고, 음수 하나만 입력으로 들어오는 코너케이스를 주의하면 어렵지 않게 풀 수 있다. from ..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 사이클에 속하지 않는 노드의 개수를 세는 문제이다. 생각보다 최적화를 깐깐하게 요구했던 문제이다. 하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다. 살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ (21.12.17 오전 10시 30분 기준) 물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ 이 문제의 알고리즘 분류는..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다. (그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.) 펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다. 어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다. 따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면 dp[s][e] = dp[s+1][e-1] + 2 이다. 단, 위 점화식의 조건은 dp[s+1][..
