에이란의 블로그

그리디 그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않습니다. : 그리디 알고리즘은 지역 최적해를 추구한다. 그리디 알고리즘이 최적해를 보장하려면? 특정한 상황 1) 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치. 2) 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음. 최소 신장 트리 대표적인 트리 형태의 자료구조. 신장트리란? 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수 보다 적은 그래프. 최소 신장 트리란? MST. 신장 트리 중 간선의 가중치 합이 최소면 최소 신장 트리. 프림 알고리즘 vs 크루스칼 알고리즘 프림 크루스칼 알고리즘의 목적 최소 신장 트리 최소 신장 트리 시간 복잡도(정점..

동적 계획법 전체문제를 한번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법. 점화식 세우기와 동적계획법 문제를 해결하는 해가 이미 있다고 가정. 종료 조건 설정. 과정 1,2를 활용해 점화식 세우기 점화식 구현: 재귀 활용 def fact(N): if N == 1: return 1 else: return fact(N-1) * N 하지만, 스택 메모리에 함수 호출 정보가 많이 쌓이므로 메모리 한계로 런타임 오류가 발생할 수 있음. 따라서 재귀 호출을 해서 문제가 생겼거나, 생길 거 같을 때 취할 수 있는 방법은 다음과 같다. - 재귀 호출 자체를 쓰지 않는 법 : 반복문 - 재귀 호출의 횟수를 줄이는 법 : 메모이제이션 재귀 호출의 횟수를 줄여주는 메모이..

시뮬레이션 주어진 상황을 잘 이해하고 이를 코드로 구현하는 과정 하나의 문제를 최대한 여러개로 분리하기 예외 처리가 필요하다면 독립 함수로 구현 문제풀이 배열 회전하기 def rotation(arr): # 행과 열의 크기 구하기 rows = len(arr) cols = len(arr[0]) # 새로운 2차원 배열 초기화 rotated_arr = [[0] * rows for _ in range(cols)] # 시계 방향으로 90도 회전 for i in range(rows): for j in range(cols): rotated_arr[j][rows - 1 - i] = arr[i][j] return rotated_arr def solution(arr, n): # n번 회전 for _ in range(n): ..

스터디에 제공한 추가자료 동영상에 비슷한 문제들로 설명이 잘 나와있어 도움이 많이 되었다. 게임 맵 최단거리 상하좌우 탐색을 진행하며 새롭게 방문하는 노드의 값 변경 bfs를 수행하면 결과적으로 최단경로의 값들이 1씩 증가함. 상대팀 진영 도착못할시 -1 더보기 스터디 발표 후 피드백 : 시작지점도 방문처리를 해줘야함 (기존코드) from collections import deque def solution(maps): n = len(maps) # 맵의 행 크기 m = len(maps[0]) # 맵의 열 크기 #상하좌우 4가지 방향 정의 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS def bfs(): queue = deque() queue.append((0, 0)) # 시..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 11장 써머리입니다. 그래프 개념 : 노드와 간선을 이용한 비선형 데이터 구조. 노드 : 데이터 , 간선: 관계흐름, 가중치: 흐름의 정도 인접행렬 그래프 : 배열을 활용하여 구현 장점 - 시간복잡도 O(1) - 구현난이도가 낮다. 단점 - 희소 그래프를 표현할때 * 희소 그래프란? 노드 수에 비해 간선 수가 매우 적은 그래프. : 노드가 n개 있을때 확보한 n*n 크기의 인접 행렬 공간 중 대부분의 공간은 식제로 사용하지 않게 되므로 비효율적 #희소그래프 예시 A - B | C #인접행렬로 표현 A B C A [0, 1, 1] B [1, 0, 0] C [1, 0, 0] ## 0이 많이 채워져있어 메모리 낭비가 큼. - 노드들의 값의 차이가 매우 큰..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 10장 써머리입니다. 집합 개념 : 중복이 없는 원소들을 갖는 자료구조. 종류 : 유한집합, 무한집합, 공집합, 상호배타적 집합 **상호배타적 집합이란? 교집합이 없는 집합 분야 - 이미지 분할 : 사람, 배경 분할할때 사용. - 도로 네트워크 구성 : 교차로의 혼잡 줄이기. - 최소 신장 트리 알고리즘 구현 : 간선 추가때마다 사이클 형성 여부 체크 가능. - 게임 개발 : 캐릭터의 동작을 자연스럽게 구현. - 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성 가능. (의존관계 없으면 동시에 복수작업 가능) 집합의 연산 배열을 활용한 트리로 집합 표현. **대표 원소란? 집합을 대표하는 역할. (여기서는 루트노드) 배열의 인덱스는 자신, 배열..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 9장 써머리입니다. 트리 데이터를 탐색하기에 유용한 구조로 계층 구조를 표현하는 용도로 사용. - 인공지능 - 자동 완성 기능 - 데이터베이스 구성요소 - 노드 루트 노드 : 가장 위에 있는 노드 리프 노드 : 자식이 없는 노드 부모 노드 : 상대적으로 위에 있는 노드 자식 노드 : 아리에 있는 노드 - 에지(간선) 노드와 노드사이를 이어주는 선 차수(degree) : 아래로 향하는 간선의 개수 표현방법 - 배열로 구현 장점 : 구현 난이도가 쉬워 구현 시간이 단축된다. 단점 : 메모리 공간 낭비. - 포인터로 구현 장점 : 메모리 공간을 낭비하지 않음. 단점 : 구현 난이도 어려움. 이진트리 순회 현재 노드를 부모 노드로 생각했을 때, - 전위 순..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 8장 써머리입니다. 해시 해시함수를 사용해서 반환한 값을 인덱스로 삼아 키와 값을 저장해 빠른 데이터 탐색을 제공하는 자료구조. ** 고려사항: 충돌을 유의 해시 특징 - 단반향 작동. - 찾고자하는 값 바로 찾기 가능 O(1). - 값을 인덱스로 활용할 시 적절한 변환과정 필요. 자주사용하는 함수 - 나눗법셈 h(x) = x mod m 키를 소수로 나눈 나머지를 활용. K 값으로는 충돌이 적게 발생하는 소수를 사용하며 상황에 따라 아주 많은 데이터를 저장하기 위해 큰소수를 사용해야 한다. ->장점 : 떠올리기 쉬운 가장 단순한 방법, 단점 : 큰소수를 구하는 효율적인 방법 부재. - 곱셈법 h(x) = ((X*A) mod 1)*m #X: 최대 버킷..

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 5장 써머리입니다. 배열 배열과 차원 배열은 차원과 무관하게 메모리에 연속할당된다. 배열의 효율성 데이터에 접근하기 위한 시간 복잡도는 O(1). 맨뒤에 삽입 O(1) 맨앞에 삽입 O(N) 중간에 삽입 O(N) - 배열 선택시 고려사항 할당가능한 메모리 크기 확인 중간에 데이터 삽입이 많은지 확인 리스트 기법 append() : 맨끝에 데이터 추가 ( +연산자로도 데이터 추가 가능) insert() : 특정위치의 데이터 삽입 pop() : 특정위치의 데이터 삭제 remove() : 특정 데이터 자체를 삭제하는 함수 len() : 데이터 개수 index() : 인덱스를 반환, 없으면 -1 반환 sort() : 정렬 count() : 특정데이터 개수 1..

코딩테스트엔 꾸준히 많이 풀어보는게 길이라고 한다. 코딩테스트를 혼자 준비하기엔 나태해질 것 같아 좋은 기회가 생겨 스터디를 시작하게 되었다. 나의 장기적인 목표는 직장을 다니면서도 안주하지않고 공부하는 습관을 들이는 것이다. 그러기 위해 앞으로 화이팅하며 나아가고자 한다. 스터디 다짐 : 코딩스터디의 과제를 기한내에 빠짐없이 참여하며, 따로 추천해준 추가 문제 최소1문제 이상 풀어보기 이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 0장 ~ 4장 써머리입니다. 1. 효율적인 코딩테스트 준비 - 언어 선택 : 파이썬 - 테스트 준비 사이트 : 프로그래머스 (+ LeetCode) 코딩테스트를 볼때 가급적 파이썬으로 준비하라고 되어있다. 정답은 없다.난 처음 개발을 배웠을때부터 파이썬으로 했기때문에 ..