프로그래밍 문제

입력된 숫자가 몇 자리 수인지 파악하고 각 자리 수를 구해서 더하는 방법이 가장 먼저 떠오르지만 파이썬스럽지 못한 풀이라고 생각했다파이썬은 리스트의 합을 구해주는 sum 함수가 있으니 숫자를 리스트로 나눠주기만 한다면 sum을 이용해 간단히 자릿수 합을 구할 수 있다.

총 N마리의 폰켓몬 중 N//2마리를 고르는 문제골랐을 때 겹치지 않는 폰켓몬의 수를 반환순열 문제로 생각할 수 있지만순열로 해결하게 되면 시간 복잡도가 매우 커질 수 있다.리스트에서 겹치는 원소를 제거하는 방향으로set 을 이용하여 list 내부의 겹치는 원소를 제거

정렬 문제인가?착각할 수 있지만 정렬 문제가 아니다.각 입력마다 자신보다 큰 입력이 몇 개인지 탐색해서 출력해주면 된다.탐색을 위해서 모든 입력을 파이썬 리스트에 저장한다.출력 형식이 줄바꿈이 아닌 공백으로 되어 있기 때문에end=" " 으로 끝문자를 수정해준다.문제는

파이썬에는 nlogn의 시간 복잡도를 가지는 리스트 정렬 방법이 내장되어 있다..sort 대신 sorted를 사용하여로 코드를 작성해도 된다.파이썬이 아닌 언어를 사용했으면선택 정렬이나 버블 정렬과 같은 n^2의 시간 복잡도를 가지는알고리즘을 사용하면 된다.여기서는 따

문제의 설명을 보면 언어에 내장되어 있는 nlogn의 복잡도를 가지는 알고리즘을 사용하라고 되어 있다.오답 코드아래는 시간초과가 뜨는 코드이다.분명 파이썬 내장 라이브러리를 사용했는데 시간초과가 뜬다.힙 정렬이나 병합 정렬을 직접 구현해야 하나 의문이 들었지만 다른 방

문제 설명을 보면 카운팅 정렬 방식을 사용하라고 나와 있다.카운팅 정렬 방식은 숫자가 나온 횟수를 이용하여 정렬하는 방식이다.아래는 파이썬으로 직접 작성한 카운팅 정렬 방식이다.이 방식을 통해 실행하면 메모리 초과가 발생한다.코드를 비효율적으로 작성하긴 했다 ㅜ.ㅜ카운

위에 제시된 함수는 재귀함수의 형태이다.코드를 작성하는 것에 큰 어려움은 없다.단순히 문제에서 제시해 준 코드를 그대로 문법에 맞게 옮기면 된다.그러나 어떤 장치도 없는 단순한 재귀함수로 위의 함수를 구현하면 시간초과가 뜨게 된다. 시간 제한은 1초이다.이 재귀함수가

동적 계획법으로 문제를 해결할 때, 규칙을 찾는 것 그리고 우리가 동일하게 반복적으로 하는 선택이 무엇이 있는지 생각하는 것이 좋다.현재 사용할 수 있는 타일은 '1' 과 '00' 두 가지 타일이다.이것이 우리가 동일하게 반복적으로 하는 선택이다.1 과 00을 선택하여

조건이 있는 동적 계획법이다.우리가 할 수 있는 선택은 1) 한 계단 오르기 2) 두 계단 오르기이다.이 때, 연속된 세 개의 계단을 밟을 수 없는 조건이 있다.첫 번째, 두 번째, 세 번째 계단에 도달했을 때 얻을 수 있는 점수의 최댓값을 먼저 살펴보자.첫 번째 계

유명한 문제 중 하나로 알고 있다.탐욕법에서도 유사한 문제가 있는데 탐욕법으로 해결할 때는ex) 3으로 나누는 것이 2로 나누는 것보다 무조건 유리해야 한다.그래야지 매 번 최선의 선택이3으로 나누기 > 2로 나누기 > 1을 빼기 의 형식으로우선 순위가 결정되기 때문이

