chap3. Dynamic programming(planning) 작은 문제가 반복되는 경우에 작은 문제를 계산하여 한번 계산한 값을 저장하고 검색 후 재사용하는 방식. = recomputing 대신 look up table 만들기. fibonacci number DP의 핵심 스텝 DP는 schedule을 사용하여 문제를 효율적으로 풀지만 메모리를 추가로 사용하고 divide and conquer는 문제를 blindly(무턱대고) 풀며, 스케줄링과 planning이 없다. - 겹치는 계산이 없을 때 쓰면 좋음. Compute binomial coefficient=이항계수 문제 계속 이전 항끼리의 합을 구하는 방식이라 겹치는(over lapping)부분과 반복되는 계산이 많다. basic operation..
chap2. Divide and conquer problem을 subproblem으로 나누어 따로 풀고 합치는 방식. = top→ down approach 3-basic step Divide conquer(solve subP) if necessary combine binary search = sorted input = T(n) = T(n/2) -> time complexity = logn every time complexity recurrence relation Master Theorem 재귀방식에 적용 가능한 time complexity 구하는 법 재귀함수가 몇번 불렸는지(a) 몇 개로 나누어 푸는지(b)를 구하고, 함수 T(n)의 재귀 외의 나머지 함수에 대해서 n^d 형태로 만들어 d를 구한다. 그..
알고리즘 중간범위 알고리즘의 정의, 수학적 귀납법, 알고리즘 효율성의 점근적 분석법 등을 배운다. 그 후 분할정복 divide and conquer, 동적 계획법 dynamic programming, 그리디 방법 greedy approach, 퇴각검색 backtracking, 분지한정 branch and bound 등의 알고리즘 설계 기법을 공부한다. 강의 후반에는 효율적인 알고리즘이 존재하지 않는 문제가 있다는 사실을 배우고 이를 다뤄본다. chap1. algorithm efficiency algorithm = step by step procedure for solving problem 알고리즘은 input을 받아 output을 내보낸다. - 문제에 따라 형태는 다르다. 왜 알고리즘을 공부하냐? pra..
델타 탐색이란 현재 위치를 기준으로 우-하-좌-상 으로 방향 전환이 고정되어 있다는 점을 활용하여 방향 전환 횟수 및 각 방향에서 움직이는 횟수에 대한 규칙을 사용하는 풀이이다. 예시 문제 swexpertacademy : 1954_달팽이 숫자 문제 문제풀이 아이디어 N자리 달팽이 숫자에서 방향 전환은 (2N-1)번 일어난다. 각 방향에서 움직임 횟수는 N ~ N-1 ~ N-1 ~ N-2 ~ N-2 ~ … ~ 2 ~ 2 ~ 1 ~ 1 순으로 발생한다는 것을 알 수 있습니다. dr = (0, 1, 0, -1) dc = (1, 0, -1, 0) for tc in range(1, int(input()) + 1): N = int(input()) snail = [[0] * N for _ in range(N)] r,..
BFS 란? BFS와 DFS의 차이는 어떤 자료구조를 사용하느냐로 너비 우선 탐색인지, 깊이 우선 탐색인지 갈리게 된다. BFS는 Queue 자료구조를 사용하여 들어온 순서대로 나가는 FIFO 원칙에 따라 너비 우선 탐색이 수행된다. 코드 정리 V, E = map(int, input().split()) # Vertex, Edge 갯수 adj_matrix = [[0] * (V + 1) for _ in range(V + 1)] # 인접행렬 기본틀 for _ in range(E): # 간선 갯수만큼 돌면서 연결 정보를 받음 start, end = map(int, input().split()) # 시작점과 끝점 adj_matrix[start][end] = 1 adj_matrix[end][start] = 1 # ..
[level 2] 전력망을 둘로 나누기 - 86971 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.4 MB, 시간: 54.22 ms 구분 코딩테스트 연습 > 완전탐색 채점결과 Empty 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를..
[level 2] 피로도 - 87946 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.2 MB, 시간: 0.09 ms 구분 코딩테스트 연습 > 완전탐색 채점결과 Empty 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나..
분류 Graph와 Tree의 구분은 Cycle이 생기냐 마냐의 차이이다. Tree는 Graph에 속한다. DFS는 크게 정보정리와 로직으로 구분된다. 정보정리 1. 인접행렬을 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리) 2. 인접 리스트를 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리) 로직 1. 스택을 활용한 풀이 2. 재귀함수를 활용한 풀이 따라서 4가지 경우의 수로 DFS를 풀 수 있다. 어떤 방식이 우월하다 하는 것은 없고, 많이 사용되는 방식은 인접행렬-스택 or 인접리스트-스택 방식이다.(이게 재귀보다 빠르기 때문) 다만 더 어려운 문제풀이의 경우 재귀방식이 사용된다.(ex) Segment Tree) 양방향 입력 예시 7 8 # Vertex = 7개, Edg..
코딩하며 알게되는 내용을 계속 업데이트할 예정입니다. 파이썬 내장함수 input()을 sys.stdin.readline()으로 변경하여 시간초과 해결. 입력부분에서 문자만 들어오는 경우와 문자,숫자 모두 들어오는 경우가 있었는데 (ex all , add 3 의 차이) text,num = sys.stdin.readline().split()# 이 아닌 text = sys.stdin.readline().split() #로 저장하여 text[0]과 text[1]에 저장되는 데이터를 불러 사용할 수 있음. strip() 함수로 \n이나 공백제거가 가능하더라. dictionary 자료형은 dict["key"] = values 형태로 저장가능함. DP문제에 대한 풀이가 익숙하지 않음.DP의 특성상 발생하는 idnex..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/81301 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 입력으로 아래와 같이 문자와 숫자가 섞인 형태로 입력이 들어옵니다. 우리는 입력으로 들어온 문자열을 아래 result와 같은 정수형으로 변환하여 반환해주어야 합니다. 구현과정 문자 : 숫자를 dict형태로 미리 저장해 두고(하드코딩) 문자열을 for문으로 하나씩 읽어 들여 숫자라면 바로 answer에 더해준다. 숫자가 아니라면 temp 문자열 변수에 값을 추가해 주고 tenp가 nums..
