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

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