이 문제는 유명한 문제인 LIS(Longest Increasing Subsequence)를 활용하여 해결할 수 있다.예제 입력과 출력으로 주어진 것을 먼저 살펴보자.1 5 는 해당 인덱스에서의 LIS 이고 5 4 3 2 1은 해당 인덱스에서 역으로 생각할 수 있는 LI

다이나믹 프로그래밍에서 일차원 dp 배열을 이용하여 문제를 많이 푸는데이 문제는 기본적으로 이차원 dp 배열을 통해 풀도록 되어있다.하지만 누적 일차원 dp 배열을 이용하여 이차원을 이용하는 것보다 간단하게 해결할 수 있다.공통 부분 수열을 파악하기 위해서는 두 문자열

굉장히 유명한 문제이다.Knapsack problem으로 알려져 있다.출처 https://www.geeksforgeeks.org/printing-items-01-knapsack/문제에서 총 물품의 개수와 담을 수 있는 최대 무게가 입력으로 주어진다.우리는 위의

그리디 알고리즘을 통해서 해결하는 문제이다.탐욕법은 매순간 최선의 선택을 통해서 답을 찾아내는 알고리즘이다.이 문제에서는 정해진 계획 안에서 최대한 많은 회의를 진행시켜야 한다.최대한 많은 회의를 진행하려면 회의 리스트를 살피면서 가능한 회의를 전부 포함하면 된다.이

연산식에 '+' 와 '-' 가 껴있을 때, 최소의 결과를 내려면빼는 값이 최대로 되면 된다.음수 값을 최대로 만들려면 '-' 마다 괄호를 치면 된다.예시로 보면"10-20+30+40-30+40" 이 입력이 되었을 때, '-' 마다 괄호를 치면10-(20+30+40)-

백준 1934번최소공배수를 구하는 것은 간단한 문제이다.A와 B의 최대공약수를 먼저 구하고 A와 B의 곱을 최대공약수로 나누면최소공배수를 구할 수 있다.G = gcd(A, B)L = A\*B / G

백준 11051번백준 11051번

복잡한 듯 보이지만 해답 자체는 단순한 조합 문제이다. 하지만 코드를 작성할 때 조금 까다로운 요소가 포함된다.백준 9375번고등수학 확률과 통계에서 볼 수 있는 수학 문제이다.A가 N개, B가 K개 C가 P개 존재한다고 할 때, 반드시 전부 입을 필요는 없지만A,B,

백준 1676번어떤 팩토리얼 값에서 뒤에 이어지는 0의 개수를 구하는 것은 다시 말하면 10이 몇 번 곱해졌는지 묻는 문제와 동일하다.또한 10이 몇 번 곱해졌는지 묻는 문제는 결국 소인수 분해를 한 경우5가 몇 번 나타는 지 구하는 것과 동일하다.2가 5보다 무조건

10828번 스택스택의 기본적인 기능인 Push, Pop, Size, Empty, Top을 구현하는 문제이다.문제에서 설명한 기능들을 구현하는데 파이썬에서는 이러한 기능을 가진 리스트 자료구조가 존재한다.list는 append, pop의 내장함수를 가지고 len 함수를

