목록알고리즘 PS (108)
DevKim
programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] bigin부터 덱에 넣어주고, 한글자만 다른지 여부를 판별해준뒤 한글자만 다르다면 덱에 넣어준다 (target이 될 때까지 반복) [코드] from collections import deque def solution(begin, target, words): cnt = 0 que=deque() n=l..
programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr [ 알고리즘 ] BFS [문제 접근] (생략) [코드] from collections import deque def solution(n, computers): que=deque() cnt = 0 visited=[0]*(n) for i in range(n): computers[i][i]=0 if 1 in computers[i]: # 외톨이가 아니면 continue else..
programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [ 알고리즘 ] DFS [문제 접근] 아 이 문제 때문에 애를 많이 먹었다.. 사전 순으로 정렬을 시켜야하나, 또 그것이 타고타고 갔을 때 끊겨버리면 안되기 때문에, 하나의 공항에서 끝까지 갔을 때 이어지는지 여부를 따로 체크하려고하다보니 많이 복잡해졌다.. DFS를 이용하여 항공편이 더이상 남아있지 않았을 경우에만 pop하여 answer에 ..
programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr [ 알고리즘 / 자료구조 ] 해시 [문제 접근] defaultdict으로 list 형태의 딕셔너리를 생성해주고, 제한 사항에 맞춰 하나씩 정렬해주고 조건을 달아주면 된다 [코드] from collections import defaultdict def solution(genres, plays): answer = [] dic=defaultdict(list) max_g=defau..
programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr [ 알고리즘 ] DP [문제 접근] 1,2만을 이용해서 n을 만드는 문제와 같다고 생각하여 바로 DP를 떠올렸다. 규칙을 찾기 위해 1~5칸 까지 종이에 그려보고, 규칙성을 찾아냈음 종이에 그려보고 바로 규칙을 찾은걸보면 DP 중엔 쉬운 문제라고 생각이 든다 *dp table을 [0]*(n+1) 로 하면 런타임에러가 떠..
programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 처음에 순열로 풀었다가 시간 초과 나서 어떻게 풀지 고민했던 문제. 해답은 팩토리얼로 구하는 간단한 문제였다programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져..
programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 문제 자체는 어렵지 않으나, 하나씩 다 구해서 최대값 구하면 안되는 문제이고, 아이디어가 딱 떠오르면 풀리는 문제 중 하나이다. 두 수의 차가 적어야 곱이 큰 것만 깨달으면 빠르게 풀어나갈 수 있는 문제 [코드] def solution(n, s): answer = [] if n > s: # 존재하지 않는 경우 ret..
programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 처음에 row와 col을 뒤집는 과정이 이 문제의 핵심키라고 생각한다. 이 문제를 통해 zip을 사용하여 한줄로 row와 col을 뒤집는 코드를 배웠다. 집합 set을 이용하여 2*2의 겹치는 캐릭터들을 합쳐주며 중복은 없애주고, 중복되어 없어진 부분을 임의의 문자로 채워주었다. 더 이상의 삭제되는 프렌즈가 없을 때까..