해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 문제에서 요구하는 것에 대해 알아보자. 해당 문제는 보석의 종류, 보석 갯수 그리고 학생의 수가 주어졌을때, 질투심이 최소가 되게 학생들에게 나누어주는 방법을 구해야하는 문제이다.( 질투심 = 가장 많은 보석을 가진 학생이 가진 보석 수 ) 보석을 나누어주기 위해선 순차탐색을 통해서 반복하면서 보석이 없어질때까지 나누어주는 방법이 처음에 생각이 난다. 하지만 문제에서 입력으로 학생 수가 최대 10억(10^9), 보석의 종류가 최대 30만(300,000)이기 때문에 위와 같은 방법으로 풀면 시간 초과가 발생할 것이라 생각한다. 그래서 다른 방법을 찾아봐야하는데 이 문제를 들여다 보면 ..

해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 해당 문제에서 요구하는 것은 스도쿠의 규칙과 같다. 고정된 9x9 격자의 하나의 인덱스에 값이 비어있으면 그 인덱스와 같은 열, 같은 행 그리고 3x3 단위로 자른 범위의 작은 격자에 같이 속하는 인덱스들은 1~9의 값들을 각각 가져야한다는 것이다. 그래서 알맞은 값을 넣은 격자를 출력하라는 문제이다. 문제에서 요구하는 것이 뭘까? 비어있는 모든 칸에 알맞은 숫자를 넣는 것이다. 비교해야하는 인덱스와 비교하면서 가능하면 값을 넣고 가능하지 않으면 다른 값을 넣는 방식으로 말이다. 해당 인덱스에 들어갈 수 있는 가능한 수 중 가장 짧은 수부터 넣으면 안되나? 그럼 제일 짧은 게 한개의 값을 넣..

33. Search in Rotated Sorted Array - 파이썬 풀이 해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 해당 문제에서 요구하는 것을 알아보자. 풀어서 적어보면 nums라는 오름차순으로 정렬된 배열을 일정 칸만큼 로테이션한 배열에서 target의 인덱스는 어디인가? 이다. 그렇다면 배열이란 뭘까? 하나의 데이터형의 여러 데이터들을 연속적인 메모리 공간에 순차적으로 저장하는 자료구조이다. 이 배열에서 위에서 요구하는 것처럼 target이란 데이터가 어느 인덱스에 있는지 알고 싶다면 어떻게 해야할까? 바로 탐색이다. 배열에서 탐색하는 알고리즘은 완전탐색, 이진탐색, 슬라이딩 윈도우, 투 포인터 등이 있다. 하지만 해당 문제에서 요구하는 시간 복잡도는 O(logN)이..

해당문제 링크목차 문제풀이 아이디어 코드구현 문제풀이 아이디어 먼저 문제에서 요구하는 것을 알아보자. 문제를 풀어보면 물건은 무게 W, 가치 V를 가진다. 이런 물건이 N개가 있을때 용량이 K인 배낭에 물건을 넣으려 한다. 물건의 넣을 수 있는 모든 경우 중 배낭안에 들어간 물건의 가치가 가장 높은 경우는? 결국은 가능한 모든 경우의 수를 구해야 최대 값을 구할 수 있다. 모든 경우의 수를 구하기 위해 생각할 수 있는 방법은 조합, 백트래킹, DP, 브루트 포스 정도를 생각할 수 있다. 문제에서 주어진 시간 제한은 2초이고 물품의 최대 수는 100, 버틸 수 있는 무게는 100,000이다. 백트래킹, 브루트 포스 등은 정확한 시간 복잡도를 구할 수 없..

200. Number of Islands - 파이썬 풀이 해당문제 링크 목차 문제풀이 아이디어 코드구현 문제풀이 아이디어 먼저 문제에서 묻는 것에 대해 알아보자. 섬은 물로 모든 면이 둘러 쌓여있고 수평 혹은 수직방향의 인접한 땅들이 모여 이루어진다. 그렇다면 주어진 그리드에서 섬은 몇 개일까? 문제에서 설명하듯이 해당 문제에선 격자가 주어진다. 그래서 해당 문제를 격자형 그래프로 생각을 해보자. 그래프는 정점과 정점을 연결하는 간선들을 모아놓은 자료 구조이다. 그리고 해당 문제에선 땅(1)을 하나의 정점으로 볼 수 있고 인접하다는 것을 간선으로 볼 수 있다. 그렇게 되면 인접한 땅(1)이 모여서 하나의 섬이 되는데 이 섬을 그래프=연결요소라고 볼 수 있는 것이다. 격자형 그래프에서 하나의 인덱스를 정점..

해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 해당 문제를 보고 처음 생각한 것은 완전 탐색을 통해 벽을 찾고 모든 벽을 0으로 바꾸고 BFS 진행하는 것을 반복하는 방식을 생각했다. 이 경우, BFS가 노드의 개수 만큼 시간복잡도를 가져서 O(NM)의 복잡도를 가지고 N, M 둘다 최대 1000이다. 그리고 벽의 개수 또한 최대 O(NM) 이기에 시간 복잡도가 최악의 경우 1000^4가 나와서 2초 안에 풀 수 없다. 다른 경우를 생각해야할 것 같다. 일단 우리가 원하는 구현은 시작점에서 목표점으로 가는데 벽을 최대 1개 부수고의 최단 거리를 찾는 것이다. 그렇다면 존재하는 모든 벽을 부술 필요가 있을까? 없다. 내가 가는..