알고리즘

[프로그래머스 Lv.3] 풍선 터트리기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이dp에서 사용하는 메모이제이션을 통해 최솟값을 저장하는 방법으로 문제를 풀이하였다. 이 문제를 풀이하긴 위해서 풍선을 마지막까지 남길 수 있는 조건이 무엇인가를 알아야 한다.문제의 조건을 간단하게 요약하면 남기려고 하는 풍선의 좌우에 위치한 남은 풍선 중 하나라도 크기만 하면 된다는 것이다.그렇기에 남기려고 하는 풍선의 좌측에 남은 풍선들의 최솟값이나 우측에 남은 풍선들의 최솟값 중 하..

[프로그래머스 Lv.3] 이중우선순위큐 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이Python의 내장 모듈인 heapq를 사용하여 문제를 풀이할 수 있다. heapq는 이진트리 기반의 최소 힙 자료구조를 제공하는 내장 모듈이다.문제 풀이에서 사용한 heapq의 메서드들을 간단히 설명한 후 코드를 통해 전체적인 풀이를 설명하겠다.heapq.heappush(list, n): 최소 힙(list)에 n을 삽입, 이진트리에 n을 삽입하는 것이므로 O(logN)의 시간 복잡도를..

[프로그래머스 Lv.3] 네트워크 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. from collections import dequedef solution(n, computers): answer = 0 ..

[프로그래머스 Lv.3] 정수 삼각형 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이DP 문제이기에 문제 해결을 위한 규칙을 찾아서 점화식을 세우는 것이 가장 중요하다.삼각형의 위에서부터 아래로 내려오면서 숫자를 더하여 각 위치에 들어갈 수 있는 최댓값을 얻어내고, 이를 저장하는 방식을 반복하여 삼각형을 모두 채운다. 가장 아래층에서의 최댓값이 구하고자 하는 답이 된다.def solution(triangle): _triangle = [] # 각 위치에서의 최대값..

[프로그래머스 Lv.3] 최적의 행렬 곱셈 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12942 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이dp 문제이다. 따라서 문제 상황을 해결하기 위한 점화식을 세워야 한다.일반적인 상황을 가정하고 이 상황을 해결하는 과정을 생각해 보면서 알맞은 점화식을 유도해 보자. 4개의 행렬 M1, M2, M3, M4가 있으며,  arr라는 배열은 arr[i][j]일 때, i 행렬부터 j 행렬까지의 곱을 수행할 때의 계산 수의 최솟값이라고 가정하자. 이런 상황에서 M1, ((M2, M3), M4)..

(Python) 백준 1912번 - 연속합

문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다. 문제 해결을 위한 아이디어는 다음과 같다. 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다. 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다. 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다. 최종적으..

[프로그래머스 Lv.3] 입국심사 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이전형적인 이진탐색 문제이다. 현재 시간으로 모든 사람의 입국 심사를 진행할 수 있으면 상한선을 현재 시간으로 조절하고, 만약 현재 시간으로 모든 사람의 입국 심사를 진행할 수 없다면 하한선을 현재 시간 + 1로 조절한다. 이런 과정을 하한선이 상한선과 동일하거나 더 커진 순간까지 반복하면 이 값을 구할 수 있다. def solution(n, times): start = 1 # 하한..

[프로그래머스 Lv.2] H-Index (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이정렬한 인용 횟수의 배열과 인덱스와 전체 길이를 사용해서 문제를 해결할 수 있다.def solution(citations): citations.sort() # 배열 정렬 idx = 0 length = len(citations) if citations[idx] > length: # 인용 횟수의 최소값이 이미 전체 논문 수를 초과한다면 return ..

(Python) 백준 6588번 - 골드바흐의 추측

문제 링크: https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 문제를 해결하기 위한 기본적인 아이디어는 에라토스테네스의 체이다. 우선 가장 홀수 중 가장 작은 소수인 3부터 시작해서 소수인지 검사하고, 만약 그 수(x)가 소수라면 n-x도 소수인지 체크를 한다. 이 모든 체크가 통과되면 n = x + n-x를 출력하면 된다. import sys MAX_NUM = 1000001 # N의 최대값 arr = [True] *..

[프로그래머스 Lv.2] 의상 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 해시와 수학적인 사고가 필요한 문제이다.우선 해시를 사용해 각 옷의 종류별 개수를 파악한다. 파악한 수를 기반으로 입을 수 있는 총 조합의 개수를 계산한다. 조합의 갯수는 옷의 종류별의 수를 n이라 했을 때, n+1을 곱해주다가 최종적으로 -1을 해주면 된다. n+1을 곱해주는 이유는 n개의 옷과 입지 않을 경우의 1을 더해주는 것이고, 최종적으로 1을 빼주는 이유는 모두 다..