728x90 반응형 알고리즘13 [백준] 9461 - 파도반 수열 삼각형으로 나선을 그리면서 삼각형이 추가 되어지고 문제는 그려지는 삼각형 중 N번째의 사이즈에 대해서 묻는 문제였습니다. 처음에 좀 헷갈렸던게 어디서 부터 삼각형이 그려지는 였는데, 간단하게 위의 그림 처럼 그려보니 빠르게 이해가 되었습니다. 그 이후에는 삼각형의 사이즈가 이루어지는 값들을 하나씩 적어봤고 5번째 삼각형인 3부터 (0,4) .... 10번째 삼각형 12까지 (5,9)로 하나씩 더해가면서 삼각형이 이뤄지는 것을 확인 했습니다. const fs = require('fs');const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';const input = fs.readFileSync(filePath).toStrin.. 2025. 2. 17. [백준] 13023 - 백트래킹 적용하기 들어가며안녕하세요, 오늘은 DFS(깊이 우선 탐색)와 백트래킹을 활용하여 친구 관계 탐색 문제를 해결하는 과정을 단계별로 살펴보겠습니다. dfs, bfs 문제를 풀고 백트래킹 문제를 풀려고 했는데 이렇게 바로 풀게 되었습니다.🤔 Before: 처음 마주친 문제 상황문제는 다음과 같습니다:N명의 사람들 사이의 친구 관계가 주어집니다.한 사람에서 시작하여 친구 관계를 4번 이상 거쳐갈 수 있는지 확인해야 합니다.가능한 경로가 존재하면 1, 없으면 0을 출력합니다.처음에는 단순히 DFS를 구현하면 될 것이라 생각했지만, 여러 문제점들에 직면했습니다:한 시작점에서만 탐색을 시작하여 모든 가능한 경로를 찾지 못했습니다.메모리를 많이 사용하는 인접 행렬 방식을 사용했습니다.이전 경로로 돌아가서 다른 경로를 탐색하.. 2025. 1. 27. [백준] 18511, 1260, 2606 / DFS, BFS 정리 / JavaScript DFS와 BFS의 실전적 이해: 백준 문제 풀이를 통한 완전 탐색 전략들어가며백준 문제를 풀면서 Greedy, DP 문제를 풀다가 드디어 항상 어려워했던 DFS, BFS 문제로 넘어오게 되었습니다. 완전 탐색 문제들을 풀면서 상황에 따라 DFS, BFS를 사용해야 할 필요를 느꼈고, 항상 개념만 알고 코드로 풀어내는 경험이 부족했던 것 같아서 정리하면서 글로 작성해보려고 합니다.DFS와 BFS의 기본 개념간단하게 이해하자면:DFS(깊이 우선 탐색): 경우의 수를 구할 때 그래프를 그린다면 나올 수 있는 가장 깊은 곳까지 갔다가 돌아오는 느낌BFS(너비 우선 탐색): 경우의 수를 구할 때 그래프를 그린다면 한 층씩 마무리해가면서 다음 단계로 넘어가는 느낌코드로 보는 실제 구현실제 구현에서 DFS와 BFS는.. 2025. 1. 25. [백준] 13305 - BigInt 사용하기 const fs = require('fs');const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';const input = fs.readFileSync(filePath).toString().trim().split('\n');//도시 마다 가야 되는 거리가 적혀있고//도시마다 기름값이 적혀있음//처음에는 첫 도시에서 기름을 넣어주고 다음 도시로 이동//다음 도시로 이동할 때 기름값이 더 싸면 그 도시에서 기름을 넣어주고 다음 도시로 이동//기름값이 더 비싸면 다음 도시로 이동//도착지로 이동할 때 필요한 최소비용을 구하라let N = parseInt(input[0]);let distance = input[1].split('.. 2025. 1. 15. [자료구조/알고리즘] - Queue/Deque 큐는 FIFO, First-In-First-Out 선입선출로 처리됩니다. 지난번에 스택을 정리할 때 테니스공, 셔틀콕을 넣는 통에 스택을 비유 했었는데, 큐의 경우에는 다른 예시 보다 책 예시가 좋은 거 같아서 적어본다. 우리가 흔히 식당에 들어가기 위해서 대기줄을 서는 경우가 있는데 그 때 제일 먼저 대기줄에 선 손님분들 부터 입장을 하게 된다. 이런 식으로 작동을 하는게 큐라고 보면 된다. 스택의 거의 모든 연산을 파이썬에서 지원해 주듯이 리스트는 큐의 모든 연산을 지원해줍니다. 주의할 점은 리스트는 동적 배열로 구현되어져 있어서 큐의 연산을 수행하기에는 효율적이지 않아, Deque라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 어제오늘 큐 문제를 최대한 많이 풀려고 했는데 파이썬으로 푼 문.. 2023. 5. 13. [자료구조/알고리즘] - 스택 자료구조를 배우게 되면 가장 많이 보게 되는 자료형이 아닐까 생각이 듭니다. 운영체제에서도 나오고 다른 CS 지식을 배우는 과정에서도 자주 나오는 자료형이라고 생각이 됩니다. 다음 글로 Queue에 대한 부분도 작성하겠지만 스택의 경우에는 Last-In-First-Out, LIFO(후입선출)에 해당 합니다. 1학년 때 자료구조를 들으면서 들었던 좋은 예시로는 테니스공이나 배드민턴 공을 넣는 통이 생각이 납니다. 위의 그림과 같이 제일 마지막에 넣은 셔틀콕을 우리가 셔틀콕을 사용하기 위해서 제일 먼저 꺼내게 됩니다. 파이썬에서는 스택 자료형을 별도로 제공하지는 않지만 리스트를 통해서 거의 대부분의 연산을 사용할 수 있습니다. 예를 들어서 pop()과 같은 기능을 제공받아서 일일히 스택에서 필요한 기능들을 .. 2023. 5. 11. 이전 1 2 3 다음 728x90 반응형
