boj

회사에 있는 사람의 이름을 알파벳 순으로 출력해야 한다. Hash자료구조를 사용해 어떤 사람이 회사에 있는지 O(1)에 알아낸 후 이를 저장하여 정렬하도록 하자. 동명이인은 없으므로 C++ unordered_set, Java는 HashSet을 사용한다.

포켓몬 이름이 주어지면 번호를 답하고 포켓몬 번호가 주어지면 포켓몬 이름을 답해야 한다. 따라서 포켓몬 이름과 그에 맞는 번호를 저장하는 해시 자료구조를 사용하고, 번호에 대한 포켓몬 이름을 답하기 위해 문자열 배열을 사용한다. 해시 자료구조로는 C++에선

학번과 수강신청 순서가 주어진다. 수강 신청을 2번 이상 한 경우 순서는 가장 최근에 수강 신청을 한 순서로 밀려난다. 최대 수강 가능 인원의 학번을 파악하기 위해 학번과 수강신청 순서를 해시 자료구조를 사용하여 저장한 후 이를 순서로 오름차순 정렬한 뒤 수강 가능 인

사이트 주소에 해당하는 비밀번호가 주어진다. 사이트 주소에 맞는 비밀번호를 출력하기 위해 해시 자료구조를 사용한다. C++에선 unordered_map, Java에선 HashMap을 사용한다.

BOJ 9375, 패션왕 신해빈테스트 크기는 100이며, 의상의 수 30, 의상의 종류는 1이상 20이하의 알파벳 소문자로 이루어져 있다. 의상의 종류가 의상의 수를 넘을 수 없으므로 입력 범위는 한정적이고, 구현에 초점을 맞춘다. 해빈이가 입을 수 있는 옷들의 조합을

입력의 크기가 10^4이라 대략 $$O(N^2)$$ 이하의 알고리즘을 사용한다. 단순히 스택 사용에 관한 문제다. STL, Collection 사용에 익숙해지자.

입력의 크기가 10^6이라 대략 O(N*logN)이하의 알고리즘을 사용한다. 정수가 "0"일 경우 가장 최근에 쓴 수를 지우고 계산하므로 stack 자료구조를 사용한다.

입력의 크기가 ... 이하의 알고리즘을 사용한다. 문제 이름처럼 스택 수열을 만들어야 한다. 가장 큰 숫자를 저장하는 이유는 이미 pop한 숫자를 중복해서 저장하지 않기 위함이다.

입력의 크기가 10^5이라 대략 O(N×logN) 이하의 알고리즘을 사용한다. 스택의 성질을 이용해서 효율성을 확 올려야 한다. 해당 문제가 스택으로 푸는지 아닌지도 알기 힘들겠지만, 일반적으로 입력을 받으면서 바로 처리하는 구조로 만들 수 있으면 스택을

입력의 크기가 10^4이라 대략 O(N^2) 이하의 알고리즘을 사용한다. 큐 자료구조를 주어진대로 잘 사용할 수 있는지 묻는 간단한 문제이다. java에서 queue 인터페이스로는 가장 늦게 삽입한 원소를 알 수 없다. 구체 클래스인 LinkedList를 직접 사용해도

입력의 크기가 500′000이라 대략 O(N×log2N) 이하의 알고리즘을 사용한다. 1번 카드가 제일 위에 N번 카드가 제일 아래인 상태로 카드가 놓여있고, 제일 위에 있는 카드를 제일 아래로 내리는 작업을 반복하므로 이를 효율적으로 할 수 있는 큐

BOJ 11728, 배열합치기입력의 크기가 10^6이라 대략 O(NlogN)이하의 알고리즘을 사용한다.최대 100만개의 크기를 가진 배열 a, b를 효율적으로 합쳐야 하므로 병합정렬의 핵심 아이디어인 두 배열의 요소를 하나씩 비교해서

