📒 힙(heap)완전 이진 트리(Complete Binary Tree)최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 (루트가 가장 작음)최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 (루트가 가장 큼) 📒 힙 자료구조 구현heapq 모듈 이용heapq.heappush(heap, item): item을 heap에 추가heapq.heappop(heap): heap에서 가장 작은 원소를 popreturn 하지 않고 접근만 하려면 인덱스로 접근heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환함 ✏️ heapq 모듈을 이용하여 최소 힙 구현heapq 모듈은 기본적으로 최소 힙으로 구현되어 있음import heapqheap = []heapq.h..

💻 Problem문제 보러 가기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + ..

💻 Problem문제 보러 가기 세준이는 1부터 N까지 모든 수를 차례대로 공백 없이 한 줄에 다 썼다. 그러고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.) 💡 Approach1부터 숫자를 하나씩 늘리면서 입력값과 비교한다.그 숫자 역할이 n이고 입력값은 num이다.n을 하나씩 늘리면서 num의 한 글자씩 비교한다.n에 들어가는 숫자에 num[i]가 ..

🌐 Web APIs? Application Programming Interfaces 웹 개발을 하다 보면 브라우저 안에서 아주 많은 기능을 기본적으로 사용할 수 있다.예를 들어, 서버와 통신하거나, 사용자의 위치를 가져오거나, 알림을 띄우는 것처럼 복잡한 기능들도 자바스크립트만으로 실행할 수 있다.이처럼 브라우저가 기본으로 제공하는 기능들을 통칭해서 Web API라고 부른다. 🧰 Web API 기능Web API는 말 그대로 “웹 환경에서 사용할 수 있도록 브라우저가 제공하는 API”를 뜻한다.이 API들을 사용하면 자바스크립트로는 직접 하기 어려운 작업도 간단하게 구현할 수 있다.대표적인 Web API는 다음과 같다.DOM APIHTML 요소를 동적으로 조작할 수 있음Fetch APIHTTP 요청을 ..

💻 Problem문제 보러 가기 길이가 N인 수열 A_1, ..., A_N이 주어집니다. 수열의 모든 수는 서로 다른 1 이상 N 이하의 수입니다. 아래 조건을 모두 만족시키는 (i, j) 정수쌍의 개수를 구하세요. 1 . A의 i번째 수부터 j번째 수까지가 오름차순으로 배열되어 있다. 즉, i k에 대해 A_k . 💡 Approach처음에 예제 이해가 잘 안됐는데 문제 내용은 아래와 같다. (i, j) 구간의 수열이 정렬된 연속한 부분수열이면 만족한다.만족하는 경우의 (i, j) 정수쌍 개수를 구하면 된다. N의 범위가 1 반복문을 하나만 쓰는 방법을 생각해야 한다. 오름차순 구간 길이에 따른 (i, j) 쌍 개수를 구해보면 아래와 같다.오름차순 구간 길이(i, j) 쌍 개수가능한 (i, j) 쌍1..

💻 Problem문제 보러 가기 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. n은 양수이며 11보다 작다. 💡 Approach dp[1] = 1dp[2] = 2dp[3] = 4dp[4] = 7dp[5] = 13...직접 세보면서 점화식을 구한다.dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 예를 들어, dp[5]의 경우, 5를 1, 2, 3 조합으로 더해야 한다.1로 시작하는 조합, 2로 시작하는 조합, 3으로 시작하는 조합을 구해보면 아래..

💻 Problem문제 보러 가기 여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 출력하자...

💻 Problem문제 보러 가기 창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다.'.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 연결된 선분을, '\'은 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점이 연결된 선분을 나타낸다.창영이가 그린 도형의 넓이를 출력하는 프로그램을 작성하시오. 💡 Approach처음엔 어려울 거라고 생각했는데 풀고 나니 쉬운 문제였다. '/'나 '\'은 무조건 넓이가 0.5이다.'.'의 넓이는 1이지만, 문제는 안쪽 도형의 영역인지 바깥쪽 빈 영역인지를 알아야 한다. 도형이 완성된다는 조건이니 '/'나 '\'로 도형을 열었으면 안쪽 영역, 이를 다시 닫았으면 바깥쪽 영..