백준 : 1379 강의실2

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

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

백준 : 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.

백준 : 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.

백준 : 14888 연산자 끼워넣기

백준 : 14888 연산자 끼워넣기문제 접근N개의 수가 주어지고, 그 사이에 넣을 수 있는 +, , , // 연산자의 개수가 주어집니다.모든 연산자를 한 번씩 사용하여 식을 만들 수 있고,가능한 모든 결과 중 최댓값과 최솟값을 출력해야 합니다.각 숫자 사이에 들어갈 연산자의 조합을 모든 경우의 수로 시도해봐야 한다. 즉 완전 탐색이 필요하고, 이 때 DFS + 백트래킹이 가장 적합하다.최종 코드import sys, operatorinput = sys.stdin.readlinedef dfs(index, current): global maxV, minV # 모든 숫자를 다 사용했다면 최대/최소값 갱신 if index == N : maxV = max(maxV, current) ..

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

백준 : 1260 DFS와 BFS

백준 : 1260 DFS 와 BFS문제 분석M : 정점의 개수 , N : 간선의 개수, V : 탐색 시작할 정점N개의 간선으로 연결된 정점의 번호DFS, BFS 탐색 결과를 출력한다.단, 1) 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 2) 입력으로 주어지는 간선은 양방향이다.우리는 저 두 가지에서 키를 얻어야 한다. 첫 번째는 입력값이 주어졌을 때, 정렬을 통해 작은 숫자부터 탐색하도록 탐색 함수를 설계해야 한다는 것이며. 두 번째는 주어진 그래프는 무방향 그래프이다. 이 두가지에 유의해서 탐색 함수를 만들어보자.최종 코드인접 리스트를 활용하여 구현한 DFS, BFS 탐색import sysfrom collections import defaultdict, deque..

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

백준 : 1197 최소 스패닝 트리

Kruskal 은 “ 간선 중심 “ 알고리즘이다가장 작은 가중치의 간선부터 하나씩 선택하며 사이클이 생기지 않도록 주의해서 신장 트리를 만들어간다이때 가장 중요한 건 간선 정렬과 Union-Find 자료구조를 통한 사이클 판별이다Prim 은 “ 정점 중싱 “ 알고리즘이다하나의 정점에서 시작해서, 아직 방문하지 않은 정점 중에서 가장 가까운 정점으로 확장해나간다이때는 Min-Heap (우선순위 큐)을 활용해서 매번 가장 짧은 간선을 빠르게 선택한다두 알고리즘 모두 MST를 구하지만, 그 접근 방식이 다르기 떄문에 구현을 해보면서 내가 어떤 자료구조를 다루고 있는지, 문제가 어떤 그래프 구조를 가졌는지에 따라 알고리즘 선택이 달라질 수 있음을 알 수 있었다.결론 도출결과는 같더라도, 과정은 전혀 다르다→ 같..

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