본문 바로가기

코딩 테스트31

[프로그래머스] 택배 배달과 수거하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제가 그리디라고는 집작은 했지만 이해가 잘 되지 않았다. 이 문제의 키워드는 멀리 있는 집부터 무조건 해치우면 된다. 솔직히 한번에 이 아이디어가 떠오르지는 않지만 지래 겁먹고 예제 2를 확인안해서 둘다 멀리있는것 부터 하는구나...라는공통점을 못본 것은 내 실수라고 생각한다. 풀이는 아래와 같다. def solution(cap, n, deliveries, pickups): deliveries = deliveries[::-1] # 배달 뒤집기 pickups = pickups[::-1] # 수거 뒤집기 a.. 2023. 2. 1.
(프로그래머스) 시소 짝꿍 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 내가 한 말못된 풀이 나는 combination을 이용하엿으나 시간 초과가 난다.... 이유는100.000이란 범위가 주어졌기 때문이다. from itertools import combinations def solution(weights): combi = list(combinations(weights,2)) result = 0 for com in combi: if com[0] == com[1]: result += 1 a = min(com[0],com[1]) b = max(com[0],com[1]) if .. 2023. 2. 1.
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.
코딩테스트 파이썬 문법 (기초편) 자료형 #소수부가 0일 때 0을 생략 a = 5. # 5.0 # 10억의 지수 표현 방식 (최단 경로문제에서 자주 사용) a = 2e+9+1 # 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(rount(a,4)) 수 자료형의 연산 a = 7 b = 3 # 나누기 a / b # 나머지 a % b # 몫 a // b # 거듭 연산자 a ** b # a의 b승 자료형 변환 # 문자열을 한 글자씩 분리하여 리스트에 저장 str = 'Hello world!' list = list(str) ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!'] # Java에서 다음과 같.. 2023. 1. 12.

티스토리툴바