programmers

Programmers, 의상의상의 수 30, 의상의 종류는 1이상 20이하의 알파벳 소문자, '\_'로 이루어져 있다. 의상의 종류가 의상의 수를 넘을 수 없으므로 입력 범위는 한정적이고, 구현에 초점을 맞춘다.해빈이가 입을 수 있는 옷들의 조합을 구해야 한다. 의상의

Programmers, 베스트앨범 genres, plays의 배열 길이가 각각 10000이므로, 시간복잡도 O(N^2)미만 알고리즘을 사용한다.장르별로 가장 많이 재생된 노래를 2개씩 모아 베스트 앨범을 만든다. 노래를 수록하는 기준이 있는데 이를 효율적으로 처리

마라톤 경기에 참여한 선수 중 완주하지 못한 선수를 구하는 문제이다. 마라톤 경기에 참여한 사람들 해시 자료구조에 저장한 뒤 완주한 사람을 제거하여 남아있는 완주하지 못한 사람을 구하도록 한다. C++에선 unordered_multiset, java에선 multiset

가장 간단하게 생각해볼 수 있는 것은 2중 루프로 strstr() 또는 contains()로 전화번호부에 다른 전화번호의 접두사가 있는지 검색하는 것이다. 대략 시간복잡도는 ... 해당 알고리즘은 사용할 수 없다. 각 전화번호를 해시

최대한 다양한 포켓몬을 선택하는 게 목표이므로, 포켓몬을 hash 자료구조에 담아 중복을 제거하여 N/2마리를 선택한다. C++은 unordered_set, Java는 HashSet을 사용한다.

Programmers, 다리를 지나는 트럭입력의 크기가 10^4이라 대략 O(N^2) 이하의 알고리즘을 사용한다. 문제를 푸는 시간보다 어떻게 큐로 풀어야 하지? 라는 고민을 더 오래 한 문제이다. 처음에는 큐를 사용하지 않고 임의의 다리 배열을 만들어 지

Programmers, 주식가격입력의 크기가 10^5이라 대략 O(N^2) 미만 알고리즘을 사용한다. stack으로 풀고 싶어서 여러 방법을 고민해 봤지만, 방법이 떠오르지 않았다. 시간초과라도 맛보자는 생각에 O(N^2)으로 편하게 구현했는데 이게

입력의 크기가 10^6이라 대략 O(N\logN) 이하의 알고리즘을 사용한다. 중복 숫자를 제거한 배열을 반환해야 한다. 배열로 같은 원소라면 무시하거나 스택을 이용해서 스택의 상단과 해당 배열의 원소가 같지 않을 때에만 원소를 삽

프로세스가 대기열 큐에서 우선순위에 따라 실행될 때, 특정 위치의 프로세스가 언제 실행되는지 구하는 문제이다. 우선순위가 높은 프로세스가 나올 때까지 pop()과 push()를 반복하다가 현재 큐에서 우선순위가 가장 높고, 특정 위치의 프로세스라면 그때의 실행 순서를

올바른 괄호쌍을 검사하기 위해 stack을 활용한다. 여는 문자일 때는 해당 문자를 스택에 푸시하고, 닫는 문자일 때는 스택 상단의 원소가 여는 문자인지 확인한다. 닫는 문자만 남았을 수도 있기에 최종적으로 스택이 비어있는지 검사한다.

앞에 기능이 배포될 때 뒤의 기능도 함께 배포되므로, 큐 자료구조를 이용해 배포 순서를 관리한다. 큐의 상단 기능이 배포 완료 될 때까지 걸린 기간을 구하고, 그 기간만큼 뒤에 기능들에도 진행도를 더한다. 뒤에 기능들도 배포가 가능하다면 첫 번째 기능이 배포될 때 뒤에

배열 array가 주어지고, i번째 수부터 j번째 수까지 자르고 정렬한 뒤 k번째 수를 구해야 한다. i,j,k 인자가 2차원 배열로 주어지는 데 인덱스를 신경 쓰며 파싱하면 된다. 임시 배열 sliced를 만들어 i ~ j 범위에 속하는 숫자를 채워 넣은 뒤

0 또는 양의 정수가 주어졌을 때, 이어 붙일 수 있는 가장 큰 수를 구해야 한다. 문제를 봤을 때, 직관적으로 그리디 풀이를 생각해 봤다. 정렬하여 가장 큰 수부터 이어 붙이면 되지 않을까? 작은 수를 먼저 이어 붙인다면 가장 큰 수를 만들 수 없다. 위 명제를 참으

