개발 이야기/Problem Solving
[묘공단] 코딩테스트 스터디 13주차
[묘공단] 코딩테스트 스터디 13주차
2024.03.02이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 16장 문제풀이입니다 16. 그리디 개념 그리디 -> 문제 해결 과정에서 순간마다 최선의 선택을 하며 선택을 번복하지 않는 알고리즘 다시 말해서 지역 최적해를 추구한다라고 말할 수 있다 그리디 알고리즘이 최적해를 보장하려면 최적 부분 구조 (Optimal substructure): 부분해를 푸는 과정이 최적해를 구하는 과정과 일치 그리디 선택 속성 (Greddy selection property): 선택 과정이 다른 과정에 영향을 주지 않음 이런 특징때문에 항상 최적해를 구할 수 있다는 보장은 못하지만, 빠르게 근사해를 제공하는 효과는 누릴 수가 있다 앞에서 공부했던 Union-Find를 활용하여 최소 신장 트리를 구하는 알고리즘도 그리디 알고리즘의..
[묘공단] 코딩테스트 스터디 12주차
[묘공단] 코딩테스트 스터디 12주차
2024.02.24이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 15장 문제풀이입니다 15. 동적 계획법 15-1. 동적 계획법 개념 동적 계획법은 전체 문제를 한 번에 해결하는 것이 아니라, 작은 부분 문제를 해결하고, 이것을 활용하여 전체 문제를 해결하는 방법 이 때 동적계획법이 효율적이려면 다음과 같은 조건들이 필요하다 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함 (중복 부분 문제) 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 함 (최적 부분 구조) 점화식 세우기와 동적 계획법 동적 계획법으로 문제를 해결하는 절차는 다음과 같다 문제를 해결하는 해가 이미 있다고 가정 종료 조건을 설정 과정 1, 2를 활용해 점화식을 만든다 Fact(N): # 문제를 해결..
[묘공단] 코딩테스트 스터디 11주차
[묘공단] 코딩테스트 스터디 11주차
2024.02.07이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 14장 문제풀이입니다 14. 시뮬레이션 시뮬레이션 문제 풀이 노하우 시뮬레이션 문제를 푸는 방법 성능에 중점을 둔 앞 장과 다르게, 시뮬레이션은 구현에 중점을 맞추는 유형이다 다른 알고리즘도 그렇지만 시뮬레이션 문제는 특히 아래 두 가지를 염두에 두고 문제 풀이에 접근 하나의 문제를 최대한 여러 개로 분리 예외 처리가 필요한 부분은 독립 함수로 구현 행렬 연산 지문에 꼭 행렬 내용이 없더라도, 행렬 연산을 활용해서 풀이할 수 있을 수 있으므로 몇 가지 연산들을 기억해두자 행렬 덧셈과 뺄셈, 그리고 곱셈 전치 행렬 좌표 연산 이전 장에서 했던 arr[row][col] 또는 arr[y][x] 형태로 주로 표현 이동 역시 dy, dx 같은 오프셋을 활용하..
[묘공단] 코딩테스트 스터디 10주차
[묘공단] 코딩테스트 스터디 10주차
2024.02.03이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 12장 문제풀이입니다 정렬 개념 정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것 오름차순 내림차순 임의의 조건 정렬이 된 데이터에서는 원하는 데이터를 쉽게 찾을 수 있기 때문에 효율적 병합 정렬 전형적인 분할-정복 방식의 정렬 알고리즘 매 과정에서 반씩 분할 후, 분할된 데이터의 크기가 1일 때부터 정렬된 순서로 합병하는 방식 힙 정렬 힙의 특징을 이용해서 최솟값 또는 최댓값을 반복적으로 pop하면 결국 정렬된 데이터를 얻을 수 있게됨 파이썬에서는 heapq의 여러가지 메서드를 활용해서 우선순위 큐 연산들을 지원할 수 있다 위상 정렬 방향이 있고 cycle이 없는 graph (DAG)에서 태스크의 순서를 정렬하는 알고리즘 각 노드로 들어오는 i..
[묘공단] 코딩테스트 스터디 9주차
[묘공단] 코딩테스트 스터디 9주차
2024.01.27이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 12장 문제풀이입니다 백트래킹 백트래킹과 백트래킹 알고리즘 개념 깊이 우선 탐색, 너비 우선 탐색은 데이터를 전부 확인하는 방법이며 이를 완전 탐색이라고 함 완전 탐색은 모든 경우의 수를 탐색하는 방법이므로 비효율적 따라서 탐색을 하다가 가능성이 없다면 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘을 백트래킹이라고 한다 백트래킹 알고리즘의 핵심은 '해가 될 가능성을 판단하는 것'이며 그것을 유망함수라는 것을 정의하여 판단함 유효한 해의 집합을 정의 위 단계에서 정의한 집합을 그래프로 표현 유망 함수를 정의 백트래킹 알고리즘을 활용해서 해를 찾음 예를 들어 1, 2, 3, 4 중 2개의 숫자를 뽑아서 6보다 큰 조합을 찾을 때 백트래킹을 활용한다면..
[묘공단] 코딩테스트 스터디 8주차
[묘공단] 코딩테스트 스터디 8주차
2024.01.19이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 11장 문제풀이입니다 실전 문제 게임 맵 최단거리 간선 가중치가 없는 케이스에서의 최단거리를 구해야하므로 아이디어로 BFS를 떠올리면 된다. 몇 가지 예외 처리 (좌표, 벽)과 방문 불가능한 케이스만 주의하면 전형적인 BFS 코드로 풀이 가능 from collections import deque from typing import List def solution(maps: List[List[int]]) -> int: def is_valid_coordinate(x: int, y: int) -> bool: return 0 int: graph = defaultdict(list) for u, v, w in road: graph[u].append((v, w))..
[묘공단] 코딩테스트 스터디 7주차
[묘공단] 코딩테스트 스터디 7주차
2024.01.12이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 11장 써머리입니다 그래프의 개념 노드와 간선을 이용한 비선형 자료 구조. 간선은 1) 무방향/유방향 2) 가중치 O/X 조합이 가능함 방향이 있는 그래프를 Directed Graph, 없는 그래프를 Undirected Graph 라고 한다 특정 노드에서 시작해 다시 돌아오는 경로가 있을 경우 Cycle (순혼)이 존재한다고 하며 Cycle Graph라고 함 그래프 구현 인접 행렬 인접 리스트 인접 행렬 구현은 배열을 주로 활용하며, 배열의 인덱스는 노드 그리고 값은 노드의 가중치로 볼 수 있다 반대로 인접 리스트 구현은 배열과 노드 객체를 이용해서 주로 표현함. 그러면 배열의 인덱스는 시작 노드를 의미하며 값에는 다음 노드를 연결할 수 있음 인접 ..
[묘공단] 코딩테스트 스터디 6주차
[묘공단] 코딩테스트 스터디 6주차
2023.12.30이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 10장 써머리입니다 집합과 상호배타적 집합의 개념 집합은 순서와 중복이 없는 원소들을 갖는 자료구조, Python에서는 간단하게 set()을 활용할 수 있다. 상호배타적 집합은 서로 다른 두 집합 사이에 공통 원소가 없는 경우를 말함 코딩 테스트에서 상호배타적 집합을 활용하는 가장 큰 이유는 그래프 알고리즘 중 사이클을 판별하기 위해서 활용. 그 외에는 아래와 같은 응용 사례들이 존재한다 이미지 분할 도로 네트워크 구성 최소 신장 트리 알고리즘 구현 게임 개발 클러스터링 작업 집합의 연산 집합의 표현은 앞서 배운 트리의 배열 표현과 거의 유사하게 구현할 수 있고, 대표적인 연산은 합치기와 탐색 (Union-Find)가 있음. 배열의 인덱스는 자기 자..
[묘공단] 코딩테스트 스터디 5주차
[묘공단] 코딩테스트 스터디 5주차
2023.12.22이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 9장 써머리입니다. 트리 트리 개념 트리는 앞에서 다룬 선형 자료구조와는 다르게 계층 구조를 표현하는 용도로 많이 사용하는 자료 구조 인공지능의 의사결정트리 Trie를 활용한 자동 완성이나 검색 기능 데이터베이스에서 데이터 삽입, 삭제, 검색을 빠르게 하기 위한 용도 (B-tree 계열) 여러 가지 새로운 용어들이 많이 등장하는 데 아래와 같다 루트 노드 노드/간선 형제 노드: 동일한 부모 노드를 갖는 노드 부모/자식 노드 리프 노드: 자식이 없는 노드 높이: 루트 노드를 레벨 0으로 보고 자식 노드로 내려가면서 1씩 증가 차수: 아래로 향하는 간선의 개수 이진 트리 표현하기 이진 트리를 표현하는 방식은 크게 두 가지가 있다 배열로 표현 포인터로 표..
[묘공단] 코딩테스트 스터디 4주차
[묘공단] 코딩테스트 스터디 4주차
2023.12.15이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 8장 써머리입니다. 해시의 개념과 정의 키를 통해서 빠르게 데이터 탐색을 지원하는 자료 구조를 해시라고 한다 이 때 키를 만들 때 사용하는 함수를 해시 함수라고 하며 다음과 같은 특징이 있다 해시는 단방향으로 동작 상수 시간에 바로 찾을 수 있음 값을 인덱스로 활용하려면 적절한 변환 과정 필요 위와 같은 특징 중 단방향 동작을 활용한 비밀번호 관리, 상수 시간에 바로 찾을 수 있는 특징을 활용한 데이터베이스 인덱싱 그리고 블록체인에서 활용된다 해시 함수 파이썬에서는 딕셔너리 또는 셋 자료형을 통해 상수 시간에 키 검색이 가능하므로 직접 구현할 일은 많지 않다 그러나 직접 구현한다면 여러 가지 조건들을 고려해야하는 데 해시 함수의 변환 값을 키 (인덱..
[묘공단] 코딩테스트 스터디 3주차
[묘공단] 코딩테스트 스터디 3주차
2023.12.08이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 6, 7장 써머리입니다. 스택의 개념과 정의 먼저 들어간 것이 마지막에 나오는 LIFO (Last In, First Out 또는 후입선출) 특징을 가지는 자료형 주요 연산은 push와 pop이 있고, 그 외에 isFull, isEmpty, 그리고 최근에 삽입한 데이터의 위치인 top도 있음 문제 풀이 때는 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리면 좋다 대부분 스택을 몰라서 못 푸는 것이 아니라 스택을 활용해야 한다는 생각을 못 떠올려서 풀지 못하는 경우가 많으므로 스택 관련 문제를 많이 풀어보고 스택을 사용해야 한다는 감을 익히는 것이 중요! 문제 풀이 괄호 짝 맞추기 전형적인 스택을 활용하는 문제 유형. 다만 조건에서 ..
[묘공단] 코딩테스트 스터디 2주차
[묘공단] 코딩테스트 스터디 2주차
2023.11.30이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 0장 ~ 4장 써머리입니다. 배열 개념 인덱스와 값을 일대일 대응해 관리하는 자료구조 인덱스만 알면 빠르게 탐색 가능 (Random access) 배열 선언 # 1차원 배열 vector = [0] * 6 # 2차원 배열 (e.g., 3 by 4 matrix) matrix = [[0] * 3 for _ in range(4)] 배열 차원 중첩 리스트 형태로 다차원 배열을 표현 가능 그러나 실제 메모리는 1차원 구조로 저장된다 또한 2차원 배열을 1차원 배열로 표현해서 풀이하는 문제도 꽤 자주 출제됨 matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] matrix2 = [1, 2, 3, 4, 5, 6, 7, 8, 9] # 2행 ..