[C++] 백준

백준 11054 알고리즘 분류 : dynamic programming (동적 계획법) 백준 11053번, LIS(Longest Increasing Subsequence)를 구하는 문제의 응용이다. 11053번과의 차이점은 LIS를 구하는 과정을, 두 번 거쳐야 한다

백준 1912알고리즘 분류 : dynamic programming (동적 계획법)정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중, 가장 큰 합을 구하는 문제다. 먼저, 입력받은 수열을 저장하는 배열 arr과 각 위치에서의 최대 합을

백준 1541알고리즘 분류 : greedy algorithm (그리디 알고리즘)괄호가 없는 수식에 괄호를 적절히 쳐, 수식의 값을 최소로 만드는 문제다.이 문제를 해결하기 위해서는, 어떤 경우에 값이 최소가 되는지에 대한 파악이 필요하다. 55-50+40 -> 55-(

백준 11286 알고리즘 분류 : priority queue (우선순위 큐) 입력받은 정수(0이 아닌)의 절댓값을 오름차순 정렬하고, 0을 입력받을 때마다 절댓값이 가장 작은 값을 출력하면 되는 문제다. (절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를

백준 1992알고리즘 분류 : divide and conquer (분할 정복)쿼드트리의 방법을 이용하여 4개의 영역을 압축한 결과를, 차례대로 괄호 안에 묶어서 표현하는 문제다. 재귀를 통해 해결한다.살펴보는 영역 안에 check와 다른 문자가 존재하는 경우, 다음과

백준 1655알고리즘 분류 : priority queue (우선순위 큐)정수를 하나씩 입력받을 때마다, 그때의 중간값을 각각 출력하는 문제다. (만약 입력받은 수의 개수가 짝수개라면, 중간에 있는 두 수 중에서 작은 수를 출력한다.)두 개의 우선순위 큐를 이용하여 문제

백준 10830알고리즘 분류 : divide and conquer (분할 정복)크기가 N\*N인 행렬 A가 주어졌을 때, A의 B제곱을 구하는 문제다.B가 1이 될 때까지, 2로 반복해서 나누어 행렬 ans를 구한다.B%2=1인 경우, solve(ans,A)B%2=0인

백준 25682 알고리즘 분류 : prefix sum (누적 합) > 🌲 문제 요약 입력 받은 임의의 MxN 크기의 보드를 KxK 크기의 보드로 잘라낸 뒤 색칠을 통해 하나의 체스판으로 만드려 한다. 이때 다시 칠해야 하는 정사각형의 최소 개수는 몇 개일까?

백준 2979트럭의 수에 따른 각각의 주차 비용 A, B, C가 주어지고, 트럭이 주차장에 주차된 시간이 주어졌을 때, 총 주차 요금을 구하는 문제.주차된 트럭의 수를 시간에 따라 저장한 배열 arr를 선언하여, 트럭 세 대의 주차 정보를 저장한 뒤, arr를 순회하며

백준 9996알파벳 소문자와 별표 한 개로 이루어진 패턴이 주어졌을 때, 입력받은 각각의 파일 이름과 패턴의 일치 여부를 확인하는 문제.패턴 pat의 구성 정보를 확인하고, pos에 별표 위치를 저장한 뒤, substr을 이용해 별표 이전의 문자열과 이후의 문자열을 p

백준 1213입력받은 영어 이름을 팰린드롬으로 바꾸는 문제.배열 arr에 영어 이름의 정보를 담은 뒤, 문자열 ret의 앞과 뒤에 arr에 담긴 각각의 알파벳을 사전 역순으로 입력받은 개수만큼 추가한다. mid가 존재할 시, 반복문을 마친 이후 ret의 가운데 위치에

백준 1629A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제자칫 높아질 수 있는 시간 및 공간 복잡도를 해결하기 위해 재귀 함수 및 모듈로 연산을 활용한다.재귀 함수 go를 통해, B의 값을 반으로 나누어가며 A의 B제곱을 분할 계산한다. 이때 과정 중간 중간,

백준 43752와 5로 나누어떨어지지 않는 정수 n이 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 출력하는 문제.1로만 이루어진 정수의 자릿수를 하나씩 늘려가며, 그때마다 정수가 n으로 나누어떨어지는지 확인한다. 자릿수를 늘리

백준 2178NxM 크기의 배열로 표현되는 미로가 주어질 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때까지 지나야 하는 칸 수의 최소를 구하는 문제.같은 가중치를 가진 그래프에서 최단거리 구하는 문제이므로, BFS을 이용하여 해결한다.상하좌우 방향으로

백준 1012인접한 다른 배추로 이동이 가능한 배추흰지렁이를 이용하여 배추밭을 보호하려고 할 때, 필요한 최소의 배추흰지렁이의 마리 수를 출력하는 문제.연결된 컴포넌트를 찾는 문제이며, dfs를 이용하여 해결한다.상하좌우 방향으로 arr를 탐색하여, 만일 arr\[ny

백준 2828스크린의 위에서 떨어지는 사과 여러 개를 바구니로 담으려고 할 때, 바구니의 최소 이동거리를 구하는 문제.바구니의 왼쪽과 오른쪽을 가리키는 변수 l과 r을 각각 선언하여, 사과가 떨어지는 위치가 l과 r의 사이인지 확인한다.그렇지 않다면, 바구니의 위치가

백준 2910 🌲 문제 요약 메시지에 등장하는 숫자를 빈도 순서대로 정렬하는 문제. 🌲 문제 풀이 맵 mp에 입력받은 숫자 tmp의 빈도 정보를 저장한다. 이때, 어떤 숫자가 처음 등장한 시점의 정보를 저장하기 위해, if (!mpfirst[tmp]) 경우에

백준 4659높은 품질을 가진 비밀번호의 조건이 주어질 때, 입력받은 패스워드의 품질을 평가하는 문제.입력받은 각각의 s를 한 글자씩 검사한다. 만약 s\[i]의 모음 자음 여부를 판별하는 check 함수가 true를 반환한다면, 연속된 모음의 개수를 가리키는 변수 a

백준 2852농구 경기에서 골을 넣은 팀과 그때의 시간이 주어질 때, 1번 팀과 2번 팀이 이기고 있던 시간을 각각 출력하는 문제.만약 득점을 한 팀이 현재 이기고 있는 팀이라면, 그 팀의 시간에 입력받은 시간을 반영시켜 더한다. 마지막에는 리드 팀에게 종료 시간을 반

백준 14502연구소의 지도가 주어졌을 때, 바이러스가 퍼질 수 없는 안전 영역 크기의 최댓값을 구하는 문제.세 개의 벽을 세울 수 있는 각각의 경우를 나누어, 안전 영역의 최대 크기를 구한다. ret = max(ret, solve())의 연산을 통해 최댓값을 비교한다

백주 2636사각형 모양의 판과 한 조각의 치즈가 주어졌을 때, 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전, 치즈가 남아 있는 칸의 개수를 구하는 문제. while문 내부에서 dfs 함수를 이용해 치즈의 테두리 부분을 반복하여 탐색한다. dfs

백준 1068주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 남은 리프 노드의 개수를 출력하는 문제.벡터 adj에 트리의 정보를 저장한 뒤, dfs 함수를 호출하여 노드를 삭제한 이후 남아있는 리프 노드의 개수를 구한다.adj를 root부터 순회하며 리프 노드의 개

백준 1325어느 회사 컴퓨터의 신뢰 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 문제.벡터 adj에 신뢰 관계를 저장한 뒤, 각각의 해킹 가능한 컴퓨터의 개수를 배열 ret에 담는다. 이 과정에서 트리 탐색을 위하여, 함

백준 17298수열의 각 원소에 대한 오큰수를 구하는 문제.스택 stk를 이용하여 문제를 해결한다. a\[i]의 값을 입력받으며 만약 stk의 내용이 존재하고, a\[i]의 값이 a\[stk.top()]의 값보다 크다면, ret\[stk.top()]에 a\[i]를 저장

백준 15686집과 가장 가까운 치킨집 사이의 거리를 치킨 거리라 하며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합이라고 한다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시키려 할 때, 어떻게 고르면 도시의 치킨 거리가 가장 작게 될

백준 2589보물이 서로 간의 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다고 할 때, 보물 사이 이동 시간을 구하는 문제.보물섬 지도의 정보를 배열 a에 저장한 후, a를 순회하며 a\[i]\[j]의 값이 'L'일 때마다 bfs

백준 16234주어진 특정 조건을 만족하는 경우, 이웃한 나라의 국경선을 하루간 열어 인구 이동을 진행한다고 할 때, 인구 이동이 총 며칠 동안 발생하는지 구하는 문제.인구 이동이 더 이상 발생하지 않을 때까지, 배열 a를 반복하여 탐색한다. 반복 과정에서 이웃한 두

백준 4179미로 속 지훈이와 불이 매 분마다 한 칸씩, 수평 또는 수직으로 이동한다고 할 때, 지훈이가 불을 피해 미로를 탈출할 수 있는 가장 빠른 탈출 시간을 구하는 문제.불의 이동 경로와 지훈이의 이동 경로를 따로 나누어 해결한다. BFS를 이용하여 불의 방문 정

백준 12869남아있는 SCV의 체력이 주어졌을 때, 뮤탈리스크가 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 문제.BFS를 이용하여 문제를 해결한다. 함수 go는 배열 \_a에 담긴 뮤탈리스크의 데미지 정보를 통해 SCV의 체력을 줄여 나가며 그

백준 16637수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 결과의 최댓값을 구하는 문제.입력받은 수식의 정수와 연산자를 각각 벡터 num과 oper에 담는다. 현재 위치를 가리키는 here, 현재까지의 계산 값을 가리키는 \_num을 인자로 갖는 함수 go

백준 17071정해진 규칙에 따라 이동하는 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제.큐 q에 수빈이의 위치를 반복적으로 push해 나가며, 수빈이의 위치와 동생의 위치를 확인한다. 배열 visite

배군 14497주난이의 점프 한 번은 한 겹의 친구들을 쓰러뜨릴 수 있다고 할 때, 주난이가 초코바를 훔친 범인을 잡기 위해선 최소 몇 번의 점프가 필요한지 구하는 문제.주난이의 위치를 배열 visited와 큐 q에 저장한 뒤, a\[y2]\[x2]의 값이 0이 되기

백준 3197빙판이 덮여 있는 호수 위에 두 마리의 백조가 있을 때, 이들이 며칠이 지나야 서로 만날 수 있는지 계산하는 문제.백조와 물의 위치 정보를 각각 visited_swan, swanQ 와 visited, waterQ에 담은 후, while문 반복을 통해 하루가

백준 1987보드 위의 말은 같은 알파벳이 적힌 칸을 두 번 지날 수 없다고 할 때, 좌측 상단부터 시작한 말이 최대 몇 칸을 지날 수 있는지 구하는 문제.방문한 알파벳의 정보를 담는 배열 visited에 시작 위치 알파벳을 저장한 뒤, go 함수를 호출하여 문제를 해

백준 2529제시된 부등호 관계를 만족하는 k + 1 자리의 최대, 최소 정수를 각각 구하는 문제.함수 go를 재귀적으로 호출하여 문제를 해결한다.go 함수 내에서는 0부터 10까지의 정수를 확인하며, 만약 idx == 0 또는 good(num\[idx - 1], i

백준 9934상근이가 종이에 적은 빌딩 방문 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 문제.주어진 순서의 중간에 있는 빌딩 번호가 각 레벨의 가장 앞에 온다는 규칙을 이용하여 문제를 해결한다.solve 함수는 시작 위치 s와 끝 위치 e를 인자로