알고리즘::백준

LIS(최장 증가 부분수열) 문제 : https://www.acmicpc.net/problem/14003 LIS 문제는 정말 유명하며 동시에 많은 변조 문제들이 있다. LIS 문제의 핵심에 대해 파악해보도록 하자. 문제 접근 방법

https://www.acmicpc.net/problem/1463정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1) X가 3으로 나누어 떨어지면, 3으로 나눈다.2) X가 2로 나누어 떨어지면, 2로 나눈다.3) 1을 뺀다.정수 N이 주어졌을 때

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.n이 주어졌을 때, n번째 피보나치 수를

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.무작정 손으로 계산하기 시작하면 끝도없이 말리는 문제다. 6까지는 손으로 계산할 수 있지만 그렇게 한다면 1, 2, 3, 4, 5, 6 각 숫자 사이의 규칙성을 찾기

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 가로의 길이가 n이므로 놓는 타일이 무엇이냐에 따라 다음 작은 문제는 n-1또는 n-2일 것이다. 임의의 숫자 n에 대해 경우의 수를 기록해둔다면 중복 연산을 피할 수 있

로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법

민규가 구매하려고 하는 카드의 개수 N과 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오N개의 카드를 구매하기 위해 지불해야하는 금액의 최댓값을 구하는 문제이므로 전형적인 DP 문제임을 알

민규가 구매하려고 하는 카드의 개수 N과 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하시오.https://velog.io/@embeddedjune/백준-알고리즘-DP-11052-카드-구매하기 문제에서 최

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.1+2+11+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를

45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 성질 1) 이친수는 0으로 시작하지 않는다. 성질 2) 이친수에서는 1이 두 번 연

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 성질 1) 이친수는 0으로 시작하지 않는다.성질 2) 이친수에서는 1이 두 번 연속으로

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.Bruteforce방법이 자연스럽게 떠오르고, 만들어지는 조합의 합을 어딘가에 기록해둔

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의 머리가

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.밑면

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.시간제한은 2초이고 정수의 개수 N은 1부터 20까지로 적은 범위가 주어졌음을 눈치챈다.간단히 a, b, c 3개

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-1182-부분수

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.https://velog.io/@embeddedjune/알고리즘-백준-DP-1208-부분수열의-합2 보다 쉬운 문제다. 과정은 위 링크에서 풀

보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.2048 게임의 구현이 대략 어떤식으로 이뤄지는지 알 수 있었던 재밌는 문제였다. 학교 심화프로그래밍 시간에 어영부영 2048 프로젝

보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 10번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-12100-2048easy 문제의

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.N을 제곱수들의 합으로 표현했을 때, 마지막으로 오는 수를 i라고 가정하자. 이때 i의 범위는 $0 \\leq i \\leq \\sqrt n$ 이다.점화식 $D(n

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.문제에 주어진 변수와 범위를 생각해보자K :

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.개인적으로 한참동안 고민했던 어려운 문제였다. 명확한 풀이법이 생각나지 않았다.스택을 사용한다.) 닫는 괄호문자를 만나면 이 문자가 레이저를 의

전형적인 DFS의 그래프 세그먼트 개수 구하기 문제다.모든 정점에 대해 DFS를 수행한 뒤 DFS가 종료됨은 각 세그먼트에 대해 탐색이 끝났음을 의미하므로 카운팅해주면 전체 섬의 개수를 구할 수 있다.vector<bool> 사용을 지양하고 bitset또는 일반 b

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 키의 합이 100이 되는 일곱 난쟁이를 찾는 프로그램을 작성하시오. 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.9명의 난쟁이에 대해 7명을 뽑아서 키의 합을 구하고 합이 100인

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때,

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.1234567891011121314151617181920212223...이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.어렵지 않은 문제다. 이

문제 > 각 날짜에는 위와같이 상담 소요일과 수익이 나타난다. 주어진 상황에서 얻을 수 있는 최대 수익을 나타내시오. 문제접근 가장 기본적인 형태의 bruteforce 문제인데 스스로의 힘으로 풀지 못해서 너무 아쉽고 분했다...ㅠ 가장 기본적인 형태의 brute

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을

