본문 바로가기

코딩 테스트/코딩테스트 - 학습17

위상정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미 예시) 선수과목을 고려한 학습 순서 설정 그래프 + 순서(단 방향이여야 한다.) 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (O) 자료구조 → 고급 알고리즘 → 알고리즘 (X) 아이디어 : "제일 먼저 올 수 있는 정점은?" = 0인걸 먼저 찾기 위상정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다 정점들의 Indegree, Indeg[1...N] 계산하기 들어오는 간선이 0개인(Indeg[i] == 0) 정점들을 찾아서 자료구조 D에 넣기 D가 빌때까지(Queue) D에서 원소 x를 꺼내서 "정렬"시키기 Graph 에서 정점 X "제거".. 2023. 3. 2.
까먹는 코테 문법2 1. 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(rount(a,4)) 2. 거듭 연산자 a ** b # a의 b승 3. 자료형 변환 char ch = 'a'+1; # 자바 ch = chr(ord('a')+1) # 파이썬 4. 입력 # N개의 정수를 한 줄로 입력 받아 List에 저장할 경우 data = list(map(int, input().split())) # N개의 정수를 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 N = int(input()) data = [int(input()) for _ in range(N)] # N개의 문자열을 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 리스트 변환 s.. 2023. 2. 16.
이분 탐색 & 매개변수 탐색 & 투 포인터 탐색 이분 탐색 vs 매개변수 탐색 vs 투 포인터 이분 탐색 : 정렬된 배열에서 중앙값(mid)이 가리키는 값이 내가 찾는 값인지가 중요 (대표 문제) 매개변수 탐색 : 배열에서 목표(target)가 원하는 조건에 만족할 때까지 최대한 찾는 것이 중요 (대표 문제) 투 포인터 : 배열에서 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 (대표 문제) 이분 탐색 매개변수 탐색 투 포인터 시간 복잡도 O(logN) O(logN) O(N) 가정 데이터 정렬 x x 방식 mid를 활용 하여 매 연산마다 탐색의 범위를 절반으로 좁혀 나감 target과 일치하는 값을 찾아도 더욱 최적의 해가 있을때까지 찾아나감 양끝 혹은 모두 왼쪽에서 한칸씩 이동하며 알맞은 값 을 찾아나감 이분 탐색 이분 탐색이란 데이.. 2023. 2. 2.
Stack/Queue 뒤에 있는 큰 수 찾기 이 문제의 단서는 1, 문제가 너무 쉽다, 2. 10,000,0000이란 최대 이기 때문에 뭔가 이상하다는 느낌은 있었다. 그런데 이게 stack 문제일줄은.....솔직히 접근 방법을 아직도 모르겠다.... def solution(numbers): stack = [] result = [-1] * len(numbers) for i in range(len(numbers)): while stack: if numbers[stack[-1]] >= numbers[i]: break result[stack.pop()] = numbers[i] stack.append(i) print(stack) return result 2023. 2. 1.
[DP] 누적합 알고리즘 누적합 알고리즘은 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있는 알고리즘이다. N개의 원소로 이루어진 배열이 주어졌을 때, 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분 합을 이용하면 모든 부분합을 O(1)에 바로 구할 수 있다. KeyPoint sum은 배열의 +1이다. 1차원 배열 - 직관적으로 매우 쉽게 이해가 가능하다. arr 을 순차 탐색하면서 sum배열을 만들어주면 된다. sum[i]에는 arr[0] + arr[i] + ...+ㅁㄱㄱ[i-1]의 정보가 담겨 있다. 활용법 arr의 i항부터 j항까지의 합을 s(i,j)라고 하자. 이때, s(i,j) = sum[j+1] - sum[i]이다. 2차원 배열 2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum .. 2023. 1. 31.
DP 틀린 문제 리뷰 1. 계단오르기 계단 오르기 - 2번 연속해서 계단을 오른 경우와 1번 연속해서 계단을 오른 경우의 최대값을 dp배열을 통해 구한다. - 전을 밟지 않은것 최대(dp[i-2]) + 현재계단(arr[i]) , 전전을 밟지 않은 것 최대(dp[i-3]) + 전 계단(arr[i-1]) + 현재계단(arr[i]) dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]) 2. 가장 ~ 하는 부분 수열 1. 가장 긴 감소하는 수열 2.가장 큰 증가 부분 수열 이것이 왜 dp인가? 나는 이 쉽게 생기면서 어려웠던 이유는 그냥 앞에서 뒤에꺼를 보고 그냥 오면 되는거 아닌가? 이런 생각을 했었다... 그러다 문득 생각난것은 "가장 큰 증가 부분 수열"을 보.. 2023. 1. 30.
자주 잊는 코딩테스트 문법 0. 기본 # 1. 나누기를 조심하자!!!!나누기하면 float으로 나온다 print(4/2) # 2.0 print(4/2) # 2.5 # 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(round(a,4)) # Java에서 다음과 같은 코드는 ch 에 'b'를 저장한다. # 하지만 파이썬은 문자를 아스키코드를 나타내는 int형으로 변환하고 연산한 뒤 다시 char형으로 형변환 해주어야 한다. char ch = 'a'+1; # 자바 ch = chr(ord('a')+1) # 파이썬 # 입력 import sys input = sys.stdin.readline # N개의 정수를 한 줄로 입력 받았을 경우 N, M, K .. 2023. 1. 29.
Union Find 서로소 집합 알고리즘 1. 서로소 집합이란 예를들어 집합 {1,2} 와 {2, 3}은 서로소 가 아니지만 {1, 2}, {3, 4}는 서로소 집합이다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집한 인지 알려주는 연산이다. 예를 들어 {1, 2, 3 ,4, 5, 6} 에서 서로소 부분 집합이 다음과 같이 주어진다고 가정하자 {1, 4} , {2, 3}, {2, 4}, {5, 6} 이와 같이 주어진 서로소 부분집합들은 각각 동일한 서로소 집합에 포함되어 있는 원소들이.. 2023. 1. 28.
(그리디) 크루스칼 알고리즘 1. 최소 신장을 찾는 크루스칼 알고리즘 신장트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 즉, 모든 노드들 간에 서로 연결은 되어 있되 사이클이 존재하지 않는 "부분"그래프를 의미한다. 예를 들어 다음과 같은 그래프G가 있을 때, 이때 그래프에서 가능한 신장 트리는 다음과 같다. 즉, A, B, C 노드들 간에 서로 연결은 되어 있되, 자기 자신으로 돌아오는 산선이 있는 사이클이 존재해서는 안된다. 이럴때 우리는 신장 트리라 한다. 신장 트리들은 원본 그래프 G의 '부분' 그래프임을 잊지 말자. 2. 왜 최소 신장을 찾을때 크루스칼 알고리즘을 사용할까? 아래와 같이 있다고 가정해 보자 위 그림을 보면 원본 그래프에서 나올 수 있는 신장 트리는 2가지 이다. 파란색, 빨간색 점으로 이루어진 그.. 2023. 1. 28.
문자열 문자열에 숫자로만 이루어졌는지 확인 +,- 부호나 소수점은 False로만 나온다 (구분 못함) print('1234'.isdigit())# True print('abc1234'.isdigit())# False 문자열 대소문자 변경 - 문자열.upper() - 해당 문자열을 대문자로 변환 - 문자열.lower() - 해당 문자열을 소문자로 변환 - 문자열.isupper() - 해당 문자열이 전부 대문자인지 판단 - 문자열.islower() - 해당 문자열이 전부 소문자인지 판단 str1 = 'ponyozzang' print(str1.isupper()) #PONYOZZANG str2 = 'PonyoZzang' print(str2.isupper()) #False str3 = 'PONYOZZANG' print(.. 2023. 1. 25.
다익스트라 다익스트라 알고리즘은 source node로 부터 모든 node까지의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘을 알기 위해서는 먼저 heapq부터 알고 해야 한다. 그전에 heapq의 특징을 알고가면 좋다. [heapq] 완전 이진 트리 형태 부모 노드 키값이 자식 노드 키값보다 항상 작다(최소힙) 키값의 대소관계는 부모/자식 관계에서만 성립하고, 자식끼리의 대소관계는 없다 다익스트라 알고리즘 1. node가 숫자일때 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net.. 2023. 1. 20.
정렬 파이썬으로 문제를 풀다보면, 여러 조건으로 소팅을 해야하는 경우가 있다. 일반적인 소팅은 다음과 같이 sorted() 혹은 .sort() 를 사용한다. a = [4,1,2,5,7,3,6] b = sorted(a) # b = [1,2,3,4,5,6,7] sorted() 를 찬찬히 살펴보면 다음과 같다. a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)] # 인자없이 그냥 sorted()만 쓰면, 리스트 아이템의 각 요소 순서대로 정렬을 한다. b = sorted(a) # b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)] # key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다. c = sorted(a, key = lambd.. 2023. 1. 20.
완전 탐색 에라토스테네스의 체 n=1000 primes=list(range(n+1)) primes[1] = 0 for i in range(2,int((n+1)**0.5)): if primes[i] != 0: for j in range(2*i, n+1, i): primes[i] = 0 + 추가적으로 그냥 반목문에 의해 소수 구하기 def sol1(n): for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True number = 100 print(sol1(number)) 백트랙킹 아래의 문제들은 파이썬 라이브러리를 사용하면 간단히 풀수 있지만 백트랙킹을 이해하는데 좋은 문제들이다. 결과값의 순서를 보고 코드의 차이점을 머리속으로 생각을 해보자! .. 2023. 1. 18.
dfs bfs 문제로 보는 정리 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. BFS & DFS 설계 (인접 리스트) from collections import deque n, m, v = map(int, input().split(" ")) visit = [False] * (n + 1) arr = [[] for i in range(n + 1)] for i in range(m): a, b = map(int, input().split(" ")) arr[a].append(b) arr[.. 2023. 1. 14.
코딩 테스트 파이썬 문법 (중간편) 코딩테스트를 준비하며 반드시 알아야 하는 라이브러리 6가지 내장 함수 print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있는 내장 라이브러리 itertools 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리, 순열과 조합 라이브러리를 제공 heapq 힙(Heap) 기능을 제공하는 라이브러리. 우선순위 큐 기능을 구현하기 위해 사용한다. bisect 이진탐색/이분탐색(Binary Search) 기능을 제공하는 라이브러리 Collections 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리 math 필수적인 수학적 기능을 제공하는 라이브러리 팩토리얼, 제곱급, 최대공약수(GCD), 삼각함수,.. 2023. 1. 12.

티스토리툴바