'이것이 코딩테스트다' 정리하기 👑(1)

황규빈·2022년 7월 9일
0

💎 개요


요새 파이썬을 이용해서 코딩테스트 준비를 다시 시작하려고 하는데 파이썬을 이용하기와 더불어서 알고리즘의 종류가 어떤 것들이 있고, 어떤 분류를 통해 문제에 접근해야할지 처음부터 정리를 해보고자 한다. 이에 따라 '이것이 코딩테스트다 with 파이썬'책과 함께 기록해둔 내용을 velog에 정리해보고자 한다!!

빠르게 내용만 정리해서 머릿속에 담아두고 파이썬을 이용한 문제를 풀어보면서 velog에 문제와 함께 풀이를 업로드 해볼 예정이다!!

참고 강의 링크! 👉 https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

💎 알고리즘


🍫 그리디 알고리즘

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만을 고르는 방법
→ 문제를 풀기위한 최소한의 아이디어를 떠올리도록 하기

ex) 루트 노드 부터 시작해서 거쳐가는 노드 값의 합을 최대로 만들기

일반적 상황에서 최적의 해를 보장할 수 없을 때가 많음

그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있도록 풀이!!

  1. 거스름 돈 문제

    → 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 최적의 해를 보장 가능

    시간 복잡도는 O(K) 동전의 총 종류에만 영향

  2. 1이 될 때까지

    주어진 N에 대하여 최대한 많이 나누기를 수행 (K에 대해서 나누고 안되면 1빼기)

    K가 2이상이면 1을 빼는 것 보다 항상 빠르게 N을 줄일 수 있기 때문에

    target = (n // k) * k
  3. 곱하기 혹은 더하기

    +보다 X 가 더 값을 크게 대개 만들기 때문에 x를 이용하였을 때 더 큰 부분을 채택

    int(input)
    
    # 두 수 중 하나라도 0 혹은 1이면 곱하기보다 더하기 수행하기
    
    if num <= or result <= 1 :
    	result += num
    else : 
    	result *= num
  4. 모험가 길드

    공포도를 하나씩 확인해서 오름차 순으로 정렬해보기

    현재 그룹에 포함된 모험가 수가 현재 확인하는 공포도 보다 크거나 같으면 그룹 결성

    n = int(input())
    data = list(map(int, input().split()))
    data.sort()
    
    result = 0
    count = 0
    
    for i in data :
    	count +=1 
    	if count >= i :
    		result += 1
    		count = 0
    
    print(result)

🍫 구현

구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

<예시>

  • 알고리즘은 간단한데 코드가 엄청 긴 문제
  • 실수 연산을 다루고 특정 소수점 자리까지 출력해야 할 때
  • 문자열을 특정 기준에 따라 끊어 처리할 때
  • 적절한 라이브러리를 찾아 사용해야할 때

일반적으로 알고리즘 문제는 2차원 공간, 행렬의 의미로 사용됨

for i in range(5):
	for j in range(5):

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터 자주 활용

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

x, y = 2, 2 # 현재 위치

for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
  1. 상하좌우 문제

    요구사항대로 충실히 구현

    시뮬레이션 유형

    *시뮬레이션 구현 완전 탐색은 비슷한 유형으로 생각하기

    방향 벡터를 활용하여 이동 계획을 하나씩 확인해보기

  2. 시각

    모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수 구하기 ex ) 00시 00분 03초, 00시 13분 30초

    하나씩 일일히 다 세서 푸는 문제 → 완전 탐색(Brute Force) 떠올리기

    24 60 60 = 86,400

    파이썬을 이용하면 1초에 약 20,000,000개의 연산을 수행할 수 있다고 염두하고 계산해보기!!

    h = int(input())
    
    count = 0
    
    for i in range(h+1):
    	for j in range(60):
    		for k in range(60):
    			if '3' in str(i) + str(j) + str(k):
    				count += 1
  3. 왕실의 나이트

    요구사항 충실히 구현하기

    나이트의 8가지 경로를 하나씩 확인해보면서 count해보기

    steps = [(-2, -1), (-1, -2), (1,-2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
    
    ord()를 사용하여 아스키 코드로 바꿔서 열을 숫자로 계산하기 
  4. 문자열 재정렬

    알파벳을 오름차순으로 정렬하여 이어서 출력하고 모든 숫자를 더한 값을 이어서 출력

    알파벳 여부와 숫자를 따로 확인하여 처리

    if x.isalpha() :
    	result.append(x)
    else :
    	value += int(x)

🍫 자료구조 스택/큐

스택 : 먼저 들어온 데이터가 나중에 나가는 선입 후출 자료구조

입구와 출구가 동일한 형태

  • 삽입 - append(요소)
  • 삭제 - pop()

: 먼저 들어온 데이터가 먼저 나가는 선입 선출 자료구조

큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능

  • 삽입
  • 삭제
  • from collections import deque
from collections import deque

queue = deque()

queue.append(5)
queue.popleft()

🍫 재귀 함수

재귀 함수 : 자기 자신을 다시 호출하는 함수

파이썬을 재귀 함수를 실행하면 최대 재귀 깊이 제한이 있음 (설정이 필요할 수 있음)
→ 종료 조건을 제대로 명시해야할 필요가 있음

예시)

  1. 팩토리얼
def factorial_recursive(n)
	if n <=1 :
		return 1
	return n * factorial_recursive(n - 1)
  1. 유클리드 호제법 (최대공약수 계산)
    두 자연수 A, B(A > B)에 대하여 A를 B로 나눈 나머지 R
    B와 R의 최대공약수는 A와 B의 최대공약수
def gcd(a, b)
	if a % b == 0 :
		return b
	else :
		return gcd(b, a % b)

재귀함수를 잘 활용하면 복잡한 알고리즘 간결하게 작성할 수 있다!
→ 재귀함수는 반복문을 이용하여 동일하게 구현 가능

스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

🍫 DFS/BFS

DFS: 깊이 우선 탐색
스택을 이용하여

  1. 탐색 시작 노드를 스택에 삽입, 방문 처리
  2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접한 노드가 없으면 스택 최상단 노드 꺼냄
  3. 2번 과정을 수행할 수 없을 때 까지 반복
def dfs(graph, v, visited) :
	visited[v] = True
	print(v, end= ' ')
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

BFS: 너비 우선 탐색 - 가까운 노드부터 우선적으로 탐색
를 이용하여

  1. 탐색 시작 노드를 큐에 삽입, 방문 처리
  2. 큐에서 노드 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 2번 과정을 수행할 수 없을 때까지 반복
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
	v = queue.popleft()
	print(v, end = ' ')
	for i in graph[b]:
		if not visited[i]:
			queue.append(i)
			visited[i] = True

💎 정리


따로 노션에 기재하면서 강의를 정리한 내용들을 velog에 옮겨 게시하였다. 이렇게 정리하였을때, 생각보다 내 velog로 다시 되돌아와서 내가 어떻게 해놨는지 보는 경우가 많았어서 앞으로 기본 개념이 뭐였는지, 또는 면접 대비를 위해 알고리즘 기본 내용이 무엇인지 떠올리기 위해 내가 정리한 부분을 다시 찾을 것이다!!

다음에는 (2)번째 내용의 '이것이 코딩테스트다'의 내용들을 옮겨 정리해볼 예정이다~~ 그 때까지 우선,,,opic 시험 마무리를 하고 다른 개발 공부와 함께 본격적으로 알고리즘 공부를 빡세게!! 해볼 예정이다.

너무 놀았던 것 같다 ㅠㅠ 좀더 열심히 해보자~~
화이팅!

profile
안녕하세욤

0개의 댓글