A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.$A - B-C-D$ 관계를 만족하는 간선이 그래프에 존재하는지 찾는 간단한 DFS 문제다.임의의 시작점을 정하고 DFS를 수

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오DFS와 BFS의 개념을 배운 뒤 코드 패턴을 연습해볼 수 있는 기본 문제다. 인접행렬보다는 인접리스트를 사용하는 것에 익숙해지는 것이 효율적이다.DFS와 BFS는 어느정도 패턴이 존재

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.https://velog.io/@embeddedjune/알고리즘-백준-DFS-11724-연결-요소의-개수 이 문제와 똑같은 문제다. 패턴과 형태에 익숙해지자.형태에

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.주어진 그래프가 이분 그래프인지 아닌지 여부를 판별하는 문제다.이분 그래프를 판단하는 문제는 DFS 문제다.임의의 시작점을 BLUE표시한 뒤 이어지는 다음 정점은 RED로

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.사이클의 존재 여부를 확인하는 문제다.오일러 사이클(트레일) 문제인줄 알고 겁먹었지만, DFS만으로 풀 수 있었다.임의의 시작점으로부터 DFS 순회를 시작해서 다시 출발지점으로 돌아올 수 있다면 사이클이

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌

https://www.acmicpc.net/problem/16940같은 BFS를 수행하더라도, 그래프 인접리스트에 정점이 어떤 순서로 들어가있냐에 따라 순회 순서가 달라질 수 있다.그러나 모든 순회 순서를 고려할 수는 없다.그러므로 주어진 BFS 순회 결과로부

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.두 가지 접근으로 문제를 해결할 수 있다.각 섬에서 다른 섬 까지의 모든 거리를 계산하고 최단거리를 구한다.직관적이고 좋은 방법이지만, 모든 점에서부터 BFS를 수행해야 하므로 너무 시

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.구하고자 하는 것이 시간이 아니라 벽 개수 라는 점을 염두하자.그러므로 정점과 간선의 관계는 이렇게 나타낼 수 있다.간선의 가중치가 2개

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 영선이가 S개의 이모티콘을 화

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 임의의 한 점에서

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼

N x N 크기의 시험관이 있다. 시험관은 1 x 1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.주어진 N-1개의 연산자를 이용해서 결과가 최대인 경우와 최소인 경우의 결과값을 구하면 된다.완전탐색(Bruteforce)으로 풀 수 있는 문

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.각 선

https://www.acmicpc.net/problem/16234N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 Ar명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다.

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에,

문제 링크맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택

문제 링크상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.이미 본 velog에서 같은 문제를 bruteforce로 푸는 방법을 다뤘다.https://velog.io/@embeddedjune/알고리즘-백준-Brutefor

문제 링크N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비

문제 문제링크 >올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신

문제 https://www.acmicpc.net/problem/2887 > 행성은 3차원 좌표 위의 한 점으로 주어지며 두 행성을 연결하는 터널의 비용은 $min(|xA-xB|, |yA-yB|, |zA-zB|)$이다. 터널을 $N-1$개 건설해서 모든 행성이 서로

에라토스테네스 + bitmask (비트마스크) 방법시간복잡도: $O(ElogV)$모든 간선의 가중치가 양수일 때만 사용.음수 간선 가중치가 있을 때 사용 가능.시간 복잡도: $O(VE)$ 로 다익스트라보다 느리다.음수 간선 합 사이클의 존재 여부 판단 가능. 존재할 때

문제 링크1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.1234567891011121314151617181920212223...이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.N의

문제링크자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열<algorithm>헤더의 next_permutation() 함수를 쓰면 간단하게 풀 수 있는

문제링크자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.https://velog.io/@embeddedjune/알

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열같은 수를 여러 번 골라도 된다.숫자에 중복을 허용한 경우에는 어떻게 문제를 풀어야 할까?중복을 허용했기

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤

문제 링크상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공

문제 링크오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수

문제링크1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 단, 연속해서 3잔 마실 수 없다.n이

문제 문제링크 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12,

문제 문제링크 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

문제 링크3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.2xN 타일링의 심화버전, 그러나 접근 방법은 다르지 않다.길이가 N일 때 문제를 푸는 방법과 N-1일 때 푸는 방법이 동일하므로 최적 부분 문제 구조를 만족한다.부분 문제들이 반복

