동까의 코딩

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 라는 문구가 있는 걸 보고, 알고리즘으로 풀어야겠다는 마음을 먹게 되면서 효율성을 따지는 구현을 생각해보게 되었습니다. 맵 크기가 N x M 크기로 주어지고, 항상 직사각형 모양으로 되어있고, 특정 좌표 두개가 주어지면 그 좌표들의 직사각형만큼 공격을 당하거나, 회복을 하는 문제입니다.type, r1, c1, r2, c2, degree 가 주어지고, type 이 1이면 degree만큼 공..

1. BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.BFS(너비 우선 탐색)는 그래프나 트리에서 시작 정점에서부터 인접한 노드를 먼저 방문하는 알고리즘입니다. BFS의 핵심 아이디어는 시작 정점으로부터 거리가 가까운 노드들을 먼저 처리하고, 그 다음 거리에 있는 노드들을 차례대로 탐색하는 것입니다.먼저 BFS의 작동 원리를 정리하면 다음과 같습니다.시작 정점 선택: 탐색의 출발점이 되는 정점을 선택합니다.큐(Queue) 사용: BFS에서는 FIFO(First-In, First-Out) 원칙을 따르는 큐를 사용합니다. 즉, 먼저 방문한 정점부터 처리하게 되어, 각 단계별(레벨별)로 노드를 확장합니다.인접 노드 방문: 현재 정점..

파이썬 프로그래머스 - 게임 맵 최단거리문제 설명프로그래머스의 게임 맵 최단거리 문제는 직사각형 모양의 맵에서 시작점(0, 0)에서 도착점(n-1, m-1)까지 이동할 때 거쳐야 하는 최소 칸 수를 구하는 문제입니다.맵은 1과 0으로 구성되며, 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타냅니다.상하좌우 방향으로만 이동할 수 있으며, 시작점과 도착점은 항상 1입니다.문제 접근 방식BFS(너비 우선 탐색) 활용시작점에서 출발하여 도착점까지 도달하는 경로 중, 가장 짧은 경로를 찾아내기 위해 BFS를 사용합니다.방문 처리방문한 칸을 추적하여 중복 방문을 방지합니다.거리 기록현재까지 이동한 거리를 maps 배열에 기록하여, 각 칸에 도달하는 데 필요한 최소 이동 횟수를 저장합니다.종료 조건도착점에..

파이썬 [프로그래머스] - 양과 늑대문제 설명"양과 늑대" 문제는 트리 형태로 구성된 노드에서 양과 늑대가 존재하는 상황에서, 루트 노드부터 시작해 이동하면서최대한 많은 양을 구하는 문제입니다. 각 노드는 0(양)과 1(늑대)로 표시되며, 이동 중 언제나 양의 수가 늑대의 수보다 많아야 합니다.문제의 목표는 가능한 경로들 중, 조건을 만족하면서 최대한 많은 양을 모으는 경우의 양의 수를 구하는 것입니다.문제 접근 방식DFS(깊이 우선 탐색) 활용노드들을 깊이 우선 탐색하면서 현재까지 모은 양(sheeps)과 늑대(wolves)의 수를 관리합니다.방문 배열 사용각 노드의 방문 여부를 추적하여 중복 방문을 방지하고, 다른 경로 탐색을 위해 방문 상태를 초기화합니다.조건 검사DFS 내에서 매번 sheeps >..

파이썬 [프로그래머스] - 네트워크문제 설명프로그래머스의 네트워크 문제는 여러 컴퓨터가 연결되어 있는 네트워크의 개수를 구하는 문제입니다.컴퓨터들의 연결 정보는 2차원 리스트(인접 행렬)로 주어지며,연결된 컴퓨터들은 하나의 네트워크를 구성합니다.문제의 목표는 주어진 컴퓨터들의 연결 정보로부터 총 네트워크의 개수를 찾는 것입니다.문제 접근 방식방문 배열(visit) 생성 각 컴퓨터가 이미 네트워크 탐색에 포함되었는지 확인하기 위해 visit 리스트를 생성합니다.깊이 우선 탐색(DFS) 활용 한 컴퓨터에서 시작하여 연결된 모든 컴퓨터들을 재귀적으로 탐색합니다.탐색 중 방문한 컴퓨터는 visit 리스트를 통해 중복 방문을 방지합니다.네트워크 수 카운팅 아직 방문하지 않은 컴퓨터가 발견되면 DFS를 실행하..

1. DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요1. 재귀 호출을 이용한 DFS장점:간결하고 직관적: 재귀 호출을 사용하면 코드가 간단해지고, DFS의 기본 개념(현재 노드에서 다음 노드로 자연스럽게 진행)을 직관적으로 표현할 수 있습니다.내장 스택 활용: 프로그래밍 언어의 함수 호출 스택을 활용하기 때문에 별도의 자료구조를 구현할 필요가 없습니다.단점:스택 오버플로우 위험: 탐색 깊이가 매우 깊거나 그래프가 크면 함수 호출 스택이 넘칠 수 있습니다.제어의 한계: 재귀 과정 중에 스택 상태를 직접 제어하기 어렵기 때문에, 특정 상황에서 세밀한 제어가 필요한 경우에는 유연성이 떨어질..

파이썬 [프로그래머스] - 가장 큰 수문제 설명프로그래머스의 가장 큰 수 문제는 주어진 숫자 배열을 이어 붙여 만들 수 있는 가장 큰 수를 반환하는 문제입니다.예를 들어, [6, 10, 2]가 주어지면 숫자들을 적절히 이어 붙여 6210을 만드는 것이 목표입니다.문제 접근 방식문자열 변환 주어진 숫자들을 문자열로 변환합니다.정렬 기준 설정 각 숫자 문자열을 반복하여 비교 기준을 만듭니다.예를 들어, 숫자 3은 "333"으로, 숫자 30은 "303030"으로 변환하여 비교합니다.문자열은 첫 인덱스가 같으면 다음 인덱스로 넘어가서 대소비교를 하기 때문에 숫자 '30'이 뒤로 밀립니다.내림차순 정렬 변환된 문자열들을 내림차순으로 정렬하여, 이어 붙였을 때 가장 큰 수가 나오도록 합니다.결과 조합 및 반환..

파이썬 [프로그래머스] - 기능개발문제 설명프로그래머스의 기능개발 문제는 각 작업의 진행 상황(progresses)과 작업 속도(speeds)가 주어졌을 때,작업이 100% 이상 완료되면 배포하는 방식으로, 배포마다 동시에 몇 개의 작업이 완료되는지를 구하는 문제입니다.문제 조건각 작업은 매일 일정한 속도로 진행됩니다.작업은 순서대로 배포되며, 앞 작업이 완료되어야 뒷 작업도 함께 배포될 수 있습니다.한 번의 배포에 여러 작업이 동시에 완료될 수 있습니다.문제 접근 방식시간 시뮬레이션 time 변수를 사용해 경과한 날짜를 추적합니다.완료 조건 체크 각 작업의 진행도는 progress + time * speed로 계산합니다.첫 번째 작업이 100% 이상이면 작업을 제거(pop)하고 배포할 작업의 수(c..