문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12911 문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. 제한 사항 n은 1,000,000 이하의 자연수 입니다. 입출력 예 n result..

완전 탐색 완전 탐색은 모든 경우의 수를 다 해보는 것으로 Brute Force라고도 한다. 컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 해보지만, 시간 역시 최대로 소모된다. for문을 사용하여 정말 모든 경우를 탐색하는 방법과, 재귀, DFS/BFS/ 백트래킹, 비트마스크 등이 존재한다. 위와 같은 방법들을 간단하게 소개하도록 하겠다. 재귀 호출 - 어느 함수가 자기 자신을 다시 참조하는 방법이다. $f(n) = f(n-1) + f(n-2)$ 등의 피보나치 수열, $n! = (n-1)! * n$ 과 같은 팩토리얼 연산 등에서 자주 등장한다. 하지만 재귀함수는 잘못 사용하면 복잡도가 어마어마하고, 함수가 끝날 때까지 자기 자신 호출 이후의 명령문이 수행되지 않는다. 또한 반드시 종료조건이 있어..

비트 조작 비트(bit)는 Binary Digit를 줄인 말로 데이터를 나타내는 최소 단위이다. 0과 1 두 값 중 하나를 가질 수 있다. 8bit가 모여서 1Byte가 되며 이후 단위들은 아래와 같다. 접두어(SI) 이름 계산법 접두어(IEC) 이름 계산법 킬로($10^3$) 1킬로바이트(kilobyte)/kB 1000B=1kB 키비($2^{10}$) 1키비바이트(kibibyte)/KiB 1024B=1KiB 메가($10^6$) 1메가바이트(megabyte)/MB 1000KB=1MB 메비($2^{20}$) 1메비바이트(mebibyte)/MiB 1024KiB=1MiB 기가($10^9$) 1기가바이트(gigabyte)/GB 1000MB=1GB 기비($2^{30}$) 1기비바이트(gibibyte)/GiB 10..

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

문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42629 문제 설명 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위..

힙 힙은 이진 트리에서 특정한 조건을 이룬 구조입니다. 이진 트리 T의 높이가 h라고 할때 h-1까지 완전 이진 트리이다. 모든 잎 노드는 깊이가 h나 h-1이다. 깊이 h의 모든 잎 노드들의 경로는 h-1의 모든 잎 노드보다 왼쪽에 있다. 힙은 역시 부분 순서 트리(Partial order tree)이기도 한데, 이는 모든 노드가 자식 노드보다 값이 크거나 같은 트리 ($key(parent)\geq key(child)$)입니다. -> 완전 순서 트리 (Total order tree) = 완전 정렬된 트리. 이진 탐색 트리에서는 중복된 값이 불가능하나, 힙에서는 가능합니다. 부모가 자식의 키 값보다 작은 최대 히프(max heap), 부모가 자식 노드보다 작은 최소 히프 (min heap) 두 종류가 존..

트리 트리 = 노드(node)로 이루어진 자료 구조. 하나의 루트 노드가 존재하고, 이로부터 0개 이상의 자식 노드들이 존재합니다. 이 노드들이 서브트리(subtree)를 구성합니다. 루트와 서브 트리, 각각 노드들간은 간선(edge)로 연결되어 있습니다. 그래프의 한 종류로써 트리는 asyclic connected(undirected) graph, 사이클이 없는 비방향성 그래프입니다. 루트 노드 (Root node) : 부모가 없는 노드 (트리의 처음) 잎 노드 (Leaf node) : 자식이 없는 노드 (트리의 마지막들) 부모 노드(Parent node) , 자식 노드(Child node)의 관계가 있음 노드의 깊이(Depth) : 루트노드(0)으로부터 도달하기 위해 거쳐야 하는 간선의 수 (부모 노..

문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 512 MB 469 261 226 61.413% 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각..

문제 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 송신 탑(높이..

문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 256 MB 2373 545 412 21.950% 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 ..