Baekjoon

백준 문제를 본격적으로 풀기 전에, 모든 코테 문제들은 시간 제한이 있다. (보통 일반적으로 1 ~ 5초의 시간제한이 주어진다.)파이썬의 경우 약 2,000만 ~ 1억 번의 연산 횟수를 진행할 수 있다고 한다.따라서 파이썬의 경우 1초에 1,000만번 또는 2,000만

https://www.acmicpc.net/problem/11720이 문제는 숫자를 공백없이 입력받을 경우 각 자릿수의 합을 더하여 출력하는 문제이다.문제풀이 방법은 다음과 같다.숫자를 리스트 형태로 입력받는다.for문을 이용해서 수를 하나씩 들고와서 더한다.

https://www.acmicpc.net/problem/1546이 문제는 입력 받은 점수 중 최대값을 구한 다음, 모든 점수를 최댓값 \* 100으로 나누는 것이다.근데 각각 점수를 변환할 필요 없이 모든 점수를 더한 후 새로운 평균을 산출해도 된다.$(A

https://www.acmicpc.net/problem/11659입력할 수의 개수와 숫자가 주어지면, i번째부터 j번째까지 수의 합을 구하는 문제이다.문제에서 수의 개수와 합을 구해야하는 횟수는 최대 100,000 이다. 따라서 i번째부터 j번째 수가 주어질

https://www.acmicpc.net/problem/11660 2차원 구간에서 구간 합을 어떻게 구할지가 핵심인 문제이다. 이 역시 각 질의마다 구간합을 구하면 연산량이 늘어나 시간초과가 발생하므로, 미리 구간 합을 구해놔야한다. 2차원 구간에서 합 배열 구하기 $Di = Di + Di-1 - Di-1 + Ai$ 여기서 Di + Di-1를 더하...

https://www.acmicpc.net/problem/10986이 문제는 연속된 부분의 구간 합이 M으로 나누어 떨어지는 구간의 개수가 몇 개인지 카운트하는 문제이다.우리가 학습한 구간 합 공식을 사용하되, 중간에 나누어 떨어지는 구간이 몇 개 있는지도 같

https://www.acmicpc.net/problem/2018자연수 N의 값이 연속된 자연수의 합으로 표현할 수 있는 개수가 몇 개인지 구하는 문제이다.N의 범위가 10,000,000으로 매우 큰 수이므로 시간 복잡도가 $O(nlogn)$만 되어도 시간 초

https://www.acmicpc.net/problem/1940투 포인터를 사용하여 문제를 해결하는 문제이다. 갑옷은 2개의 재료로 만들어진다고 나와있으므로 2개의 수를 더해서 M을 만족할 수 있는 개수를 찾으면 된다.또한 시간 제한이 2초이고 N의 최댓값은

https://www.acmicpc.net/problem/1253어떤 목표값이 서로 다른 두 수의 합으로 나타낼 수 있다면 해당 경우를 카운트 하는 문제이다.문제의 핵심은 두 수가 서로 달라야 한다. 다시 말해 목표값인 자기 자신을 포함하면 안된다는 말이다.(

https://www.acmicpc.net/problem/12891슬라이딩 윈도우 알고리즘을 통해 문제를 해결해야 한다. 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 방법이다.투 포인터 알고리즘과 매우 비슷하다.(투 포인터

https://www.acmicpc.net/problem/11003$Di = A{i - L + 1}$ ~ $A_i$ 중의 최솟값이라는 부분에서 $i-L+1$이 핵심이다.예제를 기준으로 생각해보자.N = 12, L = 3i = 1, 2, 3 ...$D1 = A{

https://www.acmicpc.net/problem/1874스택의 후입선출 원리를 이용하여 오름차순 수열을 만들 수 있는지 판별하는 문제이다.1부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식으로 풀

https://www.acmicpc.net/problem/17298N의 최대 크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과하게 된다. 따라서 이 문제는 스택을 이용하여 해결해야한다.예제의 3, 5, 2, 7에 대한 오큰수를 구하려면

