목록알고리즘 (56)
Hey Tech
BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이
📚 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 💡 접근법 ⚙️ 활용 알고리즘: BFS 저의 접근법은 다음과 같습니다. 2차원 리스트를 활용해 노드 간 연결정보를 업데이트하고 노드별 거리 정보를 저장할 1차원 리스트를 초기화합니다. 시작 노드를 큐에 삽입하고 해당 노드와 연결된 노드의 거리 정보를 시작 노드의 거리 정보에 1을 더해 업데이트합니다. 도착 노드를 다시 큐에 삽입하고 위의 과정을 반복합니다. 💻 My solution fr..
DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이
📚 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 💡 접근법 ⚙️ 활용 알고리즘: DFS 저의 접근법은 다음과 같습니다. DFS 알고리즘을 중심으로 0부터 시작하여 부모 노드에 number를 더하거나 빼는 작업을 동시에 수행하여 자식 노드를 생성하고, 해당 자식 노드를 다시 부모 노드로 치환해 위 작업을 반복 수..
완전 탐색 알고리즘 #프로그래머스 #모의고사 | 파이썬 구현
📚 문제 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/42840?language=python3 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 🤔 접근법 ⚙️ 핵심 자료구조: 완전 탐색 문제해결 전략의 핵심은 수포자별 '찍기 패턴'을 고려해 문제별 찍은 번호를 유추해 내는 것입니다. 본 문제에서 1번 수포자는 5개씩 한 패턴으로 정답을 찍고, 2번 수포자는 8개씩, 3번 수포자는 10개씩 찍는다는 것을 알 수 있습니다. 따라서 수포자별 정답 찍는 패턴..
큐/스택 자료구조 #프로그래머스 #기능개발 | 파이썬 구현
📚 문제 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 🤔 접근법 ⚙️ 핵심 자료구조: 스택 본 문제의 핵심 전략은 진도 업데이트 및 [0] 인덱스 기능의 진도가 100 이상 완수되었는지 반복적으로 확인하는 것입니다. 구현 과정을 조금 더 자세히 설명해 드리자면 다음과 같습니다. 먼저, 모든 기능의 진도(progresses)를 업데이트하고, [0] 인덱스 기능 개발이 완료되었는지(i.e...
다이나믹프로그래밍(DP) #프로그래머스 #정수 삼각형 | 파이썬 풀이
📚 문제 원본: https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 🔥 접근법 문제를 보자마자 전형적인 다이나믹 프로그래밍(Dynamic Programming, DP) 유형의 문제라고 생각합니다. 유사한 접근법을 사용한 DP 문제로서 "최저 비용의 노드만 거쳐 미로를 탈출하는 문제"를 접한 경험이 있습니다. 본 문제의 핵심 전략은 다음과 같습니다. 삼각형 맨 아래부터 2개의 인접한 자식 노드 중 큰 값을 부모 노드에 더해 부모 노드를 업데이트해 나가는 것입니..
BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이
📚 문제 링크: https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 👨💻 접근법 ⚙️ 활용 알고리즘: BFS 주어진 맵(i.e., 그래프)에서 아기상어와 떨어진 거리(i.e., 안전거리)의 최댓값을 구하는 문제입니다. 처음 생각한 아이디어는 상어가 없는(i.e., 빈칸) 노드에서부터 상어까지의 최소 거리를 구하는 것이었습니다. 하지만 해당 접근법은 연산 비용이 클 거라는 생각이 들었습니다. 이에 연산 비용을 최소화하기..
BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이
📚 문제 문제 원본: https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 👨💻 접근법 ⚙️사용 알고리즘: BFS 맵(i.e., 그래프)에 위치한 모든 양 각각을 기준으로 해당 양과 인접해 있는 다른 양의 존재여부를 확인하는 접근법을 활용했습니다. 🔥💻 소스코드 및 풀이과정 from collections import deque # 테스트 케이스 개수 입력받기 test_num = int(input()) # 탐색 방향별 이동할 좌표..
그리디(Greedy) 알고리즘 백준#1202 #골드 | "보석 도둑" | 파이썬 풀이
문제 원본 링크: https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근법 본 문제의 목표는 가격이 높은 보석을 최대한 많이 담되 용량이 적은 가방부터 차례대로 담는 것입니다. 이때 가방의 용량에 따른 탐색 순서를 고려하지 않으면 문제를 제대로 풀 수 없습니다. 예를 들어, 다음과 같이 (무게, 가치) 정보가 담긴 3개의 보석과 가방 2개가 있다고 가정해 보겠습니다. 여기서 가방의 용량..