BOJ 27551, 수 정렬하기 2 입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다.내장 sort함수를 이용할 수도 있으나, 머지소트를 구현해서 사용해본다. 평균적으로 quicksort 더 빠르지만, 직접 구현

회원 가입한 사람들의 나이와 이름이 입력으로 주어진다. 회원들은 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬해야 한다. 이 문제를 소개한 이유는 stable_sort라는 개념을 짚고 넘어가기 위해서다. stable_sort는 두 요

BOJ 11652, 카드입력의 크기가 10^5이라 대략 O(NlogN)이하의 알고리즘을 사용한다. 여러 장의 카드가 있을 때, 가장 많이 가지고 있는 카드 중 숫자가 가장 작은 카드를 골라야 한다. 해당 문제에 가장 쉽게 접근하는 방법

모든 원소를 거꾸로 뒤집고, 그 원소를 오름차순으로 정렬해야 한다. 단, 뒤집었을 때 숫자가 0으로 시작한다면 0을 지워주는 작업을 해야 한다. 0을 지워주는 작업을 하기 위해선 0이 아닌 문자가 시작하는 인덱스를 찾아야 하는데, Java에서는 이를 지원하는 메서드가

숫자의 빈도를 조사하여 빈도가 많은 대로 정렬을 하고, 빈도수가 같다면 먼저 나온 숫자를 기준으로 정렬한다. 특정 숫자에 대한 빈도를 알아야 하고, 그 숫자의 인덱스까지 알아야 한다. 해시 자료구조를 이용해 key(숫자)에 대한 value(인덱스와 빈도)를 구해내어 이

BOJ 1431, 시리얼 번호입력의 크기가 50이라 구현에 초점을 맞춘다.비교 함수를 작성하는 법을 물어보는 문제이다. A와 B의 길이가 다르다면 짧은 것이 먼저 오고, 길이가 같다면 각 자릿수의 합을 비교해서 작은 합이 먼저 온다. 만약 둘 다 같다면 사전 순

BOJ 11286, 절댓값 힙입력의 크기가 10^5이라 대략(NlogN) 이하의 알고리즘을 사용한다.N개의 수를 배열에 넣는데, 그 수가 0이라면 배열에서 절댓값이 제일 작은 수를 출력하고 배열에서 제거한다. 0이 아니라면 배열에

매우 많은 숫자 묶음이 주어지고, 매번 두 묶음씩 골라 합친다. 카드 개수만큼 비교하여 최소한의 비교 횟수를 구해야 한다. 해당 문제를 직관적으로 접근한 그리디 알고리즘을 적용했다. 매번 가장 작은 두 묶음을 합치면 비교 횟수가 최소가 된다. 만약 가장 작은 두 묶음을

얼핏 보면 이게 문제야? 라는 생각이 든다. 덜컥 최대 힙 구현하고 모든 값을 추가한 다음 N번째 큰 수를 구해야 하니 N-1번 POP 하면 되겠구나 라고 생각할 수 있다.('-') 이렇게 구현할 경우 $1500^2$ * 4byte 대략 1000MB가 넘어 메모리 초과

1번 cctv는 한 쪽 방향만 감시할 수 있고 2, 3번 cctv는 두 방향을 감시할 수 있다. cctv 번호마다 감시할 수 있는 영역이 다르고 90도씩 회전이 가능하게 이를 고려해서 구현해야 한다. 북, 서, 남, 동을 각 0, 1, 2, 3으로 두었을 때 가능한 감

혜윤이만의 스티커를 붙이는 방법이 있다. 먼저 스티커를 왼쪽 상단부터 오른쪽 하단까지 붙일 수 있는 곳을 찾아 붙인다. 붙일 수 없다면 90도 회전한 후 다시 왼쪽 상단부터 오른쪽 하단까지 찾아봐야 한다. 구현 문제답게 실수할 부분이 많다. 일단 스티커를 붙이는 곳