H-index를 구하는 문제이다. H-Index란 어떤 과학자가 발표한 논문 중에서, 해당 논문이 받은 인용 횟수가 논문의 수와 같거나 많은 최댓값이다. 예시에서 논문의 수와 인용 횟수가 주어진다. H-index는 자료에서 주어진 인용 횟수로 구할 수 있다고 생각하여,

한 번에 하나의 작업만을 처리할 수 있는 디스크에서 각 작업의 요청부터 종료까지 걸린 시간을 가장 줄이는 방법을 구하는 문제이다. 각 작업 큐에는 작업 요청 시점과 작업 소요 시간이 주어진다. 한 작업이 걸리는 시간은 작업 소요 시간 + 대기 시간이며, 대기 시간은 현

입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다. 큐에서 주어진 숫자를 삽입하고, 최댓값과 최솟값을 삭제하는 연산이 주어진다. 삭제하는 연산에서 효율적으로 최솟값이나 최댓값을 찾아내는 게 핵심이다. 모든 연산을

스코빌 지수를 K 이상으로 만들어야 한다. 이는 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 합하여 만들 수 있다. 매번 섞으며 스코빌 지수가 K가 이상인지 확인하기 위해 힙 자료구조인 우선순위 큐를 사용한다. 최소 힙을 사용하면 가장 맵지 않은 음식과 두 번째

Programmers, 소수 찾기입력의 크기가 $7$이라 구현에 초점을 맞춘다.한 자리 숫자가 적힌 종이 조각이 흩어져 있고 이를 마음대로 붙여 가능한 소수 개수를 구해야 한다. 종이 조각이 7개 있다면, 7개 중에서 1개를 고를 수 있고, 2개를 고를 수 있고...

Programmers, 카펫입력의 크기가 5000, 2'000'000이라 대략 O(n) 이하의 알고리즘을 사용한다.아래와 같은 카펫이 주어졌을 때, 갈색 타일과 노란 타일 개수로 전체 카펫의 가로와 세로 길이를 구해야 한다.해당 문제는 규칙을 찾아 2차 연립 방정식

Programmers, 피로도입력의 크기가 8이라 구현에 초점을 맞춘다. 초기 피로도, 던전의 개수, 던전을 돌기 위한 최소 피로도가 주어진다. 유저가 탐험할 수 있는 최대 던전 수를 구해야한다. 해당 문제는 완전 탐색 문제로 dfs를 이용

입력의 크기가 10^2이라 구현에 초점을 맞춘다. n 개의 송전탑이 트리 형태로 연결되어 있을 때 전선 중 하나를 끊어 2개로 분할하려고 한다. 이때 분할된 전력망이 갖는 개수를 최대한 비슷하게 맞출 때 그 차이를 구하는 문제이다. 완전 탐색 문제로 전선을 하나씩

Programmers, 모음사전 입력의 크기가 5이라 구현에 초점을 맞춘다.모음(A, E, I, O, U)으로 이루어진 단어의 순위를 구하는 문제이다. 예시를 이해하고 규칙을 찾아내는 과정이 조금 까다로웠다. 규칙을 알면 구현은 굉장히 쉽기 때문에 예시를 제대로

입력의 크기가 30이라 구현에 초점을 맞춘다. 일부 학생들이 체육복을 도난 당했고 일부 학생들이 여분이 있어 빌려줄 수 있다. 단, 체육복은 체격순으로 바로 앞 번호 학생이나 뒷 번호 학생에게만 빌려줄 수 있다. 체육복을

조이스틱을 이용해 'AAA...' 문자열을 주어진 name으로 만드는 최소 연산 횟수를 구해야 한다. 조이스틱은 크게 2가지 기능이 있다. 상하로 움직여 알파벳을 변경하는 것이고, 좌우로 이동해서 'A'가 아닌 알파벳을 최소한의 움직임으로 찾아야 한다. 상하로 움직여

입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다. 어떤 숫자에서 K개의 수를 제거했을 때 얻을 수 있는 가장 큰 수를 구해야 한다. 가장 큰 수가 되려면 앞자리 수가 가장 커야 한다. 따라서 K개의 수를 지울

Programmers, 구명보트입력의 크기가 50000이라 대략 O(NlogN) 이하의 알고리즘을 사용한다.무인도에 갇힌 사람들을 구명보트로 구출해야 한다. 구명보트에는 무게 제한이 있으며 최대 2명을 태울 수 있다. 구명보트를 최소한으로 사용

