코딩기록

https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr BFS만 사용하면 마지막 테스트 케이스가 통과되지 않는다! BFS + DP의 조합으로 ..

https://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 이 문제는 Level5 답게 굉장히 어려웠다.. 그래서 어떻게 방의 개수를 셀 수 있는지 전혀 생각나지 않았다... 그래서 문제를 풀지는 못하고 다른 사람의 풀이를 보고 정리를 했다. 방의 개수를 어떻게 구할 수 있는지에 대한 것은 이 링크를 참고하면 좋을 것 같다. 굉장히 상세하게 정리해주셔서 도움이 많이 되었다. 결론만 말하자면, 방이 생성되려면 "방문한 노드가 이미 방문한 적 있으며 해당 노드로 들어온 경로는 처음인 경우" 이다. ..

https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 이 문제는 처음봤을 때 이기고 지는 관계이므로 선후관계가 있다고 생각해서 위상정렬을 사용해서 풀어야겠다고 생각했었다. 위상정렬로 풀려고보니 위상정렬을 사용하기 위한 조건을 만족하지 못했다. 다른 사람의 풀이를 보고 사용한 알고리즘만 확인했다. 플로이드 워셜 알고리즘을 사용하면 풀 수 있었다. 예전에 공부한 것을 바탕으로 문제를 풀었다. def solution(n, results): answer = 0 graph = [[0] * (n+1) for _ in range(n+..

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를 공부했어서 쉽게 풀 수 있었던 것 같다. from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] # 연결된 노드 정보 그래프 distance = [-1]..

https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이 문제는 이분 탐색 문제였다. 이분 탐색 문제는 어느 문제든 코드 구조는 정말 비슷한데 이분 탐색할 대상? 기준? 을 찾는 것이 어려운 것 같다. 여러 문제를 풀어보면서 보는 시각을 키워야 할 것 같다. 이 문제에서는 최소 거리를 이분 탐색 대상으로 삼았다. 최소 거리를 특정한 다음 바위를 제거해가면서 n과 맞는지 확인한다. n과 최소 거리가 모두..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 이 문제는 이분탐색 문제였다. 어느 부분을 이분 탐색하는지 감이 잡히지 않아서 다른 사람들이 푼 방법을 보고 코드를 짰다. def solution(n, times): answer = 0 left = 1 right = max(times) * n # 이분탐색 수행 while left < right: mid = (left + right) // 2 count = 0 fo..

https://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 문제였다. 각 시작점의 인접 리스트를 구한 후 도착점을 알파벳 순서로 정렬하는 것까지는 생각할 수 있었다. 처음에는 재귀함수로 이 문제를 풀려고 했었다. 인접리스트에 값이 있으면 재귀함수를 호출하고 재귀함수가 끝나면 경로에 추가하는 식으로 했는데 뭔가 잘 안되..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 이 문제는 최소 변환 수를 찾는 거였어서 BFS 문제인 줄 알았으나 코드를 짜다보니 DFS 문제였다. 책에서 DFS 문제는 재귀함수로 풀라고 되어 있어서 재귀함수만 생각하다보니까 잘 생각이 안났다.. 다른 사람의 코드를 보니 스택을 이용한 코드가 많았다. 쉽게 이해되는 코드를 참고해서 이해했다. def solution(..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 이 문제는 DFS(깊이 우선 탐색) 문제이다. 끝까지 탐색하면서 네트워크를 개수를 세면 된다. 코드를 짜고 실행해보는데 에러가 발생했다. 찾아보니 재귀함수 호출이 너무 많아서 그런거였다. 코드 구조도 바꾸어 봤는데도 계속 이 에러가 떠서 다른 사람 코드를 보고 구조를 똑같이 했는데도 에러가 났다... 그러던 중 코드에서 변수를 잘못 입력해서 (j 자리에 i..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 이 문제는 깊이 우선 탐색(DFS) 를 사용하면 되는 문제였다. 왜 DFS를 사용하면 되는지에 대한 설명은 다음과 같다. 처음에는 dfs 메서드를 solution 밖으로 뺐었는데 뭔가 자꾸 에러가 나서 그냥 바꿨다... def solution(numbers, target): answer = 0 n = len(..