Development Artist

접근 - NxN 개의 시작점을 전부 방문하여 가장 높은 곳을 찾습니다. - 높은 곳은 여러개일 수 있으며 각 출발점에서 좌우상하로 가는 경우를 계산하고 기록합니다. > 위의 정보를 바탕으로 풀이방법을 유추해 봅니다. > DFS 입니다. ※ DFS인지 유추가 안된다. 시간이 없을 경우 DFS 문제 검색 후 10개만 한번 지문을 읽어보세요. 조건 - 조건이 있는지 확인합니다. > 높은 곳에서 낮은 곳으로 나아갑니다. > 공사 가능한 깊이 K에 대한 처리를 해줍니다. DFS 로직 재귀함수 : dfs def DFS(): for ~ : DFS() 상하좌우 : 방향좌표 변수들을 미리 지정한다. dx = [-1,0,1,0] dy = [0,1,0,-1] 방문배열 : 방문했는지 안했는지를 체크하는 배열 visited =..

도입 백준 단계별 풀기 DFS와 BFS 열한 번째, 마지막 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간..

도입 백준 단계별 풀기 그리디 알고리즘 첫 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검사 문제가 아니면 1번으로 돌아가서 반복 풀이 1...

도입 백준 단계별 풀기 그리디 알고리즘 세 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검사 문제가 아니면 1번으로 돌아가서 반복 풀이 1...

도입 백준 단계별 풀기에서 우선순위큐 네 번째, 마지막 문제이다. 풀이 0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최소힙이란, 루트노드에 가장 작은 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다. 1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 ..

도입 백준 단계별 풀기에서 우선순위큐 세 번째 문제이다. 풀이 0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최소힙이란, 루트노드에 가장 작은 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다. 1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 이유는 시..

도입 백준 단계별 풀기에서 우선순위큐 두 번째 문제이다. 풀이 0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최소힙이란, 루트노드에 가장 작은 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다. 1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 이유는 시..

도입 백준 단계별 풀기에서 우선순위큐 첫 번째 문제이다. 풀이 0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최대힙이란, 루트노드에 가장 큰 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 크다. 1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 이유는 시간..

도입 백준 단계별 풀기에서 이분탐색 일곱 번째, 마지막 문제이다. 풀이 0. 2가지 풀이를 할 예정, 이분탐색을 사용한 방법과, bisect 라이브러리를 사용한 방법. 1. nlist라는 빈 배열을 선언하고, 입력받은 수열의 값들을 차례대로 넣을지 말지 결정한다. nlist의 인덱스값을 mid로 설정한다. for문은 수열 A의 index값을 초기화하고 증가시킨다. 그래서 해당 index보다 입력받은 수열 A의 값과 비교한다. 수열 A의 값이 nlist의 mid보다 크다면, low 값을 1씩 증가시켜간다. 그리고 이 low를 가지고 nlist에 추가(append)를 할지, 덮어쓸지를 결정한다. 2. 이번에는 bisect이라는 라이브러리를 사용할 것이다. bisect 라이브러리의 기본 컨셉은 정렬된 리스트를..

도입 백준 단계별 풀기에서 이분탐색, 여섯 번째 문제이다. 풀이 0. 쉽게 이중for문으로 직접 값을 넣어서 NxN집합을 구성하는 것을 생각할 수 있으나, 절대 이렇게 접근하지 말자. 단계별 문제에서 이분탐색으로 분류되어서 이분탐색으로 접근을 시작했지, 이런 힌트가 없었다면, 엄청 돌아갔을 것 같다. 1. 이분탐색의 첫 번째 요점은, 'mid값을 무엇으로 설정할 것인가'이다. 이말인 즉슨, low와 high값을 뭘로 선택할 것이냐 이다. 여기서 놀라운 점은 입력받는 k값을 high값으로 설정한다는 것이다. 그리고 mid값을 B[k]값으로 반환한다는 점이다. 왜? 2. 일단, NxN의 집합을 1차원 배열에 오름차순 정렬을 하게되면, 그리고 인덱스가 1부터라면, 각 인덱스에 해당하는 값들은 인덱스보다 작거나..