imhamburger 님의 블로그

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

선택 정렬(Selection Sort)데이터가 무작위로 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째에 위치한 데이터와 바꾸는 과정을 반복한다.시간복잡도: O(N^2)array = [8,4,6,2,9,1,3,7,5]for i in range(len(array)): for j in range(i+1, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] #swapprint(array)   삽입 정렬(Insertion Sort) 데이터 집합을 순회하는 과정에서 정렬이 필요한 요소를 뽑아 다시 적절한 곳에 삽입한다.데이터가 정렬되어 있을 때 효..

스택(Stack) 스택은 후입선출(LIFO, Last In First Out) 방식의 자료구조이다.마지막에 삽입된 데이터가 가정 먼저 삭제되는 구조이다. 스택에서 쓸 수있는 메서드에는 push, pop, peek이 있다.push: 데이터를 스택에 추가pop: 스택에서 가장 최근에 추가된 데이터를 제거하고 반환peek: 스택의 가장 상단에 있는 데이터를 반환하지만 제거하지는 X그림으로 이해해보자!  push 처음에 push(1)을 하였다.다음에 push(2)를 하였다.마지막으로 push(3)을 하였다. 그럼, 왼쪽과 같은 그림으로 표현할 수 있다.      pop pop()을 하였더니 마지막으로 push했던 값 3이 제거되고 반환되었다.       peek peek()을 하였더니 값이 제거되지는 않고 가장..

배열(Array) 배열은 연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조이다.배열에 1, 2, 3, 4, 5라는 숫자를 입력하고 컴퓨터 1개의 메모리공간이 1개의 사각형이라고 했을 때, 아래 그림처럼 표현할 수 있다.  연속된 메모리 블록에 저장되므로 인덱스를 통해 빠르게 접근이 가능한 장점이 있다.  그.런.데 저 5개의 메모리공간에 '6'이라는 숫자를 append 하려고 한다면?배열은 고정된 크기를 가지며, 나중에 크기를 늘릴 수 없다.만약 크기를 늘려야 한다면, 새로운 배열을 만들어 기존 데이터를 복사해야 한다. 아래 그림처럼 말이다. 이렇게되면 4개의 메모리공간이 남게되고, 메모리공간에 관하여 효율적이지 못한 단점도 있다.  따라서, 배열의 크기를 동적으로 관리하기 위해서는 ..

이번엔 백준 대회 or 인턴 문제를 풀어보자. 문제는 다음과 같다. 문제설명백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.입력첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ ..

탐욕법(Greedy) 문제를 더 풀어보자.백준 동전 0 이 가장 대표적인 문제라길래 풀어보았다. 문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제입력10 4200151050100500100050001000050000 예제출..

탐욕법(Greedy)은 '탐욕'이라는 말 그대로 현 상황에서 당장 좋은 것만 고르는 방법이다.사실 이론적으로는 이해하기 쉽지만, 막상 문제를 풀라하면 모르겠다. 프로그래머스 체육복 문제를 풀어보자. 문제는 다음과 같다. 문제 설명점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.전체 학생의 수 n, 체육복을 도..