코딩기록

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(..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 처음에 제출했을 때 시간 초과가 났다! 이유를 알아보니 파이썬은 input().split() 으로 입력하는 경우 입력량이 많기 때문에 시간 초과가 나는 것이었다... 시간 초과가 나지 않으려면 sys.stdin.readline() 을 사용해야 한다! 이 문제는 최단 거리를 찾는 문제로 너비 우선 탐색(BFS)을 이용하면 풀 ..

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 이 문제는 첫번째 집부터 마지막 집까지 하나씩 추가하면서 최대가 될 수 있도록 값을 구하면 된다. 인접한 두 집은 털 수 없기 때문에 "현재 i번째 집 money + i-2번째 집 money" 와 "i-1번째 집 money" 중 더 큰 값을 선택하면 된다. 즉, 점화식은 dp[i] = max(dp[i-2] + money[i], dp[i-1]) 가 된다. 이 문제는..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 이 문제는 동적계획법 문제로 왼쪽 위 집에서부터 모든 경우의 수를 계산하며 학교까지 가면 되는 문제였다. 최단 경로로 가기 위해서는 오른쪽이나 아래쪽으로만 움직여야 하므로 [i][j] 위치에 오는 방법은 [i-1][j] 에서 오른쪽으로 움직이거나 [i][j-1] 에서 아래쪽으로 움직이는 방법이다. 따라서 경우의 수를 구할 때 오른쪽이나 아래쪽만 고려해..

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 이 문제는 동적계획법 문제로 꼭대기부터 최대값이 될 수 있도록 업데이트하며 풀어야 하는 문제였다. 양쪽 끝인 경우에는 그 전 줄의 양쪽 끝에만 영향을 받으므로 값을 비교할 필요 없이 더해주기만 하면 된다. 가운데인 경우에는 그 전 줄의 두 값에 영향을 받으므로 값을 비교하여 더 큰 값을 더해주면 된다. 다음 예시를 보면 이해하기 더 쉬울 것이다. 예시로 이런 삼각형이 있다고 하겠다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 이 문제의 로직은 다음과 같다. 1. 숫자 N을 사용하는 숫자당 만들 수 있는 숫자 조합을 만든다. 2. 만들어진 숫자 조합에 number이 있으면 리턴한다. 3. 만들어진 숫자 조합에 없다면 1-2번 과정을 반복한다. N이 5인 경우를 생각해보자. 숫자 5를 1번 사용할 때 5 숫자 5를 2번 사용할 때 55 (이어붙이는 경우) 5+5(10), 5-5(0), 5*5(25), 5/5(1) 숫자 5를 3번 사용할 때 555 (이어붙이는 경우) 5+55(60), 5-55(-50), 5*55(275), 5/55(1/11) 5+(5+5)(15), ..