문제 링크두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.삽입: A의 한 위치에 문자 하나를 삽입한다.삭제: A의 문자 하나를 삭제한다.교체

문제 링크세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.첫 번째 단어 : cat두

문제링크 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이

문제링크축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N

문제링크암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로

문제링크두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => &l

문제링크1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.주어지는 수열의 다음 순열을 구하면 되는 간단한 문제다.이 문제의 존재의의는 <algorithm> 헤더의 next_permutation()을 쓰라

문제링크문제가 상당히 길다. 장문의 문제는 수험생에게 혼란을 주기 위해서다.이 문제는 마지막 문단을 제외한 모든 정보가 쓸데없다.규현이가 쓴 N개의 수는 A\[]배열로 표현한다.규현이는 -10부터 10까지의 정수만 알고있다.S\[i]\[j]는 A\[]의 i부터 j까지의

이 문제에 대한 상세 설명은 알고리즘 :: 백준 :: DFS :: 1707:: 이분 그래프 (velog.io)에 있습니다. 이번에는 같은 문제를 조금 더 효율적으로 풀어보겠습니다.문제 조건에는 나와있지 않지만, 본 문제의 이분그래프는 무방향 그래프입니다.이분그래프의 특

이 문제는 전형적인 쉬운 DFS 또는 BFS 문제 유형입니다.조금 더 적나라하게 말하자면, DFS 쪽에 조금 더 친숙한 유형입니다.(DFS는 재귀(스택)를 이용하다보니 코드 줄 수가 4~6줄이면 됩니다.)main()같은 외부 함수에서 for()문을 돌며 2차원 배열의

가장 전형적인 BFS 문제입니다.이 문제를 통해 BFS에 익숙해지실 수 있으며, 더 나아가 다익스트라 알고리즘에 대해서 배우게 됩니다.임의의 점으로부터 상, 하, 좌, 우를 검사하면서 진행할 수 있는지, 방문한 적이 없는지를 검사하며 queue에 다음에 이동할 정점을

가장 전형적인 BFS 문제인 2178번: 미로 탐색 (acmicpc.net)와 똑같은 문제입니다.다만, 갈 수 있는 방향이 4방향에서 8방향으로 늘었습니다.한 번에 갈 수 있는 칸의 개수가 특정돼있지 않습니다.또한, 임의의 칸이 갈 수 있는 여부를 나타내지 않습니다.따

Greedy유형으로 오해할 수 있는 문제입니다.임의의 점을 향할 때 반드시 순간이동을 사용하는 것이 유리하지는 않습니다.예를 들어, 5에서 17로 갈 때, 5 -> 10 -> 20 -> 19 -> 18 -> 17 보다5 -> 10 -> 9 -> 18 -> 17이 1초

알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.여러분은 이전 문제에서 BFS를 이용해 최단 시간으로 동생을 찾는 방법을 구현하셨습니다. 이번에는 동생을 찾으러 가는 과정을 구하는 문제입니다.외부에 배열 track을 만

알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.저번 문제와 차이점은 단 하나입니다. 순간이동이 1초 → 0초로 바뀌었습니다.이 문제는 1697번 풀이에서 순간이동에 대한 코드에서 push()할 때 시간을 더해주지 않는

대표적인 BFS 유형인 미로찾기 유형에서 벽을 부술 수 있는 조건이 추가된 문제입니다.이 문제에는 함정이 있습니다. 구하고자 하는 것이 최소거리/최단거리가 아닌 부순 벽의 최소개수 입니다.그렇다면 생각해봅시다. 임의의 점에서 인접한 다른 점을 갈 때 벽을 부수는 경우와

우리가 취할 수 있는 액션은 세 가지입니다.화면의 이모티콘 개수는 그대로, 클립보드 개수는 화면의 이모티콘 개수로 변경.화면의 이모티콘 개수는 기존 + 클립보드 개수로 변경, 클립보드 개수는 그대로.화면의 이모티콘 개수는 기존 - 1로 변경, 클립보드 개수는 그대로.모

