https://www.acmicpc.net/problem/28458 28458번: Mahjong Tenpai 3통을 가져왔을 경우 3삭 2개를 머리로 사용한 후 3삭 4삭 5삭의 슌쯔를 몸통1, 3삭 4삭 5삭의 슌쯔를 몸통3, 1통 2통 3통의 슌쯔를 몸통3, 3통 3통 3통의 커쯔를 몸통4로 볼 수 있다. 6삭을 가져왔을 경 www.acmicpc.net 주어진 마작패가 대기패인지 아닌지 판별하고 대기패라면 완성패가 되기 위해 추가해야 하는 패를 출력하는 문제이다. 일단 대기패의 구성 숫자가 13장이고, 완성패의 구성숫자가 14장으로 크지 않고 패의 종류도 많지 않아서 브루트포스를 돌리면 되겠다고 생각했다. 그래서 34종류의 모든 패를 하나씩 대기패에 추가해보고 그렇게 구성한 패가 완성패인지 아닌지 판..
https://www.acmicpc.net/problem/28457 28457번: Every? Only One's Marble 첫 번째 줄에는 보드의 크기 $n$, 시작 시 가지는 돈 $S$, 시작점을 지나면 받게 되는 월급 $W$, 황금 열쇠 카드의 개수 $G$가 주어진다. ($3\leq n\leq 10$, $1\leq G\leq 4n-8$, $1\leq S,W\leq 10^7$) 그다음 $G$개의 www.acmicpc.net 부루마블 게임을 구현하는 문제다. 그래도 플레이어가 1명이라 구현 난이도가 엄청 높진 않다. (플레이어가 여러명인 Yut Nori 같은 문제 구현에 비하면..) 구현할 때 다음과 같은 2가지 사항에 주의해야했다. 1. 보드의 사이즈가 작을 때는 주사위 한번으로 2바퀴를 돌 수도 ..
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억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다. 그래서 결국 알고리즘 분류를 봤다.. 그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다. 다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다. 행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다. 그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치..
