알고리즘(PS)

힙(Heap)이란? 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 사이에는 항상 대소관계가 정해지는 자료구조를 말한다. 여기서 부모 노드 >= 자식 노드면 최대 힙, 부모 노드 <= 자식 노드이면 최소 힙이다. 쉽게 말해서 배열 안의 값들이 오름차순(최소

특정 전화번호가 다른 전화번호의 접두어(앞에서부터 시작하는 글자)인지 확인하는 간단한 문제이다. 파이썬에는 startswith 라는 내장 함수가 있는데, 기능은 다음과 같다.따라서, startswith 를 사용하면 짧고 간결한 코드로 이 문제를 끝낼 수 있다. 그리고,

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.124 나라에는 자연수만 존재합니다.124 나라에서는 모든 수를 표현할 때 1, 2, 4만 사용합니다.예를 들어 124 나라에서 사용하는 숫자는 다음과 같이 변환

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.예를들어0ms 시점에 3ms가 소요되는 A작업 요청1ms 시점에 9ms가 소요되는 B작업 요

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를

1. 문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다."죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.개

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.1, 2, 31, 3, 22,

1. 문제 설명 2. 해설 얼핏 보면 시키는 대로 구현하면 되지 않나 싶지만 시간 제한이 1초기 때문에 효율성을 생각해서 풀어야 한다. 우선 'R'은 배열을 뒤집는 함수니까 R이 2번 들어오면 뒤집는 의미가 없으므로 없애주고, rev라는 플래그를 하나 만들어서 뒤

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.체스판의 가로 세로의 세로의 길이 n이

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을

1. 문제 설명 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4sev

스택 활용의 바이블같은 문제로, 스택을 활용하여 괄호가 잘 닫겼는지 검사하면 된다. 문장의 길이는 상관없고, 문장을 한 글자씩 검사하면서 열리는 괄호일 경우 스택에 삽입하고, 닫히는 괄호의 경우 스택의 끝을 검사해서 짝이 맞을 경우 그대로 pop해주면 된다. 그러니까,

1. 문제 설명 2. 해설 처음에 O(n^2)의 시간복잡도로 풀었다가 시간 초과가 나서 어떻게 하면 시간복잡도를 줄일 수 있을까 고민해보았다. 처음에 입력의 오른쪽부터 검사하는 방식을 사용했는데, 여기서 아이디어를 조금 바꿔서 스택을 다시 사용해봤다.

큐의 처음과 끝이 연결되어 있는, 원형 큐를 적용하여 해결할 수 있다.그림으로 설명하자면, K-1의 주기로 start와 target index가 회전한다. 인덱스의 회전은 인덱스에 k-1을 더해준 다음 그 사이클의 큐의 길이만큼 나머지 연산을 해주면 쉽게 구할 수 있다

1. 문제 설명 업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다.

문제의 크기를 3개씩 잘라서 풀어내는 분할 정복 문제. 내 접근 방식은 이렇다.종이가 같은 수로 이루어져 있는지 검사한다.같은 수로 이루어지지 않았다면 3\*3개로 종이를 자른다.모든 종이를 탐색할 때까지(종이의 크기가 1이 될 때까지) 1번, 2번을 반복한다.처음에는

주사위 굴리는걸 시뮬레이션 해보는, 삼성 냄새가 풀풀 풍기는 문제. 주사위를 굴렸을때 각 면이 어디로 이동하는지 알아두고, 그걸 코드로 바꿔주면 된다.주사위를 굴렸을 때 지도의 숫자가 0이 아니면 주사위의 바닥면에 숫자를 복사하고, 지도의 값은 0으로 바꿔준다주사위를

DFS/BFS와 이분 탐색을 같이 사용하는 문제. 잘 만든 문제라고 생각한다.우선 중량제한의 최대값이 10억이기 때문에 이분 탐색으로 접근해야 한다. 어떻게 접근하면 좋을까?left = 1, right = 입력받은 중량제한의 최대값으로 두고 시작한다.mid값을 구하고,

문제 설명대로 구현하고 시뮬레이션하는 전형적인 삼성식 문제. 이런 문제는 코딩 기초체력 기르기에 아주 좋다.아무튼, 이 문제에서 조심할 조건은 미세먼지는 사방으로 동시에 퍼진다는 조건이다. 이 조건 때문에 우리는 단순히 이중 for문을 돌면서 먼지가 있으면 일정량 퍼지

1. 문제 설명 2. 해설 스터디그룹 하면서 풀다가 시간초과나서 어디서 효율성이 안좋지? 고민을 오래 했고, 이제서야 풀었다... 배열 한개에 나무 정보를 담아서 처리하니 시간초과가 났고, 그래서 그냥 3차원 배열 만들었다.

이중 for문을 사용해서 k가 될 때까지 반복해줘도 되지만, 우리는 여기서 '투 포인터' 기법으로 접근해볼 것이다.💡 투 포인터(Two Pointer)리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘위의 예제 중 \[3, -2, -

문제를 이해하는게 조금 어려웠다. 쿠폰 사용 기준을 이상하게 이해했더니 문제가 안 풀리지...아무튼, 이 문제는 기본적으로 투 포인터로 접근 가능하지만 일정 크기의 윈도우를 끝까지 밀어가면서 푸는 슬라이딩 윈도우 기법으로 접근해도 된다. 연속해서 k개의 접시만 먹을 수

1. 문제 설명 2. 해설 입력받은 알파벳으로 만들 수 있는 조합을 모두 만들고, 거기서 자음 2개 모음 1개를 포함하는 경우를 찾아서 출력해주면 되는 문제. 파이썬의 combinations 라이브러리를 써도 되겠지만, 이번에는 백트래킹으로 조합을 직접 구현했다.

1. 문제 설명 2. 풀이 이 문제를 풀기 위해 유니온 파인드(union-find) 알고리즘이 필요하다. > 유니온 파인드 알고리즘이란? > > 두 노드가 같은 그래프에 있는지 확인하는 알고리즘으로, 두 노드가 같은 그래프에 없다면 상호 배타적 집합(Disjoin