2048 게임과 규칙이 똑같다. 한 방향으로 밀어 같은 숫자라면 합쳐지게 된다. 같은 숫자가 아니고, 해당 방향에 숫자가 없다면 앞에서 부터 채워진다. 상, 하, 좌, 우 최대 5번 밀어 정사각형에서 최댓값을 찾는 문제이다. 구현할 때 실수를 덜기 위해서 아래에서 위로

입력의 크기가 작아 구현에 초점을 맞춘다. 집과 치킨집이 주어진다. 주어진 치킨집에서 k개를 골랐을 때 모든 집과 치킨집 사이 거리의 최솟값을 구해야 한다. 크게 두 부분으로 나눌 수 있다. 첫째로 전체 치킨집 n개에서 k개를 골랐을 때 가능한 모든 경우의

뿌요뿌요 게임을 구현하는 문제다. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 한꺼번에 없어지고 1연쇄가 된다. 뿌요들이 없어지고 나서 그 위에 뿌요가 있다면 아래로 떨어지고 또 4개 이상 연결되어 있으면 한 번에 없어지면서 2연쇄가 된다. 이렇게 반복할 때

BOJ 14891, 톱니바퀴 입력의 크기가 10^2이라 구현에 초점을 맞춘다.8개의 톱니를 가지고 있는 톱니바퀴 4개가 있고, 각각의 톱니는 N(0) 또는 S(1)극을 향하고 있다. 특정 톱니바퀴를 시계방향이나 반시계 방향으로 회전시켰을 때 양옆에 있는 톱니바퀴와

BOJ 14499, 주사위 굴리기 입력의 크기가 10^3이라 구현에 초점을 맞춘다.매번 규칙에 맞게 주사위를 이동시키며, 주사위 윗면에 있는 값을 출력하도록 한다. 주사위의 전개도는 아래와 같다. 윗면이 1이고, 동쪽을 바라보는 방향이 3이며, 주사위 바닥면은 6

BOJ 13335, 트럭 입력의 크기가 10^3이라 구현에 초점을 맞춘다. 다리를 n개의 트럭이 지날 때, 다리의 하중을 초과하지 않으면서 가장 빨리 다리를 건널 수 있는 시간을 구해야 하는 문제이다. 해당 트럭이 다리에 오를 수 있는지 판단하기 위해 bridge 배

BOJ 16985, Maaaaaaaaaze 5*5 크기의 판이 5개 주어진다. 구현에 초점을 맞춘다. 미로에서 탈출해야 한다. 판 5개를 자유롭게 쌓을 수 있으며, 판을 시계 방향 또는 반시계 방향으로 회전할 수 있다. 가장 빠르게 탈출해야 하는 경로를 구하기 위해선

BOJ 14503, 로봇청소기 입력의 크기가 50^2이라 구현에 초점을 맞춘다.로봇 청소기 위치와 방향을 담을 큐를 선언하고, 하나씩 꺼내와서 처리하는 방식으로 구현하였다. 청소기는 현재 칸의 주변 4칸 중 청소되지 않은 칸이 없는 경우와 있는 경우로 나눠서 작동한

BOJ 3190, 뱀 입력의 크기가 100^2 이므로 구현에 초점을 맞춘다.뱀 게임을 만드는 문제이다. 뱀이 기어다니면서 사과를 먹으면 길이가 늘어나고 벽 또는 자기 자신과 부딪히면 게임이 끝난다. 추가로 방향 변한 횟수가 주어져 시간이 되면 뱀의 방향을 변환시켜

BOJ 14500, 테트로미트 입력의 크기가 500이라 구현에 초점을 맞춘다.쉽게 말해 정사각형 4개를 이어 붙인 도형에 해당하는 최고 점수를 구해야 한다. 이 도형의 모양은 5가지가 있으며 회전과 대칭이 가능하다.5개 모형을 시계 방향으로 회전하면서 대칭할 경우와

