동까의 코딩

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

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

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

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

베스트 앨범 문제 풀이 및 상세 설명프로그래머스의 베스트 앨범 문제는 각 장르별로 재생 횟수를 기준으로 노래들을 정렬하고, 장르의 총 재생 횟수가 높은 순으로 두 곡씩 선택하여 베스트 앨범을 구성하는 문제입니다.문제 해결 접근 방식문제를 해결하기 위한 주요 단계는 다음과 같습니다:장르별 분류:입력으로 주어진 genres와 plays 리스트를 이용하여, 각 장르에 해당하는 (재생 횟수, 인덱스) 튜플들을 저장합니다. 예를 들어, "pop" 장르에 속하는 노래들의 재생 횟수와 해당 인덱스를 함께 저장합니다.내부 정렬:각 장르별 리스트를 재생 횟수가 높은 순으로 정렬합니다. 만약 재생 횟수가 같은 경우, 인덱스가 작은 순으로 정렬하여 우선순위를 결정합니다.장르 정렬:전체 장르를 해당 장르에 속하는 노래들의..

위장 문제 풀이: 해시맵을 활용한 조합 계산프로그래머스의 의상 문제는 주어진 옷들의 조합을 통해 가능한 경우의 수를 계산하는 문제입니다.각 옷 종류별로 선택할 수 있는 경우의 수는 해당 종류의 옷 개수에 1을 더한 값이며, 모든 경우의 수를 곱한 후, 아무것도 선택하지 않는 경우를 제외한 값을 반환합니다.풀이 과정딕셔너리 생성:입력으로 주어진 clothes 리스트를 순회하며, 옷의 종류를 key로 하고, 해당 종류에 속하는 옷의 이름을 리스트에 저장합니다.조합 계산:각 옷 종류별로 선택할 수 있는 경우의 수는 len(옷 리스트) + 1입니다.이를 모든 옷 종류에 대해 곱한 값을 구합니다.결과 도출:최종적으로 모든 경우의 수에서 아무것도 선택하지 않는 경우(1)를 빼서 결과를 반환합니다.코드 구현def s..

해시를 이용한 전화번호 목록 문제 풀이프로그래머스의 전화번호 목록 문제는 주어진 전화번호 리스트 내에서 한 번호가 다른 번호의 접두사인 경우가 있는지 판별하는 문제입니다. 이번 포스트에서는 해시 테이블을 이용한 풀이 방법을 소개합니다.문제 개요문제 설명:전화번호 목록이 주어질 때, 한 번호가 다른 번호의 접두사(prefix)가 되는 경우가 있으면 False, 그렇지 않으면 True를 반환합니다.접근 방식:모든 전화번호를 해시 테이블에 저장한 후, 각 번호의 모든 접두사를 하나씩 확인하여 해시 테이블에 존재하는지 검사합니다. 단, 자기 자신과 비교하는 경우는 제외합니다.풀이 과정해시 테이블 생성: 전화번호 목록의 각 번호를 키로 하여 해시 테이블에 저장합니다.접두사 탐색: 전화번호 리스트에서 각 번호에..

브론즈 1 문제이지만 메모리 초과가 많이 나오는 문제라서 작성하여본다. https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net append / sort를 사용하면 메모리를 다시 재설정해줘서 추가하기 때문에 메모리 초과가 난다. 메모리를 미리 할당 시켜주고, 해당 인덱스에 1씩 더해줘서 처음부터 추가된 숫자 인덱스만큼만 출력해주면 답이 나온다. import sys n = int(sys.stdin.readline()) num_list = [0] * 10001 for _ in..