알고리즘

먼저, 문제를 풀기전 피보나치 수의 점화식을 통한 행렬곱에 대한 이해가 필요했다.n이 0부터 시작할 경우, \[1,1,1,0] 이라는 행렬이 만들어지는 것을 점화식을 통해 확인할 수 있었고, 또한 n이 1씩 늘어날 수록, \[1,1,1,0] 이라는 기본 행렬값 자체를

일단 a를 제곱하여 해결하는 문제인데, 분할 정복을 이용하여 이는 쉽게 해결하였다. 단, long long 범위를 계속해서 넘지 않도록 컨트롤을 지속적으로 해주어야하는데, 이는, 한번의 연산과정에서 항상 c의 나머지를 계산해주는 과정을 중간중간에 집어 넣으면서 해결할

기본적으로, dfs를 사용하면 풀 수 있는 아주 간단한 문제였다. 그나마 지나치기 쉬운점이라면, 1번 컴퓨터를 탐색할때는 카운트에서 제외해줘야한다는점! 또한, dfs의 특정상, Link들에 가중치들이 따로 없다. 그렇기에,이런식으로, 한 링크마다 양쪽 node vect

문제는, DP를 사용하면 정말 간단하게 풀 수 있다. 그리고, 이 파도반 수열에는 간단한 점화식이 존재하는데n이 4 이상일 경우, Pn=Pn-2+Pn-3 이라는 간단한 점화식이 존재한다. 이 점화식을 이용해서 DP로 사용한 배열을 채워주었고, 그 배열값을 출력함으로써

겉보기에 굉장히 쉬운 문제지만, 이 문제의 의외의 어려움은, 바로 시간 초과에 있다. 시간 복잡도를 O(1)로 풀어줘야 문제를 해결할 수 있기에, DP 개념과 누적합 개념을 이용하여 문제를 해결할 수 있었다.그러나, 초기에는 이런 과정을 거쳐도 문제가 해결되지 않았는데

간략하게만 작성하자면, dfs는 흔히 쓰이는 vector를 이용해서 깊이 우선 탐색을 해줄 수 있었고, bfs는 c++의 queue 라이브러리를 이용해서 front값을 푸쉬팝해주는 방법으로 풀 수 있었다.

회의실 배정의 기본 알고리즘은, 끝나는 시간, end time 순으로 시간을 정렬한다.그 정렬한 배열에서, start time이 현재시간보다 같거나 클 경우, 그 회의를 수행한다.이러한 간단한 그리디 알고리즘을 사용해주었다. 주의 할점은, pair을 이용한 vector

쉬운 문제였다. 간단한 점화식 하나만 계산하면 쉽게 DP를 이용해서 풀 수 있는 문제였다. 이 문제에서 찾을 수 있는 점화식은 바로,N(i)=N(i-2)+N(i-1)이다. 이를 이용하면 아주 쉽게 풀 수 있는 문제였다.

DP를 이용해서 풀 수 있는 쉬운 문제였다. 내가 사용한 방식은, 배열의 아래쪽 부터 차례차례로 i번째 배열이라고 하면, 그 i번째부터 i,i+1,i+2 배열등등에서의 최솟값과 현재 i 배열에 있는 값을 더하여서 현재의 최솟값을 처음 정해준 list에 저장하는 방식으로

c++의 stack 라이브러리를 사용한다면, 이 문제는 말도안되게 쉽다. 하지만, stack 라이브러리를 사용한 경험이 없어서 한번 연습삼아 문제를 풀어보았다. 문제는 간단하다. 입력이 0이면 pop, 그 외엔 push를 해주는 아주 간단한 문제였다.

C++에서 heap은 우선순위 큐를 이용하면 아주 간단하게 풀 수 있다. 여기, priority_queue라는 stl이 C++에는 존재한다. 그리고 그 우선순위 큐를 이용해서 아주 간단하게 문제를 해결하였다. 여기서는, 최대힙임으로 queue 정렬은 less'<'

간만에 풀어본 조금 어려운 문제였다. 일단, 이중 우선순위 큐를 구현하는것을 max_queue와 min_queue 두개를 만들어서 연산하는 식으로 계산하였다. 그리고, dp의 visited 개념을 이용하여, test라는 map을 만들어, 이 수가 다른 queue에서 제