BOJ 13460, 구슬 탈출 2 입력의 크기가 10^2이라 구현에 초점을 맞춘다.빨간 구슬과 파란 구슬이 있는 보드판에서 상, 하, 좌, 우 방향으로 기울여 빨간 구슬을 구멍에 빠뜨리는 게임이다. 파란 구슬이 구멍에 빠지면 안 되고, 빨간 구슬과 파란 구슬이 동시

입력의 크기가 8^2이라 구현에 초점을 맞춘다. 연구소에 바이러스가 유출되었고, 바이러스를 막기 위해 최대 벽을 3개 설치할 수 있다. 바이러스가 퍼질 수 없게 벽을 세워 안전 영역 크기의 최댓값을 구해야 한다. 8 * 8 지도에 최소 바이러스가 2개 있다면, 최대 6

BOJ 14888, 연산자 끼워넣기 입력의 크기가 10이라 구현에 초점을 맞춘다.n개의 수가 주어지고, 사칙연산 연산자가 n-1개 주어진다. 연산자를 끼워 넣었을 때 만들 수 있는 최댓값과 최솟값을 출력하는 문제이다.가능한 연산자 순서를 구하기 위한 순열을 생성한다

BOJ 입력의 크기가 20이므로 구현에 초점을 맞춘다.최대 20명이 모이고 반으로 나누어 팀을 정한다. 팀 간 능력치 합의 최소 차이를 구하는 문제이다.먼저 N명이 모였을 때 각 팀원은 N / 2 명이 되며, 팀원을 뽑는 경우의 수는 N 명 중에 N / 2를 뽑는

BOJ 14890, 경사로 입력의 크기가 100이라 구현에 초점을 맞춘다.지도에서 행과 열을 기준으로 지나갈 수 있는 길을 파악해야 한다. 만약 길 높낮이가 다르다면 경사로를 설치할 수 있다. 경사로는 일정한 길이가 있기에 문제에서 주어진 만큼 평평한 땅이 존재해야

BOJ 입력의 크기가 10, 30이라 구현에 초점을 맞춘다.사다리 게임으로 세로선 개수와 세로선마다 놓을 수 있는 가로선 개수가 주어진다. n번에서 출발하면 n번으로 도착할 수 있게 최대 3개의 사다리를 설치할 수 있다. 예를 들어 세로선이 6개 있고 1번에서 출발

BOJ 15685, 드래곤 커브 입력의 크기가 100, 100, 2^{10}(세대)이라 구현에 초점을 맞춘다.드래곤 커브에 속하는 1 x 1 정사각형 개수를 구하는 문제이다. 드래곤 커브의 규칙성을 찾아내는 것이 핵심이다.세대가 업할수록 기존 세대를 시계방향으로 9

BOJ 입력의 크기가 10^8이라 대략 O(n) 이하의 알고리즘을 사용한다.동전의 최대한 적게 사용하여 K를 만들어야 한다. 가장 큰 동전부터 사용하면 동전을 가장 적게 사용할 수 있다는 명제로부터 출발한다. 가장 큰 동전을 사용하지 않고 동전을 가장 적게 사용

BOJ 1931, 회의실 배정 입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다.한 개의 회의실이 있을 때 n개의 회의에 대해 겹치지 않게 사용할 수 있는 최대 회의의 개수를 구해야 한다. 회의의 시작 시각과 끝나는

BOJ 2217, 로프 입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다. 로프마다 물체를 들 수 있는 중량이 주어진다. 로프를 병렬로 연결하면 각각의 로프에 전체 중량/로프의 개수만큼 중량이 걸리게 된다. 즉 가장 중

BOJ 1026, 보물 입력의 크기가 50이라 구현에 초점을 맞춘다.배열 A와 B가 있을 때 b를 재배열하지 않고 다음 합계의 최솟값을 구해야 한다. S = A0 × B0 + ... + AN-1 × BN-1 두 수의 곱셈의 합이 최솟값이 되려면 가장 큰 수는 가장

