No Limitation

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 유형의 정석과도 같은 문제이다. 아예 이 문제를 암기해도 괜찮을거 같다. 참고 포스팅 : https://www.youtube.com/watch?v=2IkdAk1Loek https://velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-2293-%EB%8F%99%EC%A0%84-1 이 문제는 쉽게 말하면 부분 문제로 전체 문제를 푸는 아이디어에 기초한다. 예를 ..

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr Fact Finding Index를 이용해 해당 노드 별 max값을 저장한 memo 이용 Recursion을 이용하여 노드 탐색 def depth_search(triangle, start, i, j, memo = {}, sums1=0, sums2=0) : if (i, j) in memo : return memo[(i, j)] if i == len(triangle): return max(sums1, sums2..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제는 단순 구현 문제였다. 다음과 같이 빗물이 있으면 빗물을 담기게 할 수 있는 양을 구하는 문제인데 예를 들어 위의 검정색을 건물(?)이라고 치면 건물을 구성하는 부분을 1, 하얀색으로 빈 부분을 0이라고 하자. 저 그림을 이중 배열을 통해 나타낼 수 있는데 다음과 같이 나타낼 수 있다. [ [ 0, 0, 0, 0, 1, 0, 0, 0 ] [ 1, 0, 0, 1, 1, 0, ..

https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr [ 이 문제는 복습을 꼭 해보자 ] 첫 번째 시도 차량 이동 시간의 폭이 좁은 얘를 기준으로 정렬해서 접근 해당 시간대에 카메라를 위치시킴으로서 카메라의 갯수 최소화 어느 구간이 포함되는 지에 따라 routes 갱신 구현 코드 def check(route1, route2) : if route1[0] > route2[1] or route1[1] < route2[0] : return False return True def solution(..

https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 본 문제는 MST(Minimum Spanning Tree) 문제로, MST를 푸는 대표적인 방법인 Kruskal과 Prim 알고리즘으로 풀 수 있습니다. MST에 대해서는 추후에 자세하게 다루도록 하겠습니다. 저는 본 문제를 크루스컬 알고리즘을 활용하여 풀었습니다. 크루스컬은 Union Find 알고리즘을 통해 Cycle을 체크하였고 기존 path를 정렬하여 가장 path가 적은것부터 탐욕적으로 선택하는 방법으로 문제를 풀었습니다..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택큐 유형의 전형적인 문제인 연산자 관련 문제이다. 본 문제에서는 괄호의 순서에 맞는 연산을 수행해야 하며 괄호를 형성하지 못하는 경우 0을 반환해야 한다. ( ) = 2 [ ] = 3 (..) = 2 * .. [..] = 3 * .. (..)[..] = (2 * ..) + (3 * ..) 다음과 같은 연산 성질을 갖는다. 구체적으로 예를 들어 살펴보자 (()[[]])([]) 다음은 알고리즘 ..

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 Fact Finding DFS 문제를 통해 모든 곳을 방문할 수 있는 경로를 저장 Algorithm Flow Recursion을 통한 DFS 구현 후 경로를 answer에 저장 start_point 체크를 통해 모든 곳을 방문할 수 없는 경우 filter next의 sort과정을 통해 알파벳 우선인..

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr Fact Finding DFS 문제를 통해 최소 변환 횟수를 찾기 Algorithm Flow recursion을 통한 DFS 구현 후 가장 최소의 경우를 final_result에 저장 여기서 주의해야 할 부분이 바로 global 변수의 활용이다!! 구현 코드 # 반례 # hit # cog ..

https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr Fact Finding Disjoint Set을 찾는 문제 Algorithm Flow Union Find(union by Rank) 알고리즘을 사용하여 Disjoint Set을 나눔 Disjoint Set을 찾는 알고리즘인 Union Find에 대해서는 추후 포스팅에서 자세하게 다루겠습니다! ( 양이 너무 많아질 거 같아서 ㅠ..

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr Fact Finding 재귀 함수를 통한 DFS 구현 '+'와 '-'를 번갈아서 적용해주어 모든 경우의 수를 check 이 중 타겟 넘버와 일치할 때 +1 증가시키고 recursion 수행 Time Complexity 최악의 경우 O(n^2)로 판단되는 데 정확히 분석한 것인지 확실하지 않음 def probl..