이 글은 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 원문 보기백준 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..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 1005번얼핏 보기에는 쉬워보였다. 조금 헷갈리긴 했지만 결국 그래프탐색 문제이고, 출발점을 어디로 잡는지만 결정한다면 문제를 쉽게 풀릴 것이라고 생각했다.그래서 역발상으로 출발점을 목표 건물로 잡고 BFS를 해서 문제를 풀고자 했다.당연히 테스트는 실패했다. 일반적인 bfs로 풀 시 문제점이 있다예를 들어 사진 속 4번 건물을 짓기 위해서는 2,3번 건물이 완성되어 있어야 하고, 이를 위해서는 1번 건물이 완성되어 있어야 한다.1번 건물은 건설 시간이 10초가 걸리고 2번 건물은 1초, 3번 건물은 100초가 걸린다.2번 건물은 매우 빠르게 완성되지만 결과적으로 4번 건물을 짓기 위해서는 3번 건물이 완성되어야 하기 때문에 총 120초가..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기11054번_가장 긴 바이토닉 부분 수열문제를 본 처음에는 아래와 같이 풀이 방식을 생각했다.각 위치에는 Ai를 k로 잡았을 때의 가장 긴 수열을 길이를 저장Ai를 k로 잡는다면 2가지 경우를 찾으면 됨k의 왼쪽 부분 수열: 오름차순이면 최댓값이 k보다 작은 수열k의 오른쪽 부분 수열: 내림차순이면 최댓값이 k보다 작은 수열Ai의 값은 (k의 왼쪽 부분 수열의 길이) + (k의 오른쪽 부분 수열의 길이) + 1이다.그러나 이 풀이에는 허점이 있었다. 왼쪽, 오른쪽으로 나눈 부분 수열 또한 다시 부분 수열로 나뉠 수 있다는 것이다.어떻게든 이 풀이방식을 고집한다면 문제를 풀 수 있을거 같았지만 문제가 요구하는 방식이 아니고, 이런 경우 시간복잡도..