문제에 주어진 조건들을 그대로 코드로 구현하는 전형적인 '시뮬레이션' 유형입니다.문제를 편하게 설명하기 위해 배열을 $N \\times M$ 형태의 배열 a라 가정하겠습니다.연산은 (1, 2) → (3, 4) → (5, 6) 순으로 구현이 어렵습니다.최대한 RangeE

알고리즘 :: 백준 :: 시뮬레이션 :: 16935 :: 배열 돌리기3 (velog.io) 문제와 이름은 동일하지만 배열 회전 방법이 완전히 다른 문제입니다.회전 방식은 다음과 같습니다.i번째 그룹은 a\[i]\[i] 요소로 시작해서 시계방향으로 한 바퀴 돌 때 포함되

알고리즘 :: 백준 :: 시뮬레이션 :: 16926 :: 배열 돌리기1 (velog.io) 문제와 동일한 문제입니다.연산 회수가 $10^9$로 증가했습니다.하지만, 저희는 이전 문제에서 각 그룹의 원소 개수로 모듈라한 횟수만큼 회전하는 방식을 채택했으므로 연산 회수가

시뮬레이션 유형의 골드 이상 난도를 가진 문제는 공통점이 있습니다.문제가 길어서 요구하는 바를 찾기 어려워집니다.문제에서 요구하는 조건이 많아 구현이 힘들어집니다.TLE를 방지하기 위한 방법도 고려해야합니다.시뮬레이션 유형은 반드시 문제를 읽으면서 줄치는 것 뿐만 아니

