이 글은 Velog에서 이전한 글입니다. Velog 원문 보기Lv 4. 쿠키 구입문제: https://school.programmers.co.kr/learn/courses/30/lessons/49995접근법문제 접근 알고리즘: 투포인터, 누적합(슬라이딩 윈도우 변형)문제의 본질연속된 두 구간의 합이 같은 경우 중, 그 합의 최대값 찾기전략은 간단했다.경계점 m을 기준으로 좌, 우를 투 포인터로 확장이유는 과자 수는 음수가 없으므로, 합이 작은 쪽을 늘리는 방식이 항상 올바르게 수렴하기 때문이다.풀이 전략은 평범한 투포인터 문제와 같다.경계점 m을 왼쪽 구간의 끝으로 고정초기 상태왼쪽 포인터 l = m오른쪽 포인터 r = m+1left_sum = cookie[l]right_sum = cookie[r]포인터..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준_2252번문제 설명N명의 학생들을 키 순서대로 줄을 세우려 한다. 학생 A가 학생 B보다 앞에 서야 한다는 M개의 키 비교 정보가 주어질 때, 올바른 줄 세우기 결과를 출력하라.학생 번호는 1번부터 N번까지.답이 여러 가지인 경우 아무거나 출력 가능.알고리즘: 위상 정렬 (Topological Sort)방향 그래프로 간선을 구성: A → B진입 차수(in-degree)를 기록하고, 진입 차수가 0인 노드부터 출력큐(BFS)를 이용해 순차적으로 정렬논리 흐름학생 번호를 정점으로 간주A → B 형태의 간선 구성진입 차수가 0인 노드를 큐에 삽입큐에서 꺼내면서 인접한 노드들의 진입 차수를 감소시키고, 0이 되면 다시 큐에 삽입모든 정점을 방문할..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 1197번처음 시도한 방법처음에는 그래프 탐색 문제라고 생각해서 DFS로 접근을 했다.그러나, DFS로 접근시 정점의 개수 V의 범위가 1이기 때문에 재귀 오류가 발생할 가능성이 다분하고 시간 초과에 걸린다.정답 접근법최소 스패닝 트리(MST) 문제는 전용 알고리즘이 2가지 존재한다.크루스칼 (Kruskal) 알고리즘간선을 가중치 기준으로 정렬 후, 작은 순서대로 선택하며 Union-Find로 사이클 방지프림 (Prim) 알고리즘한 노드에서 시작해서 우선순위 큐로 인접 간선 중 최소 선택내가 사용한 것은 크루스칼 알고리즘이다.코드 구조edges = []for _ in range(E): A, B, C = map(int, input()...

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기Leetcode 300번 문제"오름차순 수열의 최대 길이"를 찾는 문제라고 생각하고 풀었다.첫번째 시도class Solution: def lengthOfLIS(self, nums: List[int]) -> int: N = len(nums) dp = [1]*N # dp[i] = index i까지의 최댓값 for i in range(1, N): if nums[i] nums[i-1]: dp[i] = dp[i-1] + 1 # 증가하는 수열에 포함 return max(dp)처음에는 DP(다이나믹 프로그래밍)을 활용해서nums의 i index의 값이 i..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 15665번NZEC 오류 발생백준 백트래킹 문제 15665번을 풀던 중 NZEC라는 처음 보는 런타임 에러가 발생했다.에러의 원인을 파악하기 위해 NZEC 런타임 에러에 대해서 찾아봤다.NZEC(Non-Zero Exit Code) 오류?Python 프로그램이 예기치 않은 예외로 인해 비정상 종료되었을 때 발생합니다. 주로 입력값이 잘못되었거나, 특정 예외가 처리되지 않았을 때 발생할 수 있습니다.나의 코드import sysinput = lambda: sys.stdin.readline().rstrip()# 크기가 M인 수열, 같은 수 중복 가능# 중복 수열 x, 사전 순 오름차순def dfs(num): if len(num) == M: ..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 1699번1차 코드(실패)import sysinput = lambda: sys.stdin.readline().rstrip()import mathN = int(input())dp = [int(1e9)]*(N+1) # 1~N의 제곱수 항 최소 개수를 표현할 리스트for i in range(1, int(math.sqrt(N))+1): dp[i**2] = 1# 10을 만드는 최소항은 3^2(9) + 1^2# 11을 만드는 경우 11보다 작은 수 중 가장 큰 제곱수를 빼고 그 수를 만드는 경우를 더해주면 된다.for i in range(2, N+1): if dp[i] == 1: continue dp[i] = min(dp..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기⭐️ 서론알고리즘 풀이를 하다보니 조합, 순열, 중복 순열 개념이 자주 등장하는 것을 알았다.물론 직접 코드로 구현할수도 있지만, itertools 라이브러리에 이미 구현되어 있기에 잘 이용한다면 큰 도움이 될 것 같아서 정리를 한다.⭐️ itertools: 효율적인 루핑을 위한 iterator를 만드는 함수파이썬 공식 문서itertools의 여러가지 함수 중 조합형 iteratorcombinations()combinatios_with_replacement()product()permutations()📌 combinations(iterable, r): iterable에서 원소 개수가 r개인 조합 뽑기from itertools import com..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 3151번우선 문제는 투포인터 문제이다.하지만 학생 3명 점수의 총합을 찾아야 된다는 조건이 있다. 삼포인터 같은 알고리즘은 존재하지 않는데 문제를 어떻게 풀어야 할까?나는 아래처럼 문제를 풀고자 했다.풀이 이론점수 배열을 오름차순으로 정렬한다.학생 한 명을 고정한다.나머지 학생 2명의 점수 총합을 투포인터 알고리즘으로 탐색한다.이처럼 학생 한 명을 고정한다면 투포인터로 문제를 풀 수 있다.학생 한 명을 고정한다는 것을 제외하면 일반적인 투포인터 문제와 비슷하기에 코드는 금방 구현했다. 그러나 두번째 문제가 발생했다.문제 발생 코드import sysinput = lambda: sys.stdin.readline().rstrip()N = in..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 20922번문제가 짧아서 좋다. 이런식으로 수열을 탐색을 요구하는 문제는 대부분 투포인터 알고리즘을 사용하라는 뜻이다.투포인터 알고리즘?이름 그대로 두 개의 포인터를 사용해 탐색을 하는 것이다.대표적으로 시작 지점은 start와 끝 지점인 end를 두고, 문제 조건에 만족하는 경우 end를 옮기다가 문제 조건을 위반하는 순간 start의 위치를 문제 조건을 충족하는 위치까지 변경해주는 것이다.나는 이 문제를 아래처럼 세부 문제로 나눴다.*부분 수열의 원소의 갯수가 K를 넘지않도록 하려면 부분 수열 원소의 갯수를 따로 저장해야한다. *딕셔너리 활용, List도 가능하지만 딕셔너리가 효율적임원소 x의 갯수가 K개를 넘는 순간 start의 위치..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 2294번_동전큰 어려움 없이 푼 문제이다. 개인적으로 이 문제보다 DP 실버1 문제들이 더 어려웠던거 같다.n가지 동류의 동전, 가치의 합이 k원이 되도록, 동전의 개수가 최소 이 3가지를 보면 해당 문제를 DP로 풀어야하는 것은 금방 알 수 있다.동전 종류의 갯수 n과 타겟이 되는 k의 범위를 보면 1 이므로 머리에 떠오르는대로 단순하게 풀어도 시간 초과를 발생하지 않을거라고 생각해서 아래와 같은 과정으로 문제를 접근했다.i원을 만들기 위해 필요한 동전의 갯수를 저장할 리스트를 만든다. (name: dp)리스트 원소의 초기값은 int(1e9)로 매우 큰 값을 주고, 리스트 원소의 수는 n의 최댓값이 100,000이기 때문에 100,00..