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

https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 문제자체는 간단하다. 1. 진수변환 2. 조건에 맞는 소수 판별 # 어찌저찌 길이 줄여봄... import math def solution(n, k): num = '' while n > 0: n, mod = divmod(n, k) #몫과 나머지를 돌려줌 num += str(mod) numbers = [int(i..

https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 풀긴 풀었는데, 효율성이 좋을지는 모르겠다. 유저 : (신고한 유저목록) 과 같은 자료구조를 만들고 , 게시판 이용이 정지되는 유저목록을 구해서 교집합 연산 후에 개수를 세서 발송해야하는 메일 개수를 구하면된다. from collections import defaultdict def solution(id_list, report, k): result, ba..

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 예전에는 dp문제가 어려웠는데, 그렇게 어렵지도 않은 것 같다. 효율성 테스트도 한번에 통과했다. 위와 같이 삼각형의 일부분에 대해, 1을 지나가는 경우는, 3을 지나고 1을 지나는 경우와 8을 지나고 1을 지나는 경우 두가지밖에 없다. 즉 삼각형이 양 끝의 경우에 대해 if문으로 처리해주고, 그 가운데들에 대해서는 두 가지경우중 더 큰 경우를 선택하면서 삼각형테이블을 채우다보면, 맨 마지막 행중 최대값이 ..

1. 일반적인 마스터 정리 T(n) = rT(n/c) + O(f(n))을 만족 하는 경우 3가지의 경우로 복잡도를 구할 수 있다. 2. 등차수열의 경우, T(n-2) + T(2) + O(n)과 같은 경우 3. 마스터정리를 만족하지 않는 경우, recursion tree를 그려서 복잡도를 구하는 경우 3_1. 만약 트리의 각 층의 너비가 같은 경우 : 트리의 높이 * 너비 3_2. 만약 트리의 너비가 작아질 경우 : 등비가 1보다 작은 등비수열의 합으로 표현가능, 즉 특정 상수에 수렴한다. 3_3. 만약 트리의 너비가 커질 경우 : 트리의 잎의 개수, (나누어지는 자식노드의 개수)^트리의 높이 3_2와 3_3의 예제. (algorithms-Jeff 49p 7번 의 (k), (l)) K(n). 공비가 1보다..

분할 정복 : 말그대로 문제를 분할하여 정복하여 풀이 - 분할 정복의 대표적인 예시 : Merge Sort 병합정렬 1. 주어진 배열을 두 부분으로 나눈다. 2. 두 부분배열을 각각 Mergesort한다. 3. 정렬된 부분배열을 합쳐서(merge) 하나의 정렬된 배열로 만든다. MergeSort(A[1...n]): if n > 1: m = [n/2] MergeSort(A[1...m]) MergeSort(A[m+1...n]) Merge(A[1...n], m) - Divide and Conqur의 설계 1. 문제를 동일한 작은 문제들로 나누어라 2. 각각의 작은 문제들을 재귀요정에게 맡겨라(일단 같은 작은 문제들을 던져주면 알아서 해결해준다.) 3. 최종 해결법은 작은 문제들에 대한 답을 결합해라. * 어떤..

재귀.!, 알고리즘의 이해와 설계에 매우 중요한 기술 Recursion의 예. 1. 팩토리얼 연산 2. 자연수의 정의 - 1은 자연수이다. (Base case) - n이 자연수이면, n보다 1큰수도 자연수이다. Reduction (= 축소) 어떤 문제X에 대해 Y로 축소해라. X라는 문제를 풀기위해, Y를 푸는 함수를 호출한다. 이때 Y를 어떻게 풀것인지는 신경쓰지않는다. 이때, Y를 푸는 함수는 어떻게 작동하는지는 모르지만(신경x), 항상 옳게 Y를 풀어낸다. Example - 배열 A[0...n-1]에서 최소값 찾기 1. A를 정렬한다. 2. return A[0] - Selction(A[0...n-1], k) 배열 A[0...n-1]에서 k번째로 작은 값 찾기 1. A를 정렬한다. 2. return ..

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