파이썬

https://www.acmicpc.net/problem/11722문제 주어진 수열의 부분 수열 중 가장 긴 감소하는 수열을 찾는 문제이다. 풀이 각 인덱스에서 감소하는 수열의 최대 길이를 확인하고 그 중 가장 큰 값을 출력하면 된다.어떤 인덱스를 i라 하면 에서 감소하는 수열의 최대 길이는 i보다 앞 인덱스의 수 중 num[i]보다 큰 수를 찾고, 그 중 그 인덱스의 감소하는 수열의 최대 길이를 확인하여 1을 더하면 i에서의 감소하는 수열의 최대 길이가 된다.예제로 주어진 아래 수열을 확인해보자.10 30 10 20 20 1010은 자신보다 앞에 수가 없으므로 0에서의 감소하는 수열의 최대 길이는 1이다. 30 역시 자신보다 앞에 수 중 자신보다 큰 수가 없으므로 1이다. 10은 앞 수 중에 30이 자..

https://www.acmicpc.net/problem/27907문제 임의 길이의 소수 등차수열을 출력하는 문제이다. 풀이 여러 고민을 하면서 다양한 풀이방법을 시도했지만, 풀리지 않았는데, 풀이 방법을 찾아보니 공차에 대한 조건이 없으므로 그냥 임의의 소수를 주어진 길이만큼 출력하는 문제였다.즉 일반적인 답이 없다는 것을 빨리 알아차리고, 문제의 허점을 찾아야 하는 문제였다. 코드 print(*([2 for _ in range(int(input()))]))

https://www.acmicpc.net/problem/23886문제 주어진 수가 조건에 맞는 수인지 확인하는 문제이다.조건은 연속으로 오르거나 내릴 때 각이 같아야 하고, 시작은 증가, 끝은 감소이다. 풀이 먼저 주어진 수를 리스트 컴프리헨션을 이용해 리스트로 바꿔준다. 그냥 문자열로 처리하거나 숫자로 입력받고, 자릿수로 분해해주어도 되겠지만, 이 방법이 가장 편할 듯 하다.다른 조건을 검사하기 전에 시작과 끝의 각도를 확인하고, 시작이 감소이거나 끝이 증가이면 알프수가 아니므로 처리한다.그 후 각각의 각을 확인하면서 조건에 맞는지 확인한다.이전 각이 음수면서 지금 각도 음수인데 두 각이 다르면 알프수가 아니고, 이전 각이 양수면서 지금 각도 양수인데 두 각이 다르면 알프수가 아니다. 코드 num =..

https://www.acmicpc.net/problem/20436문제 주어진 키보드 조건에서 주어진 문자열을 타이핑하는 데에 걸리는 시간의 최솟값을 구하는 문제이다. 풀이 키보드 좌표를 구하는 부분과 키보드 타이핑 시간을 구하는 부분이 필요하다.키보드 좌표를 구하는 부분은 아래와 같이 리스트 속 문자열을 만들고, 여기서 해당 문자를 탐색하는 방식으로 만들어도 된다.keyboard = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']그러나 오른손과 왼손을 구분하는 것 때문에 각 문자에 좌표를 설정해서 딕셔너리로 찾는 것이 더 직관적이고 좋은 것 같아 아래 코드와 같이 구현했다.타이핑 시간 계산은 문제에서 제시한 방식을 그대로 사용하였다. 코드 lkeyboard = {'z':(0,0),..

https://www.acmicpc.net/problem/31418문제 정해진 스펀지 내에서 일정 시간이 흘렀을 때 바이러스들의 분포의 수를 구하는 문제이다. 바이러스들은 1초에 대각선, 상하좌우 중 한 방향으로 한 칸 이동하거나 움직이지 않을 수 있다. 풀이 바이러스가 어디에 있을 수 있냐를 구하는 문제이다. 바이러스는 좌우로는 최대 $ T $ 만큼 이동할 수 있고, 상하로도 최대 $ T $ 만큼 이동할 수 있다. 대각선도 마찬가지이니 바이러스 위치는 $ (2 \times T + 1) \times (2 \times T + 1) $ 개의 가능성을 가진다.그런데 바이러스는 스펀지에서 벗어나진 못하므로 바이러스가 이동하다가 좌우측, 상하측으로 스펀지에 막힐 가능성을 생각해야 한다. 만약 바이러스가 이동할 수..