https://www.acmicpc.net/problem/2164큐를 사용할 수 있는지 묻는 문제이다. 큐의 핵심 원리인 선입선출 개념만 알고 있으면 문제를 쉽게 해결할 수 있다.문제풀이 방법은 다음과 같다.큐에서 가장 앞부분을 pop큐에서 한번 더 pop한

https://www.acmicpc.net/problem/11286우선순위 큐를 사용할 수 있는지 묻는 문제이다. 우선순위 큐란 기본적으로 큐의 성질을 가지고 있으면서 내부에 특정 우선순위를 부여할 경우 우선순위에 맞게 값이 나오는 것을 말한다.Heap 구조로

https://www.acmicpc.net/problem/2750파이썬의 sort() 함수를 사용하면 쉽게 정렬할 수 있지만, 버블 정렬을 사용하여 구현해보자.버블 정렬은 이중 for문을 사용하므로 $O(N^2)$의 시간 복잡도를 가진다. N의 최대크기가 1,

https://www.acmicpc.net/problem/1377버블 정렬의 swap이 한 번도 일어나지 않은 루프가 몇 번째인지 알아내는 문제이다. 안쪽 for문에서 한번도 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 의미와 같으므로 프

https://www.acmicpc.net/problem/1427배열을 내림차순으로 정렬하는 문제로, 각 자리의 숫자가 붙어있을 때 각 자릿수을 어떻게 구분하여 정렬할지 생각해보는 문제이다.파이썬은 문자열 처리에 매우 강력한 언어라서 그냥 list형태로 받으면

https://www.acmicpc.net/problem/11399N의 최댓값이 1,000이고 시간제한이 1초이므로 $O(N^2)$ 이하인 시간복잡도 알고리즘 중 아무거나 사용해도 된다.돈을 뽑는데 시간이 가장 적게 걸리는 사람부터 오름차순으로 정렬한 후 합

https://www.acmicpc.net/problem/11004N개의 수가 주어지고 이를 오름차순으로 정렬하였을 때 앞에서부터 K번째 있는 수를 어떻게 구할 것인지 구하는 문제이다.현재 데이터 크기가 최대 5,000,000이고 시간제한은 2초이므로 $O(n

https://www.acmicpc.net/problem/2751N의 최대 범위가 1,000,000이므로 $O(nlogn)$의 시간복잡도로 정렬을 수행하면 된다.이 경우 병합 정렬은 $O(nlogn)$의 시간복잡도를 보장하니 해당 알고리즘을 통해 풀이를 진행해

https://www.acmicpc.net/problem/1517이 문제는 버블 소트를 진행하는 과정에서 숫자 간의 자리교체(swap)이 몇 번 발생하는 지 카운트하는 문제이다.데이터의 개수인 N의 최대 범위가 500,000 이므로 $O(nlogn)$의 시간복

https://www.acmicpc.net/problem/10989언뜻 보면 그냥 오름차순으로 정렬하라는 쉬운 문제처럼 보이지만, N의 최대 범위가 10,000,000으로 매우 큰 숫자이다. 따라서 우리가 흔히 정렬을 사용할때 걸리는 시간복잡도인 $O(nlog

https://www.acmicpc.net/problem/11724 깊이우선탐색(DFS)를 활용하는 전형적인 문제이다.

https://www.acmicpc.net/problem/2023소수 판단 알고리즘과 함께 DFS 탐색 기법을 사용해야 해결할 수 있는 문제이다.문제에서 숫자 자릿수 N이 주어졌을 때, 신기한 소수를 모두 찾아서 출력하라고 했으므로 먼저 소수를 판단하는 알고리

https://www.acmicpc.net/problem/13023 DFS 탐색을 통해 해결하는 문제이다.

https://www.acmicpc.net/problem/1260 문제에서 DFS와 BFS 탐색한 결과를 출력하는 프로그램을 작성해 보라고 하였다. 이전에 DFS는 설명했으니 생략하도록 하고, BFS에 대해 알아보도록 하자. BFS란 Breadth First Se