글과 그림이 많은 전형적인 골드급 시뮬레이션 유형 문제입니다.문제 조건을 정리하면 비교적 짧습니다.i번째 톱니바퀴로부터 왼쪽 부분, 오른쪽 부분을 검사.맞닿은 톱니바퀴가 반대극일 때 반대방향으로 회전. 같다면 무반응.톱니는 12시 방향부터 표현 → gear\[i]\[8

간단한 문제입니다. 조건을 정리해봅시다.이동하는 경우왼쪽으로 무조건 회전합니다.진행가능하다면 진행합니다.이동 불가능한 경우네 방향 모두 청소되거나 벽인 경우 후진합니다.후진조차 불가능한 경우 작동을 멈춥니다.위에 파란색으로 표시한 조건을 꼭 반영하셔야 합니다.이 문제에

정말 어려웠던 문제였습니다. 이 문제는 두 가지가 어렵습니다.문제 이해하는 것이 어렵습니다.PS 경험이 적은경우, 시계 방향이라는 표현이 애매모호합니다.글과 그림을 봐도 어떻게 이런 그림이 나오는지 이해하기 힘듭니다. 드래곤 커브를 어떻게 구현할지 생각하기 어렵습니다.

겉넓이는 도형을 상, 하, 좌, 우, 위, 아래 6방향으로 바라봤을 때 단면적의 넓이를 더하면 쉽게 구할 수 있습니다.하지만, 위 방법으로는 답을 구할 수 없는 경우가 있습니다.첫 번째 그림은 문제의 예제와 똑같이 쌓기나무를 쌓았을 때의 모습입니다.두 번째 그림은 쌓기

정말 까다로운 문제입니다. 만일 정육면체 전개도 종류가 11가지라는 사실을 몰랐다면 이 문제를 어떻게 풀 수 있을지 모르겠습니다.정육면체의 전개도는 몇개일까?중앙 파란색 전개도를 제외한 나머지 10가지 전개도는 3X4 배열로 나타낼 수 있습니다.(중앙 파란색 전개도는

스도쿠는 $9 \\times 9$ 배열, 즉 81칸으로 이뤄져있습니다.0번째 칸부터 재귀를 돌면서 0이 들어있는 칸에 대해서는 임의의 숫자를 넣습니다.숫자를 넣을 때는 가로와 세로 그리고 포함된 그룹을 검사해서 적합한 숫자를 찾습니다.1~9 까지 수는 각 행과 열 그리

이전에 풀이했던 '스도쿠'문제 알고리즘 :: 백준 :: Bruteforce :: 2580 :: 스도쿠 (velog.io) 의 연장선입니다.기본 골자는 거의 같지만, 이번에는 가로 2칸 또는 세로 2칸으로 도미노를 놓아야 한다는 점이 다릅니다.이번에는 저번 풀이와는 다르

Queen의 공격 범위는 가로, 세로, 대각선입니다.각 행마다 queen은 단 하나만 들어갈 수 있습니다.각 열마다 queen은 단 하나만 들어갈 수 있습니다.모든 행마다 queen을 넣었을 때 대각선을 고려해줘야 합니다.외부 배열 row\[N], leftDig\[2

저번에 배웠던 교훈에 따라 효율성 신경쓰지말고 먼저 정답을 만들기에 집중했습니다.(AC는 받았지만 속도 느리다는 점 미리 밑밥 깔고 갑니다...ㅎㅎ)문제를 요약하면, ''단어 N개 중 알파벳 K개로 표현할 수 있는 단어의 최대 개수를 구하세요'' 입니다.문제 과정을 요

상, 하, 좌, 우로 구슬을 굴려서 빨간 구슬만 구멍으로 내보내는 최소 회수를 구하는 문제입니다.정말정말 까다로운 문제였습니다. 결국 시간 내에 풀지 못했습니다. 배울 점이 참 많은 문제입니다.주요 조건은 다음과 같습니다.공은 동시에 움직입니다.시뮬레이션 또는 brut

이번 문제의 유형은 시뮬레이션 및 구현입니다.문제를 읽고 복잡한 조건을 잘 정리한 뒤 빠짐없이 구현하는 능력이 필요합니다.stack 자료구조를 사용한다.이항연산은 pop()을 2회 수행하고 계산결과를 push()한다.나눗셈의 경우 다음과 같이 계산한다.피연산자는 모두

이번 문제의 유형은 시뮬레이션 및 구현입니다.문제를 읽고 복잡한 조건을 잘 정리한 뒤 빠짐없이 구현하는 능력이 필요합니다.물이 고슴도치보다 먼저 이동해야합니다.물은 돌과 소굴을 지나갈 수 없습니다.고슴도치는 돌과 물을 지나갈 수 없습니다.처음에 물은 여러 개 있을 수

순열/조합을 이용한 대표적인 bruteforce 문제입니다.알파벳은 26개, 사용하는 필수 알파벳은 5개, 21개 알파벳 중 K-5개 알파벳을 고르므로 최대 경우의 수는 ${21}C{10} = 352,716$입니다.$단어의 개수 \\leq 50$ , $8 \\leq 단

문제를 잘 읽고 조건을 빠짐없이 구현하는 구현, 시뮬레이션 문제입니다.처음 모든 사진틀 비어있다.빈 사진틀 없는 경우, 게시된 후보들 중 추천수가 가장 낮고 게시된 지 오래된 순으로 교체한다.학생은 총 100명있다.답은 학생 번호의 오름차순으로 출력한다.문제 조건에 따

시뮬레이션 문제입니다.동전은 가장 왼족 위 (0, 0)에 있다.동전이 있는 칸의 숫자만큼 상, 하, 좌, 우 중 한 방향으로 이동한다.(이때, 중간에 지나치는 구멍은 무시한다.)구멍에 빠지거나 보드 바깥으로 나간다면 게임은 종료한다.무한번 움직일 수 있다면 -1을 출력

시뮬레이션 문제입니다.이 문제는 간단하지만, 숨겨진 예외조건을 찾기 까다롭습니다.연산을 K번 할 수 없는 경우 -1을 출력한다는 말을 이해하기 어렵기 때문입니다.N = 1,000,000인 경우, 연산을 수행할 수 없습니다.N = 1~9 또는 N = 10, 20, 30,

모든 경우의 수를 구한 뒤 최적해를 구하는 bruteforce 문제입니다. 이 문제는 두 가지 방법으로 해결할 수 있습니다.Bruteforce 방법: 알파벳은 최대 10개이므로 $10! = 1,034,768$​을 모두 구한 뒤 최적해를 찾습니다.Greedy 방법: 높은

모든 경우의 수를 구한 뒤 최적해를 도출하는 bruteforce 문제입니다.집의 개수는 최대 100개, 치킨집의 개수는 최대 13개다.모든 집을 기준으로 모든 치킨집에 대한 치킨거리 정보를 기록하는 2차원 테이블을 만듭니다.치킨집 M개를 선택하는 조합 을 구합니다.선택