BOJ 11399, ATM 입력의 크기가 10^3으로 구현에 초점을 맞춘다.ATM 앞에 N명이 줄 서 있을 때, 모든 사람이 기다리는 최소 시간 합을 구해야 한다. 모든 사람이 기다리는 최소 시간 합을 구하기 위해선 가장 빨리 일을 처리하는 사람부터 일을 보면 된다

BOJ 2457, 공주님의 정원 입력의 크기가 10^5이라 대략 O(NogN) 이하의 알고리즘을 사용한다.꽃들의 피는 날과 지는 날이 주어질 때, 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 하는 꽃의 최소 개수를

BOJ 1541, 잃어버린 괄호 입력의 크기가 50이라 구현에 초점을 맞춘다.양수, +, -로 이루어진 식이 주어진다. 괄호를 적절히 사용해서 식을 최솟값으로 만들려고 할 때 해당 최솟값을 구해야 한다.음수 연산자가 나오면 괄호를 이용해 뒤에 +연산자가 있든 간에

BOJ 11501, 주식 입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다. 날 별로 주식 가격이 주어지고 하루에 주식을 한 주를 사거나 모두 팔 수 있다. 최대 이익을 구해야 한다. 단순하게 생각하면 가격이 하락한다면

BOJ 1744, 수 묶기 입력의 크기가 10^6이라 대략 O(NlogN) 이하의 알고리즘을 사용한다.수열이 주어질 때 모든 수열을 더한 값의 최댓값을 구해야 한다. 수열에서 임의의 두 수를 묶을 수 있는데 묶인 수는 서로 더하는 게 아니라

피보나치수열로 n == 0일 때 0을 호출하고 n == 1일 때, 1을 호출한다면 fibonacci(n)을 호출했을 때 0과 1의 호출된 횟수를 각각 구해야 한다. fibo(n) 함수를 한 번 호출하면 내부에서 fibo(n - 2), f

BOJ 1932, 정수 삼각형 입력의 크기가 500이라 대략 O(N^2) 이하의 알고리즘을 사용한다.아래 그림을 볼 때, 맨 윗층 7부터 시작해서 아래에 있는 수 중 하나를 선택해서 내려갈 때 선택된 수의 합을 최대가 되는 경로를 구해야 한다. 단, 아래층에 있

입력의 크기가 10^3이라 구현에 초점을 맞춘다. 2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수를 구해야 한다. 2xn 타일링 문제를 풀어봤다면 dp문제임을 쉽게 알아차릴 수 있지만 처음 보면 이것을 dp로

BOJ 1912, 연속합 입력의 크기가 10^5이라 대략 O(NlogN) 이하의 알고리즘을 사용한다.n개의 정수로 이루어진 수열이 주어진다. 연속된 몇 개의 수를 선택해서 가장 큰 합을 구해야 한다. 최소 1개 이상 선택한다.먼저 가장 큰 합

입력의 크기가 10^3이라 구현에 초점을 맞춘다. 수열 A가 주어질 때 증가하는 부분 수열 중 합이 가장 큰 것을 구해야 한다. 핵심 아이디어는 수열에 각 위치에서 끝나는 증가 부분 수열의 합을 구한 뒤 원소 간의 비교를 통해 작은 부분 수열의 합을 큰 곳에

BOJ 9461, 파도반 수열 입력의 크기가 100으로 구현에 초점을 맞춘다.정삼각형이 나선 모양으로 추가될 때 n번째 삼각형의 한 변의 길이를 구해야 한다.일정한 규칙으로 삼각형이 만들어지므로 n번째 삼각형의 길이를 알기 위해 테이블을 만들고 초깃값을 넣어 규칙을

BOJ 15486, 퇴사 2 입력의 크기가 10^$이라 대략 O(NogN) 이하의 알고리즘을 사용한다.N + 1일 째 되는 날 퇴사를 하는데, 남은 N일 동안 상담을 하고 얻을 수 있는 최대 수익을 구해야 한다.문제 지문 설명만으론 N +