My Develop Log

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4

문제 N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 * 5 얼음틀 예시에서는 아이스크림이 총 3개 생성된다. 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니..

문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한 사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 n vert..

이진 탐색 트리란? 이진 트리는 트리의 종류이며, 각 노드가 최대 2개의 자식노드를 갖는 트리이다. 이진 탐색 트리는 다음과 같은 특징을 갖는다. 부모 노드보다 왼쪽 자식 노드가 작다. 부모 노드보다 오른쪽 자식 노드가 크다. 즉, "왼쪽 자식노드< 부모 노드 < 오른쪽 자식 노드"의 규칙을 갖는다. 이러한 성격 때문에 이진 탐색은 O(logN)의 속도를 내며, 탐색 범위가 큰 2,000만을 넘어가는 문제 혹은 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상일 때, 이진 탐색을 떠올려 적용해보기! 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제는 이진탐색으로 결정 문제를 해결하면서 범위를 좁혀나갈 수 있다. 이진탐색을 진행하는 과정은 다음과 같다. 재귀 함수를 통해 이진 탐색 코..

파이썬에서는 우선순위 큐를 활용할 수 있도록 모듈이 제공된다. 1. PrioirtyQueue 모듈 불러온 후 큐 생성하기 from queue import PriorityQueue # 큐 생성 q=PriorityQueue() q2=PriorityQueue(maxsize=8) # maxsize를 활용하여 크기 제한 가능함. 2. 큐에 원소 삽입하기 # put()을 활용하여 원소를 넣음. q.put(3) q.put(4) q.put(1) # (우선순위, 값)의 형태로 저장이 가능함. q2.put((1,'apple')) q2.put((2,'cherry')) q2.put((3,'orange')) 3. 큐에서 원소 꺼내기 # get()을 활용하여 원소를 삭제하고 반환함. print(q.get()) # 1 print(..

Stack이란? 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 Last In First Out(LIFO) 구조를 따른다. 이때, 데이터를 넣는 것을 'push'라고 하고 안에 들어 있는 데이터를 꺼내는 것을 'pop'이라고 한다. 그림으로 표현하면 다음과 같다. 파이썬에서는 Stack을 list를 활용하여 표현하는데 pop(), append()연산을 활용한다. pop() 연산은 O(1)의 시간복잡도를 갖고 있으며, append() 연산 또한 O(1)의 시간복잡도를 갖는다.

연결 리스트(LinkedList)란? 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 구조이다. 즉, 이전 노드는 다음 노드의 주소값을 갖고 있으며, 포인터를 통해 그 다음 노드와 연결을 담당해준다. 배열 vs 연결 리스트 배열은 데이터가 나란하고 인덱스를 통해 값에 대한 접근이 매우 빠르다는 장점이 있다. 하지만, 처음이나 마지막 부분이 아니라 중간에 삭제하거나 삽입할 때 요소들의 재배열이 필요하다. 연결 리스트는 떨어진 공간에 존재하는 데이터를 연결시켜 둔 것으로 필요한 경우 메모리에 공간을 할당해서 사용하고 요소를 중간에 삽입하거나 삭제해도 연결만 바꿔주면 되기 때문에 요소들의 재배열이 필요하지 않다. 하지만, 연결 리스트는 요소에 바로 접근이 가능하지 않고 연결되어 있는 ..