본문 바로가기

PS/프로그래머스

[프로그래머스 LV 3] 가장 먼 노드 (파이썬/python) 2021. 6. 21. https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 딱 보고 다익스트라네... 싶었는데 자세히보니까 bfs로도 충분히 풀 수 있을거라 생각해서 우선 bfs로 풀었다. bfs는 재귀의 깊이의 최소값을 보장해줄것이기 때문에 각 노드별 갈 수 있는 거리의 최솟값을 뽑아줄것이다. 다익스트라는 구현연습용으로 풀어봤는데 뭐 잘 풀렸다! 한 노드에서 다른 모든 노드로 가는 최단거리를 구할수있어 다익스트라는! bfs풀이와 결과 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..
[프로그래머스 LV 3 ] 등굣길 (파이썬/python) 2021. 6. 21. https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr ######## 이 문제 puddles 안에 있는 변수가 행, 열 순서가 아니라 열, 행 순서임 주의!!! ######## 처음에 단순 bfs문제인줄 알았다. 하지만 엄청나게 많은 경우의수가 있을 수 있다는 점을 깨닿고 동적계획법을 이용해서 효율성을 높히는 방법에 대해 생각해보게되었다. 수능수학 확통시간에 목적지로 갈 수 있는 경로의 수 문제를 보면 ..
[프로그래머스 LV 3] 정수 삼각형 (파이썬/python) 2021. 6. 21. https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 3레벨 문제는 아닌거같음 한 2레벨정도? 탑다운으로 풀면 훠얼씬 쉽게 풀 수 있지만 바텀업 연습을위해 바텀업으로 풀었음 dp[ i ][ j ] = max(그 위에 있는 고를 수 있는 값) + triangle[ i ][ j ]임 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def solution(triangle): dp = [[0 for j in range(len(triangle))] for i in range(len(..
[프로그래머스 LV 3] 여행경로 (파이썬/python) 2021. 6. 21. https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 옛날에 손도 못 댔던 문제들을 풀고있다... 약간 감격스러움.. 이 문제도 몇달전에는 풀다가 포기했던 문제다.. 정렬함수를 이용해서 도착지를 오름차순으로 정렬해줬다. 모든 경우를 dfs와 백트래킹으로 돌며 가능한 경로를 answer에 담았다. 첫번째 answer에 담길 값만 찾으면 된다. 정렬을 통..
[프로그래머스 LV 3] 단어 변환 (파이썬/python) 2021. 6. 19. https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr dfs와 백트래킹으로 문제를 풀어봤다. 할 수 있는 모든 경우를 탐색하며 가장 최소로 바꾸며 타겟 단어까지 바꾼 횟수를 리턴해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38..
[프로그래머스 LV 3] 베스트앨범 (파이썬/python) 2021. 6. 19. https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 딕셔너리에 장르별 총 재생횟수를 넣어주고 리스트에 노래별 장르, 재생횟수, 인덱스값을 넣어주었다. 정렬을해주고 답을 도출했다. 한 2달전에 풀때 뭔지 싶어서 건들지도 못했던 문젠데 좀 늘었나; 파이썬으로 바꾼게 컸나; 뭔진 모르겠지만 푸는데 이십분 안걸린것같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..
[프로그래머스 LV 3] 스티커 모으기 (파이썬/python) 2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 재귀 돌려서 완전탐색으로 풀었는데 시간초과가 퍼퍼퍼퍼펑 터져버린다. LV3 부터는 더이상 잔재주가 통하지 않는다는걸 느꼈음.... 좀 더 효율적인 풀이법을 생각해보자 완전탐색으로 실패했고 dp로 견적이 나온다는 생각이 들었다. 바텀업으로 생각을 해보면 i번째 스티커를 뽑았을 경우 i-1번쨰는 뽑을 수 없고 i-2번째는 뽑거나 안 뽑거나 의 경우가..
[프로그래머스 LV 3] 야근 지수 (파이썬/python) 2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr (맨 처음 풀이) n번의 반복문을 돌며 works 안에 있는 값 중에 가장 최대인 값에서 1씩 빼주는 식으로 만들었다. 그랬더니 테스트케이스는 잘 풀리는데 효율성 테스트에서 시간초과가 난다. 내가 짠 코드의 시간복잡도는 max( len(works) , n ) 이다. 이 뜻은 뭐냐.. 로직은 맞는데 효율적으로 풀지 못 했단 소리다 효율적으로 푸는 방..
[프로그래머스 LV 3] 멀리 뛰기 (파이썬/python) 2021. 6. 17. https://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 처음에 완전탐색으로 풀었고 시간 초과가 났다. 더 효율적인 풀이법을 생각하다 메모이제이션을 통해 기존에 구한 값은 더 이상 계산하지 말고 바로 반환할 수 있게 동적계획법을 사용했다. 나는 탑다운으로 푸는게 편해 일단 탑다운으로 풀고 바텀업으로 같은 로직을 한번 더 작성해봤다. 탑다운은 뒤에서부터 결과값을 ..

티스토리툴바