https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 개인적으로 플레 난이도 치고는 풀만한 문제라고 생각한다. 중복되는 키가 연속으로 들어오는 경우를 체크하는게 고민 포인트. 내가 푼 알고리즘은 다음과 같다. 0. 맨 처음에 들어오는 키는 그냥 스택에 넣는다. 1. 수를 입력받으면 해당 수와 스택의 탑에 있는 값을 비교한다. 1.1 탑에 있는 값 > 새로 들어온 값 인 경우 (키가 감소) 탑에 있는 값과 새로 들어온 값이 서로..
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/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 모든 가로수의 간격이 같도록 새로 심어야 하는 가로수의 최소 개수를 구하는 문제이다. (최대 개수로 심으려면 그냥 간격을 1씩 해서 심으면 되니 간단하다) 바꿔말하면 주어진 수열이 등차수열이 되도록 하는 공차의 최댓값을 구하는 문제로 볼 수 있다. 등차수열의 일반항 An = a + (n-1)d 으로 생각을 해보면 구하는게 공차의 최댓값이니 공차를 구하는데 방해가 되는 초항 a 를 없애준다...
백준에서 정렬 문제를 풀다가 궁금한 점이 생겼다. https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀던 문제는 이 문제다. 어렵지 않은 정렬 문제다. 근데 내가 5달 전에 파이썬으로 푼 코드와 오늘 파이썬으로 푼 코드의 길이가 비슷한데 시간차이가 많이 났다. 그래서 처음에는 set.add() 로 아이템 개수만큼 추가하기 vs 리스트에 담아둔 걸 set 으로 감싸서 리스트 객체로부터 set 객체 만들기 이 방법 차이로 시간이 많이 차이..
난이도 : 레벨 1 다트 점수 현황이 문자열로 주어질 때, 해당 문자열로부터 다트 점수를 계산하는 문자열 구현 문제이다. 내가 무식하게 푼 방법과 다른 사람의 코드를 보면서 배운 점을 적어보고자 한다. 평소에 구현을 무식하고 우직하게 하다보니 시간도 오래걸리고 실수도 정말 많이 해서 힘들었는데 이런 쉬운 깡구현 문제를 많이 풀면서 연습을 해야겠다는 생각이 들었다. 1. 다트는 3번 던진다. 2. 각 기회에서 점수는 0~10 사이의 점수가 주어진다. 3. 각 점수 이후에 해당 점수를 몇 제곱할지 S, D, T 가 주어진다. 4. 이후에 해당 점수와 기존 점수에 연산을 진행하는 옵션 *, #이 주어질 수도 있고 주어지지 않을 수도 있다. def solution(dartResult): point_list = ..
https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드 동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼 www.acmicpc.net 옛날에 봤을 땐 분명 골드5 문제였는데 어느샌가 골드4로 올라간 문제이다. 풀고나서 보니까 왜 누구는 골드5로, 누구는 실버1로 매겼는지 알 것 같았다. 문제 상황을 프로그래밍적으로? 정의하고 나면 되게 간단해지기 때문이다. 그런데 이 문제는 그 정의가 어려운 문제였다 그래서 나도 이 문제 난이도에 골드4를 줬다. 문제는 간단하다. 좌우버튼과 엔터 버튼만으로 구성된 키보드를 이용해 주..
전에 풀었던 문제인데 2달전 재채점 때 틀려서 다시 풀어보았다. 다시 풀려니까 도저히 풀리질 않아서 외판원 순회 아이디어를 읽었는데도 모르겠었다. 그래서 결국 내가 전에 티스토리에 썼던 글을 보았는데, 신기하게 그걸 보니까 작성할 수 있었다. 나는 내가 제일 잘 아는건가ㅋㅋ 하지만 그 글에서 헷갈렸던 부분이 있어서 다시 정리하려고 한다. 1. 외판원 순회는 어디에서 시작해도 값이 같다. "도시" 가 아니라 "간선" 을 기준으로 보면 바로 이해된다. 1-3-2-1 이 최적해라고 하자. 그럼 최적해를 구성하는 간선은 1-3 3-2 2-1 이렇게 3개이다. 만약 3에서 시작했다고 하면 최적해는 3-2-1-3 이렇게 된다. 최적해의 구성 간선은 3-2 2-1 1-3 순서만 다르지 아까와 똑같다. 따라서 어디에서..
https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 처음엔 그림만 보고 그래프 문제를 예상했는데, 문제를 읽어보니 경우의 수를 세라길래 DP로 예상해서 DP 점화식을 세웠다. 근데 dp테이블을 일일히 채우고 있다가는 저 10억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다. 그래서 결국 알고리즘 분류를 봤다.. 그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다. 다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다. 행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다. 그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치..
https://www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 자료구조를 이용한 깡 구현 문제이다. 구현문제아니랄까 한글자 오타난 걸 디버깅하느라 애를 먹었다. (무수한 assert 문 제출 시도..) 맨 앞의 연산자 / 맨 뒤의 연산자 둘중 하나를 골라서 스택처럼 처리해야하므로 덱을 이용했다. 파이썬으로 풀 때 음수 나눗셈에 주의하고, 음수 하나만 입력으로 들어오는 코너케이스를 주의하면 어렵지 않게 풀 수 있다. from ..
https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 이분 탐색을 쓰면 좋겠다고 떠올렸지만, 한번 쓴 카드를 다시 쓰지 않도록 체크하는 부분을 어떻게 해야할지 떠올리지 못했던 문제이다. 결국 알고리즘 분류를 통해 힌트를 얻고 풀었다. 분리집합을 보고 처음에는 어떻게 분리집합을 이용해서 풀 수 있을지 감이 안잡혔는데, 노트에 생각을 정리하다보니 아이디어가 떠올랐다. 이분탐색, 특히 upper bou..