https://www.acmicpc.net/problem/9414문제 각 테스트 케이스에 따라 규칙적으로 증가하는 땅값을 확인하고, 구매할 수 있다면 구매하는데 필요한 비용을, 구매할 수 없다면 "Too expensive"를 출력하는 문제이다. 풀이 파이썬은 데이터의 크기에 따라 메모리를 동적으로 할당하기 때문에 큰 수를 다루기 용이하다. 따라서 문제 그대로 모든 땅값을 구하고, 상근이 가진 돈과 비교해서 너무 비싸면 "Too expensive"를 출력하면 된다. 만약 C++, Java 와 같이 데이터 타입에 따라 범위가 정해져 있는 언어를 사용한다면 땅값을 더해주면서 상근이 가진 돈과 비교하면 되겠다.땅값을 구하는 공식은 $ 2 \times (L_i)^t $ 인데, 해가 지날수록 기하습수적으로 증가한다..

https://www.acmicpc.net/problem/14381문제 각 테스트 케이스에 대해 입력을 받고, 주어진 규칙에 따라 숫자를 기록한 후, 조건에 부합하면 해당 숫자를 출력하는 문제이다.주어진 규칙은 주어진 수를 1, 2, 3 으로 곱해나가면서 각 자리 수에 있는 숫자를 기록하는 것이고, 조건은 그렇게 기록된 숫자가 0 부터 9 까지 있을 때 이다.  풀이 입력을 받고, 1 부터 시작해서 계속 곱해나가며 각 자리 수에 있는 숫자를 기록하면 된다. 단 입력으로 0 이 들어오게 되면 무엇을 곱해도 0 이 되어 0 부터 9 까지 수를 기록할 수 없으므로 조건에 따라 INSOMNIA 을 출력한다.기록할 때는 set 을 이용하여 집계하면 편할 것 같아 set 을 사용하면 좋을 듯 하다. 0 부터 9 까..

https://www.acmicpc.net/problem/10816문제 상근이가 가지고 있는 숫자 카드 묶음에서 주어진 숫자 카드들을 몇 개씩 가지고 있는지 구하는 문제이다. 풀이 상근이가 가지고 있는 숫자 카드 묶음은 입력받아 리스트로 만들어 주면 된다.이 문제의 핵심은 많은 카드 가운데 해당 숫자가 적혀있는 카드를 얼마나 빨리 찾느냐는 것이다. 일반적으로 count 함수를 사용하거나, in 함수를 사용하면 리스트에서 하나 하나 탐색하기 때문에 시간 복잡도가 $ O(n) $ 이 되고, 탐색을 모든 카드에 대해 해야하기 때문에 전체 탐색 알고리즘의 시간 복잡도가 $ O(n^2 ) $ 이 되게 된다. 따라서 탐색을 빠르게 하는 것이 중요하다.C 와 같은 언어에서는 카드 묶음을 정렬하고 이분 탐색을 이용하여..

리스트 컴프리헨션 리스트를 생성해서 값을 담을 때 코드를 더 간결하게 만들어주는 문법이다. 리스트 생성, for 문, 리스트에 대입 등 적어도 3 줄 이상으로 길어질 코드를 한 줄에 담을 수 있게 만들어준다.list_arr = [expression for item in iterable_data]기본적인 문법을 일반화시키면 위와 같다.expression 은 item 이 포함된 표현식으로 이 표현식이 리스트에 들어가게 된다. item 은 iterable 자료구조, 즉 리스트, 튜플, 문자열 등에서 가져오게 되는 각 항목이다. 수학의 조건제시법과 유사하다.위 기본적인 문법에 조건을 넣거나, for 문을 더 사용하는 방식으로 변형해서 사용할 수도 있다. 기본형 예를 들어 1 부터 10 까지 수를 리스트에 담는다..

https://www.acmicpc.net/problem/12683문제 각 문제의 정답 확률과 답안 제출 기회를 사용하여 답안을 제출했을 때 모든 문제를 맞아 시험에 합격할 수 있는 확률의 최댓값을 구하는 문제이다.영어 문제이지만, 번역기 정도만 사용해도 이해할 수 있다. 풀이 답안 제출 기회에 따라 풀이가 달라질 것이다. 만약 답안 제출 기회가 단 한 번만 있을 경우, 문제를 풀 때 합격 확률이 가장 높은 답안을 선택하여 제출해야 한다. 이 답안의 합격 확률은 각 문제의 정답 확률들을 곱했을 때의 값 중에서 가장 큰 값이 되며, 따라서 이 답안은 각 문제의 정답 확률 중에서 가장 높은 값들이 선택된 답안이 된다.하지만 답안 제출 기회가 여러 번 있을 경우에는 단순하게 접근하기가 어려워진다. 처음 답안을..