본문은 프로그래머스 K-Digital Credit 강좌를 수강하고 작성한 게시물입니다. 문제 https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 본 문제는 그리디 알고리즘에 속하는 문제이다. '전파 범위(w)만큼 오른쪽으로 이동해서 기지국을 세운다면 세워진 기지국에 의한 전파의 유효범위가 최대가 된다'라는 아이디어가 핵심이었다. 이때, 기지국을 세우고자 하는 위치가 이미 전파 범위 안에 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차_전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 풀이 브루트포스 + 그래프 탐색을 이용해 풀 수 있는 문제였다. 기본 문제풀이 로직은 다음과 같다. for문을 통해 그래프의 간선을 하나씩 제외한다. 나머지 간선들로 그래프를 초기화한다. 간선이 n-2개 존재할 시 그래프는 2분할되므로 각 영역에 속한 노드 수의 차를 구하고 answer을 갱신한다. 중요한 점은 그래프가 트리 구조로 되어있다는 것이다...
문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 풀이 트리 구조로 입력이 주어지지만, 딱히 트리 구조를 구현할 필요는 없는 구현 문제였다. 부모 노드를 통해서 조상 노드를 계속해서 탐색하며, 수익을 계산해주면 된다. 이때, 수익을 계산하는 방식을 눈여겨봐야한다. 조상 노드부터 현재 노드까지의 서브 트리가 가질 수 있는 총 수익을 total_profit이라고 할 때, ※ total_profit은 매 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 풀이 간단한 구현 문제였다. 파이썬에선 defaultdict, 자바에선 HashMap 자료구조를 이용해서 풀 수 있었다. 다만, "Leave"의 경우엔 "Enter"나 "Change"와 달리 split한 배열의 길이가 2가 되므로 이에 주의해야 한다. 코드 파이썬 from collections import defaultdict def solution(rec..
문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 기본 아이디어는 순회를 하면서 주어진 두 배열의 원소를 비교하는 간단한 문제였다. 문제의 제한사항 중 '중복된 원소가 없다'라는 조건이 있었는데, 이를 이용하면 간단하게 문제를 풀 수 있다. 코드 파이썬 def solution(lottos, win_nums): answer = [] zero_cnt = 0 ..