Programmers, 단속카메라입력의 크기가 10^이라 대략 O(N^2) 이하 알고리즘을 사용한다.고속도로를 이동하는 차량의 경로가 주어질 때 모든 차량을 감시할 수 있도록 단속 카메라를 설치하는 문제이다. 단속 카메라 최소 개수를 구해야 한다. 고속도로 진입

입력의 크기가 90이라 구현에 초점을 맞춘다. 이친수란 이진수 중 특별한 성질을 갖는 수이다. 이친수는 0으로 시작하지 않고 1이 두 번 연속으로 나타나지 않는 특징을 가진다. N자리 이친수의 개수를 구해야 한다. 이전에 1로 끝난 수는 반드시 뒤에 0이

BOJ 입력의 크기가 100이라 구현에 초점을 맞춘다.자릿수가 주어지면 계단수의 개수를 구해야 한다. 개단수란 456656처럼 모든 자리의 차이가 1인 숫자를 말한다. 0으로 시작하는 수는 계단수가 아니다.계단수를 찾기 위해 먼저 규칙을 찾고 점화식을 세워야 한다.

Programmers Lv3, 최고의 집합입력의 크기가 10,000이라 대략 $O(N^2)$이하 알고리즘을 사용한다.자연수 n개로 이루어진 중복 집합 중 각 원소의 합이 S가 되는 집합에서 각 원소의 곱이 최대가 되는 집합을 구해야 한다.자연수 중복 집합임을 명심해야

Programmers Lv3, 1차 셔틀버스 크루가 몇 시에 셔틀버스를 기다리는지를 알고 있을 때, 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시간을 구해야 한다.콘은 마지막 버스를 타고 가면 된다. 여기서 문제는 버스 정원이 주어지기 때문에

Programmers Lv3, 인사고과 입력의 크기가 100,000이라 대략 O(N \* logN) 이하 알고리즘을 사용한다.인사고과에 따라 인센티브를 지급하는데, 근무 태도 점수와 동료 평가 점수가 어떤 임의의 사원보다 두 점수 모두 낮은 경우 인센티브를 받지 못한

Programmers Lv3, 파괴되지 않은 건물 입력의 크기가 1,000과 250,000이라 대략 O(N^2)이하 알고리즘을 사용한다.스킬에 따라 벽 내구도를 낮추고, 높인다. 마지막에 벽 내구도가 0을 초과하여 부서지지 않은 개수를 반환하면 된다. 최대 $100

Programmers Lv3, 순위입력의 크기가 100이라 대략 O(N^3)이하 알고리즘을 사용한다.초기 접근 방법은 순서를 구하는 것이라 생각하여 위상 정렬을 사용하였다.위상정렬로 순서 구함.1번에서 나온 순서로 다시 노드를 돌면서 순서 검증 하지만 위상 정렬로

Programmers Lv3, 자물쇠와 열쇠입력의 크기가 20이라 구현에 초점을 맞춘다.처음에 해당 지문을 제대로 이해하지 못해서 시간 복잡도에 오해가 있었다. 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와

Programmers Lv3, 불량 사용자 입력의 크기가 8이라 구현에 초점을 맞춘다.문제에 처음 접근할 때, 해시 자료구조인 unordered_set 배열에 가능한 목록을 담았다. 예를 들어 아래와 같이 담긴다. dfs를 이용해 순열을 만들고, 중복 순열을 제거하는

입력의 크기가 1,000,000이라 대략 O(N * logN)이하 알고리즘을 사용한다. 임의의 위치에서 삽입과 삭제가 반복된다. 직관적으로 list를 사용하는 문제임을 알 수 있다. 배열로 푸는 경우 임의의 위치에서 삭제하고 삽입하는 과정에서 배열 복사 비용

Programmers Lv3, 다단계 칫솔 판매입력의 크기가 10,000이라 대략 O(N^2)이하 알고리즘을 사용한다.다단계 칫솔 판매 문제로 등록인, 추천인, 판매인과 판매 수량이 주어진다. 수익의 90%는 자신이 갖고, 10%에 대해선 추천인에게 주어야 한다.

Programmers Lv3, 길 찾기 게임 입력의 크기가 10,000이라 대략 O(N^2)이하 알고리즘을 사용한다.같은 레벨에 있는 노드는 같은 y좌표를 가지고, 임의의 노드 V 왼쪽 서브 트리에 있는 모든 노드 값은 V의 X값보다 적고, 오른쪽 서브 트리에 있는