스택을 이용해서 올바른 괄호를 찾는 문제이다.여기서 올바른 괄호란 ( ) 의 짝이 맞는 괄호이다.)( 은 올바르지 않은 괄호이다.스택에 '(' 괄호가 나올 때마다 삽입하고 ')'가 나오면 삭제하는 방식으로 풀 수 도 있고파이썬의 replace 함수를 이용하여 문제를 해

17298번 오큰수해당 문제에서 가장 중요한 조건은 시간 제한이다.최대한 효율적인 방법으로 각 '인덱스'의 오큰수를 구해야 한다.여기서 인덱스가 핵심이다.처음에 문제를 접근할 때, 스택에 3, 5, 2, 7 처럼 인덱스가 아닌 실제 값을 삽입했었다. 그 경우에 스택에서

11866번 요세푸스 문제 0이 문제를 접근할 때, 오해하게 되는 부분이 있다."문제에서 N명의 사람이 주어지고 K번째 사람을 제거한다" 라고 쓰여있기 때문에만약 사람이 K 명 이하가 되면 어떡하지? 라는 오해를 한다.처음에 그래서 문제에서 주어지지도 않은 규칙을 혼자

회전하는 큐가 어떤 자료구조이지? 배운적이 있었나? 라고 고민하는 것은 이 문제를 대하는 태도가 아니라고 생각한다.문제에서 큐가 할 수 있는 3가지 연산을 정해주었다.원소를 뽑아내기 2. 원소를 왼쪽으로 이동 3. 원소를 오른쪽으로 이동이 연산의 의미를 어느 정도 해석

시간 제한으로 인해서 은근 난이도가 높은 문제이다.예제 출력을 얻어내는 알고리즘을 구현하는 것은 매우 간단하다. 문제에서 주어진 명령을 그대로 수행하면 되기 때문이다.따라서 문제에 대해 따로 해석할 것은 존재하지 않는다.하지만 직전에 말한 것 처럼 시간 제한이 계속 발

1992번 쿼드트리이 문제는 분할정복 알고리즘을 해결하는 문제이다.분할정복이란 방대한 크기의 문제를 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 해결하는 것이다대표적으로 퀵소트와 병합정렬이 있다.2630, 1992, 1780 세 문제 모두 동일한 방식으로 해

1629번 곱셈이 문제의 해답을 분할 정복을 통해 구하는 것은 큰 어려움이 없다.이 조건을 통과하기 위해서는(A x B) % p = (A % p) x (B % p) % p

11401번 이항 계수 3단순히 이항 계수를 구하는 것은 어렵지 않다.nCk = n!/(n-k)!k! 을 계산하면 이항 계수를 구할 수 있다.하지만 문제의 입력 범위가 1~4,000,000으로 매우 넓기 때문에 재귀로 해결하려고 할 때, 재귀 깊이 초과 오류가 발생하게

11444번 피보나치 수 6문제의 조건을 보면 n이 1,000,000,000,000,000,000보다 작은 수이다.그렇기 때문에 아래와 같이 우리가 알고 있는 대로 해결하면 당연히 시간 초과가 발생한다.문제를 해결하면서 이번 기회에 새로운 것을 배웠다.매우 큰 피보나치

10816번 숫자 카드 2어떤 리스트 안에 내가 원하는 숫자가 몇 개 들어있는지 그 개수를 세서 출력하는 문제이다.하지만 시간 제한이 있고, 숫자의 범위가 큰 만큼 효율적인 알고리즘을 통해 해결해야 한다.일반적인 이분 탐색 알고리즘이다 근데 이제 count 함수를 곁들

1654번 랜선 자르기이 문제는 이분 탐색의 원리를 이용한 parametric search를 이용하여 해결한다.parametric search의 간단한 설명을 제시한다.Parametric search 이분 탐색의 원리를 이용한 탐색 방식으로특정 변수의 최대 또는 최소를

11279번 최대 힙문제 자체는 간단하다.최대 힙을 구현해서 0이 입력되면 pop연산을 자연수가 입력되면 insert연산을 수행한다.배열이 비어있는 경우에 pop연산을 요구하면 0을 출력한다.풀이 1은 직접 최대 힙 자료구조를 구현하는 것이다.MaxHeap이라는 클래스

11049번 행렬 곱셈 순서동적 계획법은 보통 dp 테이블을 작성하는 것으로 해답을 구한다.간단한 문제들은 일차원 디피 테이블로 구할 수 있지만 이 문제는 이차원 디피 테이블을 이용해야 한다.테이블을 시각화하면 아래와 같다.이 2차원 테이블에서 우리는 대각선을 기준으로