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

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

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

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

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

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

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 23.

백준 : 2470 두 용액

변수 설정N : 전체 용액의 수A : 주어진 용액의 특성값함수의 매개변수 : start, end이 문제에서는 target 설정이 불필요하다. A 리스트의 값을 더한 것의 절댓값 끼리의 비교이며, 0과의 거리가 가장 짧은 것을 구한다면, 절댓값이 가장 작은 수를 반환하면 되기 때문이다.문제 특성 상, 여러가지의 정답을 허용하기 때문에 어떤 값이라도 출력을 하고 그 값의 합이 0과 가장 가까운 값이라면 Pass를 준다.최종 코드def salt (start, end): best = float('inf') answer = (0, 0) while start 코드를 구성하며 어려운 점은, sum 값을 리스트에서 직접 받아와야 한다는 점과, 타겟 설정이 불필요하다라는 생각에 도달하기 까지 시간이 오래..

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

백준 : 2110 공유기 설치

백준 : 2110 공유기 설치백준의 2805 나무 자르기 문제와 동일하게 이진탐색을 이용하여 풀이하였고, 함수의 동작도 동일했다. 만약 나무자르기 문제 풀이를 완료했다면 동일한 로직으로 푸는데 크게 어려움이 없을것이라 예상된다.문제 이해이 문제는 문제의 요구사항을 이해하는게 관건이다. 문제 정의가 명확하지 않다면, 삽질을 할 가능성이 크다.N으로 주어진 집의 개수에 따라, C개의 공유기를 설치할 수 있는 최대 거리 중 각 공유기의 최소 거리를 구해야 한다. 요구 사항은 최소 거리를 리턴하는 것으로 정답은 하나만 있지만, 그 정답에 도달하는 방식은 여러개일 수 있다.즉 최소 거리는 동일하지만, 어떤 집에 설치할지는 다양할 수 있다. 주어진 집 간의 거리를 예시로 들어보자면,집의 좌표 : 1, 2, 8, 4..

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