Programmers 3차] 방금그곡 입력의 크기가 작아 대략 O(N^2)이하 알고리즘을 사용한다.방송된 곡의 정보와 네오가 기억하는 멜로디가 주어진다. 곡의 멜로디는 노래가 시작하는 동안 계속해서 반복된다. 네오가 기억하는 멜로디가 반복된 곡의 멜로디에 있는

Programmers k진수에서 소수 개수 구하기 입력의 크기가 1,000,000이라 대략 O(N * logN)이하 알고리즘을 사용한다.양의 정수 n이 주어지고, 이 숫자를 k진수로 변환해야 한다. 변환된 수 안에 소수가 몇 개인지 구해야 한다. 예를 들어, 437

Programmers [3차] 파일명 정렬 입력의 크기가 1,000이라 구현에 초점을 맞춘다.파일명이 크게 HEAD, NUMBER, TAIL로 이루어져 있을 때 HEAD를 기준으로 사전 순으로 정렬하고(대소문자 구분 X) NUMBER 숫자 순으로 정렬한다. 이때, 숫

입력의 크기가 200,000,000과 200,000이다 O(N * LogN)이하 알고리즘을 사용한다.단순하게 구현하면, 한 명씩 건너면서 건널 때마다 돌다리값을 -1로 줄일 수 있다. 돌다리값은 200,000,000이기 때문에 200,000 \* 200,000,00

그래프 문제로 정점이 최대 100개, 간선이 대략 5000개가 있다. 대략 O(N^2)이하 알고리즘을 사용한다. n개의 섬 사이에 다리를 건설하는 비용을 줬을 때 모든 섬을 연결하는 최소 다리 건설비용을 구해야 한다. 즉, 최소 신장 트리를 구하는 문제라고 볼 수

Programmers Lv3, 단속카메라입력의 크기가 25라 대략 O(N^2)이하 알고리즘을 사용한다.경주로 건설 비용을 구해야 한다. 직선 도로는 100원, 방향이 달라지면 600원이 든다. 이때 {0, 0}에서 출발하여 {r - 1, c - 1}까지 도로를

Programmers 메뉴 리뉴얼입력의 크기가 작아 구현에 초점을 맞춘다. 각 손님이 주문한 단품 메뉴가 주어지고, 만들 코스 요리의 단품 메뉴 개수가 주어질 때 손님들이 가장 많이 주문한 단품 메뉴를 고려하여 코스 요리를 구성한다. 메뉴 구성이 여러 개라면 배열에 담

입력의 크기가 작아 구현에 초점을 맞춘다. 5개의 대기실에 응시자가 자리에 앉아 있다. 거리두기로 인해 맨해튼 거리(2) 이하로 앉지 않아야 한다. 단, 응시자 사이에 파티션이 있다면 붙어서 앉을 수 있다. 거리두기 준수 여부를

정점은 최대 200개, 간선은 최대 100,000개가 존재한다. 무지와 어피치가 택시를 타고 각자 집에 귀가한다. 함께 탑승할 수 있을 때 최저 택시 요금을 구해야 한다. 택시 요금을 가중치로 보고, 최단 거리를 구하는 알고리즘을 적용할 수 있다.

Programmers Lv3, N으로 표현 숫자 N이 주어지고, 최대 8번 사용해서 number 숫자를 만들어야 한다. +, -, \*, /와 괄호를 사용할 수 있다. 문제 예시를 보면 사칙연산 외에도 문자열을 붙여주는 경우를 고려해야 한다.단순히 사칙연산,

Programmers Lv3, 네트워크 컴퓨터의 개수와 연결에 대한 정보가 담긴 2차원 배열이 주어질 때 네트워크의 개수를 반환하는 문제이다.각 컴퓨터는 자신의 네트워크를 가지고, 연결이 되어 있을 때 같은 네트워크라고 판단한다. DFS와 BFS, Union-Fin

Programmers 1차 뉴스 클러스터링 입력의 크기가 1,000이라 대략 O(N^2)이하 알고리즘을 사용한다. 두 문자열이 주어질 때, 두 문자열 사이의 자카도 유사도를 구해야 한다. 자카도 유사도란 두 집합의 교집합의 크기를 합집합의 크기로 나눈 값이며.

