컴공생 일상 블로그 컴공생 일상 블로그

Algorithm의 수행시간을 이론적으로 분석하기 위한 개념 수행시간은 환경에 따라 달라진다.(구현한 언어, 컴파일러, 컴퓨터의 스펙 등) 즉, 같은 환경적 요인들을 가졌을 때의 수행시간을 비교 아래 3가지에 대한 시간 복잡도를 주로 분석한다. ● Big-Oh Notation 빅오 표기법, 주로 사용하는 표기법이다. 왜 빅오표기법을 주로 사용하는가? - 'A라는 알고리즘이 최선의 경우 1초만에 문제를 해결한다.' 하지만, 최악의 경우 inf의 시간이 걸린다면, 의미가 있다고 할 수 있을까? 이보다는 'A라는 알고리즘은 최악의 경우에도 10초만에 문제를 해결해' 가 더 의미있을 것이다. - 두 함수 간의 관계를 나타내는 표기법 시간복잡도를 나타내는데 주로 쓰이지만, 별개로 함수의 증가속도(growth ra..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def solution(n, computers): visited = [0 for i in range(n)] answer = 0 def DFS(arg): visited[arg] = 1 for i in range(n): if computers[arg][i] and not visited[i]: DFS(i) for c in range(n): if visited[c..

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 def solution(numbers, target): result = 0 def dfs(num, level): nonlocal result if level == len(numbers): if num == target: result += 1 return signs = [-num, num] if level ==..

https://programmers.co.kr/learn/courses/30/lessons/87694# 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr Python, 프로그래머스 위클리챌린지 아이템 줍기이다. LV3 이라 ??? 했는데, 생각보다 쉽게 풀었다. 상자들이 인접할때, 넘어가는 것을 막기위해 크기 자체를 2배로 늘렸다. - 풀이 1. 2배 크기의 배열 선언 2. 1은 이동 가능한곳, 0은 이동 불가능한곳, 2는 아이..

https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 순열... 활용 쉽다. from itertools import permutations def solution(k, dungeons): cases = permutations(dungeons, len(dungeons)) # 순열 answer = 0 for c in cases: result = 0 temp = k for i in c: if temp >= i[0..

https://programmers.co.kr/learn/courses/30/lessons/87377?language=python3 코딩테스트 연습 - 교점에 별 만들기 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 1. 모든 교점을 구한다. - 나누는 수가 0일경우..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 어릴 때 학교 수학시간에 배웠었던, 최단거리 경우의수 문제이다. 아래 숫자들은 각 지점에 대한 최단거리로 도달가능한 경우의 수 개수이다. 1. 2차원 빈 리스트를 하나 만든다. 2. 시작점은 1로 한다. 3. 웅덩이는 0으로 한다. 4. 가로 첫번째 줄, 세로 첫번째 줄에 대해, 웅덩이를 만나기 전까지는 1, 웅덩이를 만난후에는 0으로 설정해준다. 5..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 처음에 아래와 같이 푸니까, 테스트케이스 5, 6, 7 다 틀려서 ..??? 했는데 이전 결과에 N연산만 하는 것이아니라, 숫자 4개의 조합의 경우 (3개로만들수있는경우 * 1개로만들수있는경우) , (2개로만들수있는경우 * 2개로만들수있는경우) 와 같이 모두 경우를 추가해줘야한다. - 코드 def solution(N, number): cases = {} if N==number: return 1 cases[1] = set({N}) for i in range(2, 9): temp = [int(str(N)*i)] for c_half in rang..