백준 : 1379 강의실2

백준 : 1379 강의실2문제 요약총 N개의 강의가 있다.각 강의는 세 가지 정보:강의 번호시작 시간종료 시간겹치는 강의들은 서로 다른 강의실이 필요하다.목표:최소 강의실 개수 출력각 강의마다 배정된 강의실 번호 출력 (강의 번호 순)문제 분석이 문제는 전형적인 그리디 + 우선순위 큐 (heapq) 문제입니다.📌 강의실 배정의 본질겹치지 않는 강의들은 같은 강의실을 사용할 수 있다.가장 먼저 끝나는 강의실부터 체크하면서 빈 방이 있으면 재사용.없다면 새로 방을 배정한다.📌 주의강의 번호와 강의 순서는 다르다!출력은 강의 번호 순처리 순서는 시작 시간 순따라서 입력을 받아서 → 시작 시간 기준으로 정렬 → 결과는 별도 배열에 저장최종 코드import sys, heapqinput = sys.stdin.r..

  • format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
  • · 2025. 4. 10.
백준 : 2098 외판원 순회

백준 : 2098 외판원 순회

백준 : 2098 외판원 순회문제 분석비트마스크와 DP를 이용해 모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최소 비용을 구하는 문제로, 방문 상태를 비트마스크로 관리하면서 현재 도시와 방문 경로를 기반으로 dp 테이블을 갱신해 최적 경로를 찾는다.비트마스크 활용n = 도시 개수비트마스크를 사용하여 0과 1로 도시 n개의 방문 여부를 관리한다.비트마스크는 도시 개수 n만큼의 자리수를 가지는 이진수로 표현된다.예시: 0111비트마스크를 읽는 방법은 오른쪽 → 왼쪽 이다.(오른쪽이 출발 도시, 왼쪽으로 갈수록 번호가 높은 도시)0 : 도시 3 방문 안 함1 : 도시 2 방문함1 : 도시 1 방문함1 : 도시 0 (출발지) 방문함 (시작 시 초기 세팅)tsp(visited, current) 에서 초기..

  • format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
  • · 2025. 4. 9.
[알고리즘] 위상정렬

[알고리즘] 위상정렬

위상 정렬방향 그래프의 정점들을 "선후 관계(의존 관계)"에 따라 나열하는 정렬 방법이다.단, 위상 정렬은 비순환 방향 그래프(DAG : Directed Acyclic Graph)에서만 가능하다 만약 순환이 있다면, 어떤 노드도 “처리 순서를 앞에 둘 수 없기 때문에” 선형 정렬 자체가 불가하다.(진입 차수가 0이 될수 없는 구간이 존재하고, 그러면 각 정점은 우선순위가 없으며 위상 정렬을 통해 탐색 순서를 정의할 수 없다) 위상 정렬 예시 : 라면 끓이기DFS 기반 위상 정렬깊이 먼저 따라가서, 끝에서 역순으로 쌓는다사리 부수기 → 사리 넣기 → 물넣기스프넣기 → 물넣기끓이기 → 물넣기밥 준비하기 (독립)✔️ 결과 예시 (역후위 순회) :밥 준비하기 → 사리 넣기 → 사리 부수기 → 스프 넣기 → 끓이..

  • format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
  • · 2025. 4. 3.
[알고리즘] 그래프

[알고리즘] 그래프

파이썬의 그래프그래프 관계(relationship)을 표현하는 자료 구조로, 파이썬에서는 어떤 관계를 표현할때 적합한 것은 사전(dictionary)이다. 그래프는 인접 행렬, 인접 리스트로도 나타낼 수 있다.  키(key) : 노드값(value) : 키와 연결된 노드 리스트#무방향 그래프graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}#방향 그래프graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}리스트를 이용하여 그래프를 나타내 보자. 리스트의 인덱스가 사전의 key에 해당하고, 인덱스의 값은 사전의 값과 똑같다.#무방향 그래프graph1 = [[], [2, 3, 5], [1, 3], [1, 2, ..

  • format_list_bulleted 카테고리 없음
  • · 2025. 4. 3.
[알고리즘] 트리 구조

[알고리즘] 트리 구조

트리 구조루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다형제 : 부모가 같은 노드를 형제라 한다조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 ..

  • format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
  • · 2025. 4. 3.
백준 : 2665 미로 만들기

백준 : 2665 미로 만들기

백준 : 2665 미로만들기문제 분석입력:첫 줄에 방의 수 N(1≤N≤50)이 주어진다.다음 N개의 줄에는 길이가 N인 수열이 주어지며, 각 수열은 '0'과 '1'로 이루어져 있다.출력:시작점에서 도착점까지 이동하기 위해 부숴야 하는 검은 방의 최소 개수를 출력한다.이 문제는 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾는 문제로 볼 수 있다. 각 방을 노드로, 상하좌우 이동을 간선으로 간주하며, 흰 방('1')은 가중치 0, 검은 방('0')은 가중치 1로 설정할 수 있다. 이러한 특성 때문에 0-1 BFS 또는 다익스트라 알고리즘을 활용하여 해결할 수 있다.최종 코드0-1 BFS를 활용한 해결import sys, mathfrom collections import dequeinput = sys..

  • format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
  • · 2025. 3. 31.