Programmers Lv3, 단어 변환단어의 길이는 10 이하, 단어 집합의 크기는 50 이하이므로 구현에 초점을 맞춘다.두 개의 단어 begin, target이 주어지고 단어 집합이 주어진다. begin에서 target으로 변환할 때 한 번에 단어 한 개만 바꿀 수

Programmers Lv3, 등굣길 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구하는 문제이다. 집은 왼쪽 최상단에 위치하며, 학교는 우측 최하단에 위치한다. 오른쪽과 아래 방향으로만 움직일 수 있다.오른쪽, 아래 방향으로만 움직일 수 있으니, 학교에 도착했다면

Programmers Lv3, 등산코스 정하기 여러 개의 출입구와 산봉우리가 주어진다. 출입구에서 산봉우리까지 갔다가 같은 출입구로 되돌아올 때 휴식 없이 이동해야 하는 가장 긴 시간(intensity)이 최소가 되도록 등산 코스를 정해야 한다. 딱 하나의 산봉우리만

Programmers Lv3, 외벽 점검 - 레스토랑 외벽의 취약한 지점을 최소한의 친구들을 파견해 점검한다. 친구들이 1시간 동안 이동할 수 있는 거리를 주며, 모든 친구를 투입해도 1시간 내 취약 지점을 점검할 수 없으면 -1을 반환한다.취약 지점이 {1,5,6,

Programmers Lv3, 광고 삽입시청자들의 누적 재생 시간이 가장 많은 곳에 공익 광고가 들어갈 시작 시간을 구해야 한다. 동영상 재생 길이, 공익 광고 재생 길이, 시청자들이 동영상을 재생했던 구간 정보가 주어진다.크게 다음 단계로 문제에 접근할 수 있다.

Programmers Lv3, 양과 늑대특정 노드에 방문할 때마다 해당 노드에 있던 양과 늑대가 따라온다. 루트 노드에서 출발하여 양과 늑대를 모을 때, 최대한 많이 모을 수 있는 양의 개수를 반환한다. 늑대의 수가 양보다 많거나 같아지면 양이 잡아먹히니, 잡아먹히지

Programmers Lv3, 기둥과 보 설치문제의 요구사항에 따라 기둥과 보를 설치하거나 제거하여, 남아있는 건축물을 정렬하여 반환하는 문제이다. 먼저 기둥과 보를 설치하는 방법을 알아보자.기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위

모든 문제를 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구해야 한다. 알고리즘 공부를 해서 시간당 1의 알고력을 높일 수 있고, 코딩 공부를 해서 시간당 1의 코딩력을 높일 수 있다. 또한, 문제를 풀어 x 시간을

9월 15일에 발생하는 초당 최대 처리량을 구해야 한다. 이는 임의의 시간부터 1초간 처리하는 요청의 최대 개수를 말한다.문제를 풀기 위해 가장 중요한 부분은 입력 문자열 파싱과 초당 최대 처리량을 어떻게 구할지다.

한 변의 길이가 1인 정삼각형을 2n+1 개를 이어 붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있다. 이때 사다리꼴 윗변과 변을 공유하는 삼각형을 이어 붙일 수 있다. 이는 tops\[] 배열로 주

Programmers Lv3, 매칭 점수html 문자열 파싱 문제이다. 웹 페이지들의 매칭 점수를 구한 뒤 가장 큰 매칭 점수를 가진 웹 페이지 인덱스를 출력한다. 매칭 점수는 기본 점수와 링크 점수의 합으로 계산하며, 기본 점수는 해당 웹 페이지의 텍스트 중 검색어가

Programmers Lv3, 카드 짝 맞추기게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는 데 필요한 키 조작 횟수의 최솟값을 구해야 한다. 같은 그림을 제거하지 않으면, 다시 원상 복귀되므로 같은

A와 B가 n개의 주사위 중 n/2 주사위를 골라 주사위를 모두 굴린 후 나온 수들을 비교하여 점수가 큰 쪽이 이기는 주사위 게임을 한다. 주사위마다 쓰인 수의 구성이 모두 다를 때 A가 자신이 승리할 확률이 가장 높은 주사위

n개의 카드로 이루어진 카드 뭉치와 여러 코인이 주어진다. 아래 규칙에 따라 진행된다. 규칙 처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가

Programmers Lv3, 가장 긴 팰린드롬 입력의 크기가 2,500이라 대략 N^2이하 알고리즘을 사용한다. 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 한다. 문자열 s가 주어질 때, s의 부분 문자열 중 가장 긴 팰림드롬의 길이