백준 : 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 알고리즘 문제풀이
• · 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 알고리즘 문제풀이
• · 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 알고리즘 문제풀이
• · 2025. 3. 29.

백준 : 1197 최소 스패닝 트리

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

• format_list_bulleted 알고리즘 문제풀이
• · 2025. 3. 29.

백준 : 11053 가장 긴 증가하는 부분수열

문제 이해수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)을 구하는 프로그램을 작성하라. 여기서 가장 긴 증가하는 부분 수열이란, 어떤 수열에서 원래 순서를 유지하면서 앞보다 뒤가 점점 커지는 숫자들이며 그 중 가장 길게 고를 수 있는 경우를 출력하면 된다.문제 분석처음 이 문제를 접했을 때, 가장 먼저 고민한 것은 start와 end 값을 어떻게 정해야 할지였다. 이진 탐색의 구조를 떠올리긴 했지만, target 값은 매 반복마다 바뀌게 되고, 우리가 구하고자 하는 건 "원래 위치"가 아니라 LIS를 만들기 위한 위치이기 때문에 mid 값이 의미가 있는 건지 확신이 서지 않았다. 원래의 위치를 정확히 추적하려면 리스트를 정렬할 수 없고, 그렇다면 이진 탐색을 어떻게 시작할지 막막했다.초기 ..

• format_list_bulleted 알고리즘 문제풀이
• · 2025. 3. 23.

[크래프톤정글] 정글에서의 생활

정글에 입소하기 전에 가장 걱정했던 부분 중 하나는 기숙사의 환경과 밥을 어떻게 해야하는지였다. 추후 정글을 지원하려는 분들을 위한 기록용으로 간단하게만 소개한다.기숙사 입소입소 당일에 짐이 너무 많아서 택시를 타고 왔다. 다행히 집이랑 그리 멀지 않기도 하고, 늦게 출발하니 막히는 시간에서 벗어나서 거의 하이패스로 도착할 수 있었고 택시비도 예상보다 훨씬 덜나왔다. (네이버 지도보다 약 1만원 정도 덜나와서 기분 좋았다) 그리고 기사님이 짐 많은 중생을 많이 도와주셔서 덕분에 잘 도착할 수 있었다.기숙사는 안내되는 바와 같이 2인 1실이다. 지금은 짐이 다 차있어서 그나마 입소하자 마자 찍어둔 사진으로나마 공유한다.참조로 기숙사에는 책상이 없다. 공부는 무조건 강의실에 와서 하거나 캠퍼스 곳곳에 놓여있..

• format_list_bulleted 크래프톤정글 (2025.03-07)
• · 2025. 3. 23.