📌문제N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하시오.단 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다. 📌풀이모든 원소가 정렬이 된 상태로 입력되므로 이진 탐색을 이용하여 값이 x인 원소의 개수를 O(logN)에 찾아낼 수 있음수열 내 x가 존재한다면 연속적으로 나열되어 있음따라서 x가 처음 등장한 인덱스와 마지막으로 등장한 인덱스의 차를 계산 이진 탐색 함수 2개를 사용하여 문제 해결1. 가장 첫번째 위치를 찾는 이진 탐색 함수2. 가장 마지막 위치를 찾는 이진 탐색 함수 📌코드# 정렬된 수열에서 값이 x인 원소 개수를 세는 메서드def count_by_value(array, x)..
📌문제정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 A,B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는데에는 A+B번의 비교를 해야한다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. N개의 숫자 카드 묶음의 각각의 크기가 주어질 때 최소한 몇 번의 비교가 필요한지 구하시오. 📌풀이항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해 보장매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내어 이를 합친 뒤 다시 리스트에 삽입우선순위 큐 사용(원소를 넣었다 빼는 것만으로 정렬된 결과 얻음) 📌코드import heapqn = int(input())# 힙에 초기 카드 묶음을 모두 삽입h..
📌문제https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 📌풀이스테이지 번호를 1부터 N까지 증가시키며 해당 단계에 머물러 있는 플레이어들의 수를 계산플레이어들의 수 정보를 이용하여 모든 스테이지에 따른 실패율을 계산실패율 기준으로 내림차순 정렬 📌코드def solution(N, stages): answer=[] length=len(stages) #스테이지 번호를 1부터 N까지 증가 for i in range(1, N+1): #해당 스테이지에 머물러..
📌문제일직선상의 마을에 여러 채의 집이 위치한다. 이 중에서 특정 위치의 집에 특별히 한개의 안테나를 설치하기로 하였다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록 설치하려고 한다. 이때 안테나는 집이 위치한 곳에만 설치할 수 있고 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.집들의 위치가 주어질 때 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오. 📌풀이중간값에 해당하는 위치의 집에 안테나를 설치했을 때 안테나로부터 모든 집까지의 거리의 총합이 최소가 됨모든 집의 위치 정보를 입력받은 뒤 이를 정렬해서 중간값 출력 📌코드n = int(input())data = list(map(int, input().split()))data.sort()print(..
📌문제도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.1. 국어 점수 감소하는 순서2. 국어 점수 같으면 영어 점수 증가하는 순서3. 국어 영어 점수 같으면 수학 점수 감소하는 순서4. 모든 점수 같으면 이름이 사전 순으로 증가하는 순서 📌풀이튜플을 원소로 하는 리스트가 있을 때 리스트를 정렬하면 각 튜플을 구성하는 원소의 순서에 맞게 정렬만약 튜플이 3개의 원소로 구성된다면 첫번째 원소의 순서에 맞게 정렬, 첫번째 원소 값이 같은 경우 두번째 원소의 순서에 맞게 정렬, 두번째 원소의 값이 같은 경우 세번째 원소의 순서에 맞게 정렬sort 함수의 key 속성 사용📌코드n = int(input())studen..
📌문제N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어진다. 우리는 수와 수 사이에 연산자를 하나씩 넣어 수식을 하나로 만들 수 있는데 이때 주어진 수의 순서를 바꾸면 안된다.식의 계산은 연산자 우선순위 무시하고 앞에서부터 진행한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. N개의 수와 N-1개의 연산자가 주어졌을 때 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.📌풀이모든 경우의 수를 계산하기 위해 DFS 혹은 BFS를 이용사칙 연산을 중복으로 사용할 수 있기 때문에 중복 순열을 계산만약 n=4라면 사칙연산 중 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려 📌코드n = in..
📌문제https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 📌풀이문제에 제시된 알고리즘을 재귀적으로 구현 📌코드#균형 잡힌 문자열의 인덱스 반환def balanced_index(p): count=0 #왼쪽 괄호 개수 for i in range(len(p)): if p[i]=='(': count+=1 else: count-=1 if count==0: return i #올바른 ..
📌문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나눠지며, 특정한 위치에 바이러스가 존재할 수 있다. 바이러스의 종류는 1~K번까지 K가지가 있으며, 모든 바이러스는 이 중 하나에 속한다.모든 바이러스는 1초마다 상 하 좌 우의 방향으로 증식하는데 매초 번호가 낮은 종류의 바이러스부터 먼저 증식한다.시험관의 크기와 바이러스의 위치 정보가 주어졌을 때 S 초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 📌풀이너비우선탐색(BFS) 이용낮은 번호부터 증식하므로 초기에 큐에 원소를 삽입할 때 정렬해서 낮은 바이러스의 번호부터 삽입 📌코드from collections import dequen, k = map(int, input().split())gr..
📌문제연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며 벽은 칸 하나를 가득 차지한다.일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며 꼭 3개를 세워야 한다.벽을 3개 세운 뒤 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 할 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오. 📌풀이벽의 개수가 3개가 되는 모든 조합을 찾은 뒤에 조합에 대해 안전 영역의 크기를 ..
📌문제어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 특정한 도시 X부터 출발하여 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하시오. 📌풀이모든 간선의 비용이 1로 동일할 때는 너비 우선 탐색(BFS) 이용하여 최단 거리 찾음특정한 도시 X를 시작점으로 BFS 수행하여 모든 도시까지의 최단 거리를 계산한 후 그 값이 K인 경우에 해당 도시 번호 출력 📌코드from collections import deque# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호n, m, k, x = map(int, input().split())graph = [[] for _ in range(n + 1)]..