본문 바로가기

코딩 테스트107

[파이썬] 기지국 설치 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 n의 최댓값이 2억인데 채점 시 효율성 테스트까지 거치므로 시간 복잡도는 O(n)을 넘으면 안됨 n을 순회하기 보단 길이가 1만 이하인 stations를 활용해서 수학적으로 접근 한 지점에서 커버 하는 공간은 2*w + 1 이다. (좌우 + 자기 자신) 길이가 10이고 w가 1이면 10//3 을 통해 4개가 필요한 걸 알 수 있음 stations이 이미 있으므로 이것을 제외하.. 2023. 4. 17.
[2021 카카오 블라인드] 합승 택시 요금 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 S에서 출발해서 a,b에 도착하는 최소한의 비용을 출력하는 문제 s->k->a , s->k->b 를 구해야함. 한 점을 지나쳐서 다른 점을 방문하는 것이므로 플로이드 와샬을 떠올릴 수 있음 n의 갯수도 200 이하 이므로 시간 복잡도 괜찮 하지만 나는 다익스트라 최단 경로를 이용해서 특정 점에서 a와 b에 도착하는 최단 경로를 구해줌(시간을 더 최적화 시켜줄려고) dikstr.. 2023. 4. 17.
[탐색] 여행 경로 (python) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 BFS/DFS 중에서 BFS로 접근 경로가 여러개 일 경우 알파벳 순으로 사용하므로 ticket들 정렬 gr이라는 딕셔너리에 [출발 지역]:[tickets idx] 저장 큐에 현재 공항, 이용한 경로, 사용한 티켓 idx 를 담음 이용 경로의 갯수와 티켓+1 이 같으면 종료 (모두 사용한 거니까) 딕셔너리에서 키 값이 없는 것을 그냥 꺼내오면 에러가 나서 get으로 걸러내기 .. 2023. 4. 16.
[그리드] 섬 연결하기 (python) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 시작 노드가 주어지지 않는 채, 연결 정보들이 주어졌을 때의 모든 노드를 탐색 하는 최소 가중치(비용)를 구하는 문제 모든 노드를 탐색하면서 최소 가중치를 구하는 알고리즘을 짜야함. 이 때 크루스칼 알고리즘 떠올리는 짬이 있어야함 크루스칼은 주어진 정보들을 가중치를 기준으로 오름차순으로 정렬한 뒤, 하나하나 간선들을 이어나가는 과정 이 때, 특정 경로에서 하나의 왕복 루틴이 .. 2023. 4. 11.
[그래프] 가장 먼 노드 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1번 노드에서 출발 해서 각 노드들에 최단 경로로 도착하는데 그 중에 가장 멀리 떨어진 노드들의 갯수를 출력하는 문제 다익스트라로 풀었는데 노드 갯수만 적었다면 bfs dfs도 가능할듯? 소스 코드 import heapq INF = int(1e9) def solution(n, edge): answer = 0 gr = [[]for i in range(n+1)] dit = [IN.. 2023. 4. 10.
[2020 카카오 인턴십] 스티커 모으기(2) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1칸 띄워서 계산하는 문제이므로 개수가 3개 이하라면 그 수들 중 가장 큰 수가 정답이 됨. a, b, c 일 땐 a와 c도 합체가 안되므로 dp [n]=max(s [n]+dp [n-2], dp [n], s [n]+dp [n-3] ) 경우의 수 첫 번째 수부터 계산(이 경우 마지막 숫자는 빼줘야 함) 두 번째 수부터 계산(이 경우 마지막 숫자도 더하기 가능) 세 번째 수부터 .. 2023. 4. 7.
[2019카카오] 불량 사용자 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 불량 사용자 id에 해당 할 수 있는 유저 id를 전체적으로 다 찾아봄(해당 하는 유저id의 인덱스를 gr[불량사용자 인덱스]에 넣어줌) 그 뒤 bfs 방식으로 모두 탐색 제제 아이디 목록들을 구했을 때 순서와 관계없이 동일하면 같은 것으로 처리하기 때문에 집합으로 체크해줌 소스 코드 from collections import deque def solution(u_id, b_.. 2023. 4. 7.
[해시] 베스트 앨범 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 구해야 할 값은 각 장르의 총 합, 해당 장르에서의 최대 재생횟수 2개 추출 어떤 장르들이 있는지 알기 위해 장르 리스트를 집합화 시켜서 중복을 없애고 다시 리스트화 시켜줌(index 처리를 위해) 어떤 값이 최솟값이 될지 모르므로 "a"라는 장르는 -1 번 이라는 고정값을 넘겨주기 위해 gens와plays에 "a",-1 추가 g라는 리스트는 각 행에 [해당 장르 총 재생수,.. 2023. 4. 6.
[연습 문제] 숫자 게임 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 b가 최대 승점을 얻었을 때의 경기를 출력하는게 아닌 승점만 출력하는 문제 a의 순서를 바꿔도 상관 x (b가 그것에 맞춰 경기하는 방식이 되기 때문) a와 b를 내림차순으로 정렬 idx 를 0 으로 잡은 후, a[idx]와 b[0]의 최대 값을 계속 비교 b[0]가 a[idx]보다 크다면 a[idx]보다 작은 값들은 모두 b[0]보다 큰 값이므로 이후 비교 의미x b[0]>.. 2023. 4. 5.

티스토리툴바