https://www.acmicpc.net/problem/2178 미로 탐색 역시 BFS를 통해 해결하는 문제이다. 가장 왼쪽 상단 위인 (1, 1) 좌표에서 시작하여 N x M 미로의 크기인 (N, M)까지 이동하는 최단 경로를 구해야 한다. BFS는 특정 노드를

https://www.acmicpc.net/problem/1167 트리에서 두 점 사이의 거리 중 거리가 가장 긴 것을 트리의 지름이라고 하였다. 먼저 트리라는 것은 사이클이 형성되지 않는 연결 그래프를 의미한다. 예제 입력에 대한 그래프 표현은 다음과 같다.

https://www.acmicpc.net/problem/1920N의 범위가 최대 100,000이므로 단순 반복문만으로 문제를 해결하려고 하면 $O(N^2)$이 되어 시간초과로 해결할 수 없으며, 못해도 $O(NlogN)$의 시간복잡도인 알고리즘으로 해결해야

https://www.acmicpc.net/problem/2343블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 한다는 점이 이진 탐색을 생각해 볼 수 있는 단서가 된다.블루레이에 첫 번째 레슨부터 마지막 레슨까지 차례대로 저장해 보면서, 모두 저장할

https://www.acmicpc.net/problem/1300k의 범위가 1 ~ $min(10^9, N^2)$이므로 시간복잡도가 $O(N^2)$인 알고리즘은 사용할 수 없다.이 말은 N x N과 같은 2차원 배열에서 직접 원소를 모두 확인하는 방법이 불가능

https://www.acmicpc.net/problem/11047그리디 알고리즘 하면 가장 쉬운 예시로 나오는 동전 문제이다.그리디 알고리즘이란 이름 그대로 문제가 주어진 조건에서 항상 최선이라고 생각하는 해를 고르는 것이다.문제에서는 동전을 최소한으로 사용

https://www.acmicpc.net/problem/1715정렬된 카드 묶음들을 합칠 때 어떤 방식으로 합쳐야 비교를 최소한 할 수 있는지 묻는 문제이다.문제를 푸는데는 상관이 없지만 문제에서 20장의 카드와 30장의 카드를 합치려면 20 + 30 = 5

https://www.acmicpc.net/problem/1744특정 수열이 주어지면 특정 수를 적절히 묶어서 최댓값을 만들어 내야 한다.예를 들어 A = -1, -2, 0, 1, 2, 3, 4가 주어지면, $(-2 × -1) + 0 + (1 × 2) + (3

https://www.acmicpc.net/problem/1931한 개의 회의실에 가능한 많이 회의를 잡을 수 있도록 구하는 것이 문제이다.예제 입력을 기준으로 잘 생각해보면, 정렬을 아래와 같이 진행해야 한다는 점을 파악할 수 있다.끝나는 시간을 기준으로 오

https://www.acmicpc.net/problem/1541그리디 관점으로 생각해보면 쉽게 풀리는 문제이다. 최솟값을 만들기 위해 "-"를 기준으로 문자열을 구분한 다음 가장 첫번째에 등장하는 수만 더하고, 이후에는 모두 빼주면 된다.예제 입력을 기준으로

https://www.acmicpc.net/problem/18352BFS를 통해 주어진 최단거리 K를 만족하는 도시를 찾는 문제이다. 만약 하나도 존재하지 않을 경우 -1을 출력하라고 했다.예제 그림을 기준으로 본다면 K = 2, X = 1인 경우 1번 노드를

https://www.acmicpc.net/problem/1325A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다는 것이 핵심이다.예제 입력을 기준으로 분석해보면 다음과 같다.N = 5, M = 43은 1을 신뢰 -> 1을 해킹하면 3을 해킹 가능

https://www.acmicpc.net/problem/1707이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 2가지 색으로만 표현이 가능한 그래프를 의미한다.예제의 테스트 케이스를 그림으로 표현해보면 다음과 같다.첫 번째 그래프인 1 &

https://www.acmicpc.net/problem/2251

https://www.acmicpc.net/problem/1717최대 원소의 개수가 1,000,000이고 질의 개수가 100,000으로 상당히 큰 편이다. 따라서 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.유니온 파인드란 여러 노드가 있을 때 특정 2