C++

처음에는 단순하게 Brute Force로 풀었다. 배열을 입력 받는다.for문을 이중으로 사용하여 바깥 for문은 i=0부터 i=n-1까지, 안쪽 for문은 j=i+1부터 j=n까지 반복시킨다. arri\*arrj의 값을 sum에 더한다.이렇게 풀었을 때 시간 초과가

이 문제를 처음 접했을 때는 크기 순으로 정렬시킨 배열을 하나 더 생성하여 그 배열의 인덱스 값을 결과 배열에 넣고, 결과 배열에서 같은 값을 가진 수만큼 빼면 답을 구할 수 있을 거라고 생각했다.x배열과 x2배열을 만들고 x배열의 값을 x2배열에 복사한다.x2배열을

기본적인 원형큐 문제이다. queue STL을 사용하여 풀었다. queue는 Last In First Out이다. push()를 하게 되면 뒤로 들어가게 되고, pop()을 하게 되면 가장 앞의 원소를 지운다.원형 queue는 앞과 뒤가 연결된 원형이라고 생각할 수 있

이런 문제는 결과값들을 분석하는 것이 중요하다고 생각한다. 그래서 결과값들을 써보며 분석해보았다. 결과값들을 저장하는 배열을 cnt라 하고, N을 index로 적용해서 생각했다.cnt1 = 1 (1) 이다.cnt2 = 2 (1+1, 2) 이다.cnt3 = 4 (1+1+

이번 문제는 for문을 이중으로 사용하여 풀었다.연속된 값들을 계속 더하여 cnt가 m과 같아지면 result를 증가시킨다.cnt가 m보다 작다면 계속 반복한다.Code문제는 풀었지만 알고리즘 분류에 두 포인터로 명시되어 있었고 두 포인터로 푸는 법도 찾아보았다. lo

이번 문제는 이분 탐색을 통해 해결할 수 있는 문제이다. low=0, high=1,000,000,000으로 설정한다.mid를 (low+high)/2로 설정하고, x, y에 mid를 더하며 tempz값을 z와 비교한다.z가 tempz보다 크거나 같으면 low를 mid+1

이번 문제는 pair와 우선순위 큐를 사용하여 해결했다.n에 반복 횟수를 입력받는다.pair에 각 강의의 시작 시간과 종료 시간을 입력 받는다.각 강의들을 시작 시간순으로 정렬시킨다.가장 처음 시작하는 강의의 종료 시간을 우선순위 큐에 넣는다.반복문을 통해 우선순위 큐

이번 문제는 쉽게 생각하면 받은 두 인덱스를 for문에 넣어서 구하면 된다. 그러나 이런 방식으로 구하면 시간 초과가 발생한다.문제의 해결 방법은 문제 이름에 있었다. 구간 합을 구하면 간단하게 풀 수 있는 문제다.배열을 입력받는 for문에서 구간합 배열을 같이 구해준

이번 문제도 전에 풀었던 부분 합 구하기 문제와 비슷한 방법으로 부분 합을 구해 풀어야 시간초과가 발생하지 않는 문제이다. NxN 형식이라 공식을 찾아내는데 조금 힘들었다. psumi=psumi-1+psumi-psumi-1+arri; 이러한 공식으로 psum을 구했다.

이번 문제를 처음에 접했을 때 부분 수열이 연속된 수들에서만 생성할 수 있다고 생각했다. 그래서 다음과 같이 풀었다.sum에 모든 배열의 값을 더한다.k를 1로 두고 배열의 n-1부터 0까지 검사하며 빼고 만약 S와 같으면 멈추고 cnt를 증가시키고 k도 증가시켰다.그

이번 문제는 처음 봤을 때는 쉽게 해결할 수 있을 것 같았지만 중복을 피해야 한다는 제약 때문에 조금 까다로웠던 문제였다.sort()함수를 이용해 배열을 정렬한다.마지막에 추가한 수와 이번에 추가하는 수가 값이 같다면 중복이 되므로 이때는 출력을 하지 않아야 한다.마지

이번 문제는 공식을 찾아내서 푸는 문제였다.cnt배열에 각각 인덱스 값을 값으로 넣는다.for문을 sqrt(인덱스값)까지 반복하며 cnt배열에 최소값을 찾아 넣는다.Code

이번 문제는 문제 그대로 해결하면 수가 매우 커지므로 과정마다 %연산을 사용해 수를 줄여줘야한다.a에 어떤 수가 와도 일의 자리만 고려하면 된다. 1~9 모든 수가 4개의 수로 이뤄진 패턴을 반복한다.4개의 수로 패턴이 이뤄지므로 b에 %4연산을 미리 해준다. 이때 b

이번 문제는 우선순위 큐를 사용하여 N번째로 큰 수를 구하는 문제이다. 유의할 점은 메모리 제한이 12 MB라는 점이다. 처음에는 메모리 제한을 신경쓰지 않고 구현했다.우선순위큐를 큰 순서대로 정렬되도록 선언한다.N-1번 만큼 pop하고 top을 return한다.이렇게

이번 문제는 KMP 알고리즘을 활용하는 문제였다. 본인은 KMP 알고리즘을 처음 접해봤기 때문에 찾아보면서 해결했다.KMP 알고리즘은 문자열 안에서 주어진 문자열을 찾는 알고리즘으로 O(nm)을 O(n+m)으로 개선시킬 수 있다.apple로 예를 들어 본다.prefix

이번 문제는 함수의 재귀 호출을 이용하여 해결하는 문제였다.트리가 만들어진다고 생각을 한다.재귀함수를 통해 완전탐색으로 탐색하여 result배열에 하나씩 채워 넣고 트리의 깊이가 6이 되면 result배열을 출력한다. Code

이번 문제는 다익스트라 알고리즘을 사용하여 해결하는 문제였다. 문제를 풀기 전에 다익스트라 알고리즘에 대해 조금 알아보도록 하자.그래프 알고리즘에서 최소 비용을 구하는 문제에서 사용하는 대표적인 알고리즘이다. 두 노드 사이의 비용을 구하는 문제에 유용하게 사용된다.시작

이번 문제는 전에 사용했던 다익스트라 알고리즘을 활용하여 푸는 문제였다.우선순위 큐에 넣기 때문에 작은 값들의 우선순위가 default로 높게 잡힌다. 그러므로 -를 해서 우선순위 큐에 넣어줘야 한다.

이번 문제는 BFS 알고리즘을 활용하여 푸는 문제였다.DFS & BFS BFS에 대한 설명은 이 글로 대신한다.기존 BFS에서 사용하는 큐에 time을 세기 위해 pair를 사용해 2개의 값을 넣었다.Code

이번 문제는 BFS 알고리즘을 활용하여 해결하는 문제였다. DFS & BFS원래 BFS는 방문 처리를 하였지만 이번 문제에서는 그래프에 직접적으로 값을 더하여 그 중 가장 큰 값을 시간으로 구했다.그래프 좌표의 이동을 dx, dy 배열로 구현했다.BFS를 통해 그래프

이번 문제는 DFS 알고리즘을 활용하여 해결하는 문제였다.DFS & BFS입력에 띄어쓰기가 없으므로 string 형으로 입력 받은 뒤에 2차배열에 넣어준다.그래프의 이동은 dy, dx 배열을 통해 구현한다.DFS 안에서 그래프 범위 내의 방문하지 않은 값이 1인 인덱스

이번 문제는 두 포인터 알고리즘으로 쉽게 풀 수 있는 문제였다. 이중 for문으로도 해결 가능하지만 시간 제한에 걸리게 된다.start, end 두 포인터를 두고 while문을 실행시킨다.만약 sum이 s보다 크거나 같다면 출력값을 저장하는 cnt에 넣는다. 이때 기존

이번 문제는 BFS 알고리즘을 활용하여 해결하는 문제였다.DFS & BFS 알고리즘BFS함수 안에서 BFS에 이용할 큐를 생성한다. 이때 인자를 4개 두는데 순서대로 y,x,부순 블럭 수, 이동거리를 의미한다.좌표의 이동은 dy, dx배열로 구현했다.좌표가 나타내는 값

이번 문제는 투 포인터 알고리즘을 활용해 푸는 문제였다.벡터를 오름차순으로 정렬해준다.두 개의 포인터를 벡터의 첫 인덱스와 끝 인덱스를 가리키게 한다.두 수의 합이 찾는 값과 같다면 cnt를 증가시켜주고 끝 인덱스를 감소시켜준다.두 수의 합이 찾는 값보다 크다면 끝 인

이번 문제는 투 포인터 알고리즘을 활용하여 해결하는 문제였다.배열을 정렬해준다.start포인터는 0, end포인터는 n-1으로 초기화해준다.두 포인터가 가리키는 배열의 원소 합의 절댓값이 최솟값보다 작으면 최솟값에 저장해주고 이때의 각 포인터를 저장해준다.두 포인터가

이번 문제는 정렬을 통해 간단하게 해결할 수 있는 문제였다. a배열을 오름차순으로 정렬한다.b배열을 내림차순으로 정렬한다.s를 구한다.

이번 문제는 정렬과 우선순위 큐, 그리디 알고리즘을 활용해 해결하는 문제였다. 본인은 처음에 다음과 같이 생각했다.가방을 내림차순으로 정렬한다.보석의 가치를 내림차순으로 정렬한다.가방의 용량과 보석의 무게를 비교하며 가방에 넣는다.그러나 이 방법은 만약 보석의 무게와

이번 문제는 DFS 알고리즘을 재귀적으로 구현하여 해결했다.정수A를 2로 곱할 수도 있고, 10을 곱한 뒤에 1을 더할 수도 있다.DFS 함수 안에서 x2와 x10+1을 DFS로 재귀호출 한다.result에는 임의의 큰 값을 넣고, result에는 더 작은 cnt값이

이번 문제는 스택 자료구조와 그리디 알고리즘을 활용하여 해결하는 문제였다.숫자를 string형으로 받는다.string형 숫자를 orig라는 vector에 char형으로 넣는다.orig의 앞에서 부터 result에 넣어준다. 이때 뒤에 등장하는 수보다 작은 수들은 모두

이번 문제는 스택을 활용하여 해결하는 문제였다. 시간 제한을 보고 시간이 부족하겠다고 생각은 했지만 우선은 스스로 풀어보기로 했다.n만큼 반복하며 stack에 탑의 높이를 넣어준다.이중 반복문 안에서 stack을 복사한다.복사한 stack을 pop시키며 원래 stack

이번 문제는 특별한 알고리즘을 사용하지 않고 구현하는 문제였다. 남학생일 경우는 쉽게 구현할 수 있었지만 여학생인 경우가 조금 어려웠다. 남학생인 경우 인덱스가 받은 수의 배수인 경우의 스위치의 상태를 바꾸므로 for문 안에 %를 사용하여 스위치 상태를 바꾼다.여학생인

이번 문제는 주어진 조건들을 이용하여 재귀함수를 구현하는 문제였다. int형으로 재귀함수를 정의한다.위의 제약 조건들을 입력한다.재귀 함수의 결과가 여러번 더해지는 경우에는 result에 값을 저장하고 result를 반환한다.무한 루프인 while문 안에서 a,b,c를

이번 문제는 그래프 탐색, 백트레킹, DFS를 통해 해결할 수 있는 문제였다.보드의 입력이 문자열로 이뤄지므로 string으로 받아 배열에 저장하였다.bool형 배열을 통해 지난 알파벳인지 판별한다.상하좌우로 밟지 않은 칸으로 이동하며 밟은 표시를 해주며 진행하고, 밟

이번 문제는 특별한 알고리즘 구현 없이 해결할 수 있는 문제였다. 본인은 처음에 전체 넓이를 더한 뒤에 겹치는 부분을 빼야한다고 생각했다. 그러다가 문득 색종이가 올라간 부분만 표시를 해주면 된다는 생각을 하게 되었고 그 방법으로 간단하게 해결할 수 있었다.흰색 도화지

이번 문제는 특정 알고리즘을 사용하지 않고 구현하는 문제였다. 4개의 꼭지점의 좌표를 저장한다.4개의 좌표를 이용하여 좌표를 r번 이동시킨다.이동이 끝나면 4개의 꼭지점을 안쪽으로 한칸씩 이동시켜 안쪽 배열을 돌린다.이를 반복한다.

이번 문제는 스택을 활용해서 해결하는 문제였다. 이중 for문을 통해서도 해결할 수는 있지만 시간 제한에 걸리게 되므로 스택을 통해 해결해야 한다.본인은 스택으로 해결하기 전에 이중 for문으로 한번 구현해 보았고 당연히 시간 제한에 걸렸고, 스택으로 다시 한번 풀어보

이번 문제는 결과값의 패턴을 파악하여 해결하는 문제였다. 본인이 파악한 결과값의 패턴은 다음과 같다.n이 1일 때와 2일 때, 모두 결과값이 1이다.n이 3일 때는 결과값이 2이다.n이 4일 때는 결과값이 3이다.n이 5일 때는 결과값이 5이다.n이 6일 때는 결과값이

이번 문제는 브루트포스 알고리즘을 활용하여 해결하는 문제였다. n을 입력받고 n만큼 s와 b를 입력받는다.ts에 s를 모두 곱한 값을 저장하고, tb에 b를 모두 더한 값을 저장한다.사용 여부를 체크하기 위한 bool형 used배열을 사용하여 모든 경우를 확인한다.확인

이번 문제는 DFS를 활용하여 해결할 수 있는 문제였다. 보라색 테트로미노를 제외한 테트로미노들은 그래프 이론을 통해 확인이 가능하다. 그래서 보라색 테트로미노는 따로 확인을 실시했다.DFS의 인자로 y, x, sum, cnt를 주었다. sum은 테트로미노가 올라간 자

이번 문제는 BFS를 활용하여 해결할 수 있는 문제였다. 처음에 문제를 시도할 때에 큐를 사용하지 않아 시간 초과가 발생했다. BFS는 큐를 사용한다는 것을 기억하자. queue<pair<>>를 사용하여 큐에 현재 위치와 버튼 누른 수를 저장한다.BFS를 돌

이번 문제는 이분 탐색을 통해 해결하였다. 소수들을 먼저 벡터에 넣어준다.소수를 판별하는 기준은 이중 for문에서 합성수에 방문표시를 하여 방문되지 않은 수를 소수로 인지한다.주어진 k보다 큰 첫번째 소수를 찾고, 그 소수와 그 앞의 소수의 차를 출력한다.만약 k의 방

이번 문제는 이분탐색을 통해 해결하였다.우선 범위가 최대 10억이므로 자료형은 long long을 사용한다.입력받은 x중 가장 작은 수를 사용해야 하므로 오름차순으로 sort해준다.이분탐색의 범위는 가장 작은 수인 x0과 x0이 될 수 있는 수 중 가장 큰 수인 x0+

이번 문제는 누적합을 구한 뒤에 이분탐색을 통해 경우를 찾는 문제였다. 여러번 시도 끝에 해결하였는데 처음에는 다음과 같이 작성하였고 오답처리 당했다.배열 a,b에 대한 누적합 배열 asum, bsum을 구하고 이를 정렬한다.누적합 배열 asum에 대해서 이분탐색을 누

이번 문제는 이분탐색으로 해결하는 문제였다. 처음에는 이분탐색으로 해결하는 방법이 생각이 안나서 이분탐색을 빼고 생각해보았다.각 휴게소 간의 거리 배열 dis를 만든다.dis를 내림차순으로 정렬한다.가장 큰 거리를 반으로 자른다. (휴게소를 사이에 세운다.)dis를 다

이번 문제는 입력의 패턴을 읽어 해결하는 문제였다. 처음에는 가로와 세로에 대한 최댓값과 최솟값을 구해서 해결하려 했다. xcode에서는 정상적으로 동작했지만 백준 채점은 오답처리 되었고, 다른 방법으로 해결하였다.기본적인 틀은 큰 직사각형을 구한 뒤 파여져있는 작은

이번 문제는 이분탐색을 통해 해결하는 문제였다. 이분탐색의 범위에 대해서 고민을 많이 했던 것 같다. 이분탐색의 범위는 0과 배열의 최대값으로 하였다.배열을 돌며 해당 인덱스에서의 최대값-최소값의 값이 mid보다 크다면 cnt를 증가시켜주고, cnt가 m보다 작거나 같

이번 문제는 백트레킹 알고리즘을 활용하여 해결하였다. 문제의 조건없이 출력하는 것은 쉽지만 같은 수를 여러 번 골라도 되지만 길이M의 수열끼리는 중복을 허용하지 않는다는 조건에서 생각이 필요했다.bool형 num_chk 배열을 통해 입력된 값이 존재하는지 확인한다.만약

이번 문제는 백트레킹을 통해 해결하였다.DFS의 인자를 현재 인덱스+1,누적된 결과값, +갯수, -갯수, \*갯수, /갯수로 정의한다.모든 경우를 전부 비교해야 하므로 각 연산자의 갯수가 0보다 크다면 그 연산을 진행한다.DFS의 첫번째 인자, 즉 현재 인덱스+1에 해

이번 문제는 백트레킹을 활용하는 문제였다. 처음에 고민했던 것은 결과값을 n을 입력 받은 후에 구할지, 미리 결과값을 배열로 저장해둘지 결정하는 것이었다. 본인은 결과값들을 배열에 저장하기로 하였다.우선 조건으로 명시되어야 하는 것이 앞의 자리가 가장 커야한다는 것이었

이번 문제는 그리디 알고리즘을 통해 간단하게 해결하였다.입력받은 예상 등수를 오름차순으로 정렬한다.예상 등수를 wish라고 하고 등수를 rank라고 한다면, abs(wish-rank)가 최소가 되기 위해서는 예상 등수 배열의 첫번째 수부터 차례대로 등수를 메긴다.반복문

이번 문제는 백트레킹을 통해 해결하였다.n이라는 사이클동안 키트를 한번씩만 사용할 수 있으므로 사용 여부를 체크하는 bool형의 chk 배열을 선언해준다.DFS함수의 인자로 일수를 나타내는 day와 현재 중량을 나타내는 cur을 넣어준다.DFS함수 내에서 day와 n이

이번 문제는 BFS를 통한 그래프 탐색으로 해결하였다. 문제를 이해하는데 조금 오래 걸렸던 것 같다.매 사이클마다 방문한 영상인지 체크하기 위한 visited 배열을 선언한다.영상은 vector 배열로 선언하여 각 영상에서 추천되는 영상을 저장한다.영상 간의 연결은 양

이번 문제는 DFS를 통한 그래프 탐색으로 해결하였다. 결과적으로 현재 위치에서 갈 수 있는 최대 깊이-현재 위치의 깊이>=d인 위치까지 가면 모든 노드에 전단지를 돌릴 수 있게된다. 경로들을 vector배열로 저장해준다.각 노드에서의 깊이와 최대 깊이를 나타내기 위한

이번 문제는 정렬로 간단하게 해결하였다.학교명과 술 소비량을 같이 저장하기 위해 vector<pair<string, int>>형을 사용한다.술 소비량으로 내림차순 정렬을 해야하므로 compare함수를 작성하였다.STL의 sort함수에 compare을 넣어 내

이번 문제는 Greedy 알고리즘을 활용하여 해결하였다. 우선 규칙을 찾아보는 것이 중요했다.vi가 가질 수 있는 그렇고 그런 사이는 n-i개이다.이를 0부터 n-1까지 반복하고 더하여 k를 만들어내는 문제이다.k의 범위가 0보다 크거나 같고, n-1보다 작거나 같다면

이번 문제는 Greedy 알고리즘을 통해 해결하였다. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열이 PPAP가 된다는 정의에서 이해가 조금 필요했다. 이 정의를 간단한 예시들로 정리해보면 PPAP -> PPAPPAP(1번 P가 PPAP가 된 경우), PPPAP

이번 문제는 분할정복으로 해결하였다. 처음에는 재귀방식으로 Moo배열을 만들어 주려고 생각을 했었다. 그러나 구현하던 도중에 n의 범위가 10억이기 때문에 메모리 초과가 발생한다는 사실을 알게 되었다. 그래서 Moo배열의 길이를 이용하여 길이가 n보다 크거나 같을 때까

이번 문제는 분할 정복으로 해결하였다. 전에 풀어보았던 별 찍기보다 복잡한 형태의 문제여서 고민을 많이 했다. 출력되는 별이 많으므로 2차원 배열에 저장하기로 하였다.n의 범위가 3x2^10까지이므로 3072까지 가능하다. 예제 출력을 자세히 보면 가장 위에 별이 가로

이번 문제는 문자열을 주어진 우선순위에 따라 정렬시켜 해결하는 문제였다. 본인은 C++의 표준 라이브러리 중 sort함수를 사용하였다.sort함수를 사용할 때에 3번째 인자를 비워두면 오름차순으로 정렬된다.3번째 인자에 들어갈 정렬 기준 함수 compare함수를 정의하

오랜만에 알고리즘 문제를 풀게 되어서 쉬운 문제를 풀어보았다. 처음 보기에는 이 문제도 어렵다고 생각했지만 패턴을 파악하였고 이를 통해 쉽게 해결하였다.k번째 23은 k\*23이 된다.endl을 사용하면 시간제한에 걸리기 때문에 '\\n'을 사용하였다.

이번 문제는 STL의 sort함수를 사용하여 해결하였다.중복을 제거하는 방법으로 bool형 배열을 사용한다. n을 입력 받았다면 chkn은 true가 되고, 새로 입력받은 m에 대한 chkm이 true라면 배열에 넣지 않는다.배열에 추가하기 편하도록 배열은 vector

앞서 파이썬으로 풀어보았던 DP문제를 c++로 다시 풀어보았다. 같은 방식으로 풀이했기 때문에 풀이는 생략한다.\[ BOJ / Python ] 2293번 동전 1

파이썬으로 풀었던 문제를 C++로 다시 한번 풀어보았다. 풀이 방법은 파이썬과 같다. \[ BOJ / Python ] 2096번 내려가기

파이썬으로 풀어봤던 코드를 C++로 다시 한번 풀어보았다. 파이썬 코드와 같은 방식으로 풀이하였기 때문에 설명은 생략한다.\[ BOJ / Python ] 13398번 연속합 2

파이썬으로 풀어본 문제를 같은 방식으로 C++로 풀어보았다. 풀이 방식은 같으므로 설명은 생략한다.\[ BOJ / Python ] 11497번 통나무 건너뛰기