재귀를 이용해서 간단하게 풀 수 있었던 문제이다. 특히 1,2,4,8,16,32,64,128 등, 하나의 색종이가 분할 되었을때 4분할로 잘라진다는 점을 이용하였다.그래서, 하나의 색종이에서 색이 일치하지 않을때, 이렇게 4개의 분할에서 재귀 함수가 실행될 수 있도록

실버1의 문제라고 하기엔, 약간은 어려웠다. 특히, 처음엔 list나 map을 사용하려했으나, 문제에서 주어지는 배열의 범위가 2의 15승까지이기에, 메모리 초과가 나기에 다른 방법을 선택해야했다. 2번쨰로 생각한 방법이, 배열에 저장하지 않고, r,c 행열에 다다를때

bfs를 이용해서, visited의 수를 점점 증가시키는 식으로 문제를 해결하였다. 이 과정에서, xy좌표값을 직접 계산해서 올바를 경우에만 전진시키는 식의 알고리즘으로 계산하였다. 추가로, 처음에 input을 문자열로 받아야하는데, 이는 c++의 string을 이용하

적록색약일때는 R과 G를 같은 취급, 일반인은 다른 취급을 해주는 bfs 문제로, 어렵지 않게 해결할 수 있었다!

bfs를 이용해서 손쉽게 문제를 해결할 수 있었다. 골드치고는 쉬운 문제였는데,이런 식으로, 내가 다음 주사위를 굴려서 갈 곳에 뱀이나 사다리가 있을 경우, 위 코드처럼 2개의 visited를 체크해주는 식으로 문제를 해결하였고,그게 아닐 경우에는, 그냥 평범하게 주사

최근들어, 이분 탐색 부분에 대한 알고리즘에 다소 약한 것 같아, 이분 탐색 관련 알고리즘 문제들을 찾아서 풀고 있다. 이 문제도, 숫자의 범위가 정말 정말 컸기에, long long으로 정의 해주었다는 점과, 내가 초기에 다소 고생했던 부분은, 이분탐색에서 왼쪽값,

로직 자체는 어렵지 않지만, 처리해줘야할 것이 너무 많아서 좀 시간을 많이 썻던 문제다..! 이게 카카오 인턴 문제구나 싶었고..가장 중요한 로직은0 다이얼을 처리해주기 위해서다음과 같은 로직을 통해서, 10,11,12 라는 다이얼을 하나 더 있는 것으로 가상화하였다.

백트래킹을 이용한 간단한 쉬운 문제이지만, 백트래킹 분야에 약간 어려움을 겪는 것 같아서, 쉬운 문제부터 차근차근 풀어보았다.먼저 기본적인 백트래킹으로 ans 배열에 각 요소들을 넣는 간단한 형식이지만 이 문제에서는 각자의 자연수가 모두 다른 수라는 조건이 있다.이를

노가다에 가까운 BFS 문제였다...먼저, 기본적인 BFS 문제 개념에, 3차원 박스에서의 토마토가 익어가는 과정을 생각해서, 3차원 배열과 그리고 6개의 방향으로 향할 수 있게 6개의 direc을 만들어주었다.그리고 흔히 접할 수 있는 BFS 문제와 달리, visit

간단하게 문제를 해결할 수 있었다. 그저, i번째 수의 DP를 계산할떄는, i 이후의 DP중에 최댓값을 찾아서, 그 최댓값에 1을 더해주는 식으로 간단하게 풀 수 있었다.

전형적인 다익스트라 알고리즘을 이용한 문제였다. 정말 정석적인 C++로 다익스트라 알고리즘 구현하기 방식이였는데, 이 문제에서는 Node의 숫자가 생각보다 많았기에, 시간 초과를 줄이기위한 중복 처리가 필요했다.그래서 내가 생각한 방법이, 몰론 dist의 값을 비교하는

내가 푼 BFS 문제중 가장 골치 아팠다.. 해결방법은, 상어가 한마리를 잡아먹을 때마다 bfs 새로 돌려주고, 또 그 안에서 minx와 miny를 통해 상어가 위쪽과 왼쪽을 먼저 먹을 수 있도록 해주었다. 정말 섬세한 상어다..

처음 이 문제를 봤을때는 당연히 BFS, DFS 문제일 것 같지만, 사실은 그렇지 않다. 이 문제에서 우리가 생각해야할 것은 단순히 x축 y축 좌표를 이용해서 거리를 계산해야하는 것이기에, 이미 건설되어 있는 치킨집 중에서 M개를 뽑고, 그 M개에 대한 House