Algorithm

최대공약수약수 구하기입력받은 두 수의 최대공약수를 구해준 후 최대공약수의 약수들을 구해주면 된다.사과의 개수가 최대 10억 이므로 최대공약수를 구한 후 약수를 찾을 때 for문의 범위를 최대공약수의 제곱근까지 봐주면 최악 10억을 연산 횟수를 약

동적계획법dpi = {i번째 년도의 별레 수, i번째 년도에 죽을 벌레 수}

필요한 지식힙접근한 상태에서 가능한 3가지 경우가 있다.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.화면에 있는 모티콘 중 하나를 삭제한다.한 상태에서 가능한 3가지 경우를 모두 봐주고 힙에 넣어준다.힙

SET시뮬레이션예전에 풀었던 문제였지만 너무 괴랄한 코드를 작성했었기에 다시 풀어보았다.아래는 예전에 제출했던 괴랄한 코드이다. 해석조차 힘들다.이번에 풀떄는 한 세대가 증가할 때의 규칙을 이용하여 풀었다.드레곤 커브의 좌표가 아닌 방향을 저장해간다고 했을 때, 1세대

구현

BFS시뮬레이션이 문제는 1년전 즈음 시험 볼 당시 문제를 똑바로 읽지 않아 3가지 이동방향이 아닌 8 방향으로 내마음 대로 해석하고 총 24가지의 경우를 작성해 버렸던 문제이다.다시는 그런 실수 안해야지파이프의 뒤,앞 2개의 좌표를 가진 구조체를 선언하고 사용가로에선

힙조합시뮬레이션완전탐색구현조합으로 3명의 궁수를 중복되지 않게 배치한다.3명의 궁수의 적을 선택한다.궁수 한명 선택모든 적을 탐색 && 힙에 넣어주기힙의 top은 거리가 가장 가까운, 같다면 가장 왼쪽에 있는 적이 있다.그 적을 따로 저장 해 준후 모든 궁수에 대해 과

완전탐색연산을 앞에서 부터 해주므로 앞에서 부터 연산자와 숫자를 한 단위로 보면서 재귀로 완전탐색한다.연산자와 숫자를 한단위로 볼때 가능한 연산의 경우는 두가지 이다.현재 숫자를 괄호치지 않고 이때까지 계산한 값과 연산하는 경우현재 숫자와 다음숫자를 괄호를 치고 이때까

백트래킹문제에서 제시하는 주의해야 할 조건들은0이 적힌 칸에는 색종이가 있으면 안된다.색종이는 각 크기별로 5개씩 가지고 있다.최소의 종이수가 필요하다.정도 이다.입력이 10X10 정도밖에 안되므로 한 칸마다 종이를 놓아가면서 모두 봐주면되는데 가짓수를 줄이기 위해 아

시뮬레이션조합선수들을 4번째 자리를 제외하고 가능한 모든 선수배치 방법을 구한다.그 선수 배치에 따른 점수를 계산한다.모든 선수배치방법에 따라 결과의 최대값을 저장하며 반복한다.chk\[i]=j : i번째 순서의 선수번호는 j이다.game\[i]\[j]=k : i-1

시뮬레이션조합완전탐색연산들의 조합을 구한다.연산들의 조합이 정해지면 연산을 순서대로 수행한다.배열 A 값을 업데이트 한다.모든 연산들의 조합에 따라 반복한다.per(i) : 1번째 연산의 자리를 찾음. 모든 연산이 자리를 찾을때까지 재귀적으로 탐색하며 연산들의 조합을

DFS조합완전탐색지역들이 선거구 2개에 나눠지는 조합을 구한다.조합을 구할 때 마다 문제에서 요구하는 조건을 체크한다.각 선거구는 적어도 하나의 지역을 포함한다.모든 지역은 2개의 선거구에 무조건 포함되어야 한다.같은 선거구 끼리는 인접해야한다.1에서 구한 조합이 위의

그래프 탐색유니온 파인드시뮬레이션MST섬에 번호를 매겨준다.각 섬에서 다리를 놓았을 때 문제에서 요구하는 조건을 만족하며 다른 섬에 도달할 수 있다면 힙에 넣어준다.힙에 있는 것을 거리가 짧은 순으로 꺼내며 union-find를 이용하여 MST를 구성한다.image

라인스위핑좌 2칸 중 최대 높이(lt), 우 2칸 중 최대 높이(rt)를 구한 후 현재 위치한 빌딩의 높이와 비교한다.lt 와 rt의 최대값이 현재빌딩의 높이보다 낮다면 그 차이값이 조망권을 획득한 세대 수 가 된다. image

Multiset최대를 바로 확인할수 있는 SET하나 최소를 바로 확인할 수 있는 SET하나를 가지고 있는다.(원소가 중복될 수 있으므로 Multiset 을 사용)평탄화를 더이상 진행할 수 없을 조건을 검사해주고 평탄화를 계속 반복한다.평탄화 작업은 첫번째 원소를 era

필요한 지식 구현 코드(C++)

필요한 지식 구현 코드(C++)

조합재귀재귀로 n/2개를 선택하고 그때의 값을 계산해 준다.조합의 가짓수를 줄이기 위해 첫 번째 깊이에서 i를 선택했다면 그 다음 깊이에선 i보다 큰수만 선택하게 해서 중복으로 체크하지 않게한다.조합next_permutation첫 번째 방법과 다르지않다. next_pe

이분탐색이분탐색의 mid값을 한 그룹의 최대 숫자의 합으로 두고 이분탐색을 진행한다.mid값을 정하고 그 값으로 구슬이 저장된 벡터를 돌면서 mid값을 넘지않게 그룹으로 나누었을때 몇개의 그룹으로 나뉘는지 체크한다.정확히 m개의 그룹으로 나뉘었거나, m개보다 적은 수의

시뮬레이션Deque머리는 항상 1칸씩 이동하지만, 사과의 먹냐 안먹냐에따라 꼬리가 제자리에있거나 이동한다. 머리와 꼬리에 둘다 접근이 가능해야한다.뱀이 자기 몸에 박거나 벽에 박으면 게임이 종료된다. 자기 몸에 박는경우를 찾아줘야하므로 뱀의 몸 좌표들을 가지고있어야한다

완전탐색첫 날의 떡 개수와 둘쨋날의 떡 개수를 정해주고 d일 까지 진행하고 k와 같은지 비교한다.

이분탐색이분탐색의 mid값을 파닭에 넣을수 있는 최대 파의 길이로 정의하고 진행한다.입력받을때 파의 길이 중 최대값을 저장해 두고, mid값이 저장한 최대값 보다 크다면 right를 mid-1로 바꿔주고 다음단계로 진행한다.2번 조건을 만족하는 경우 모든 파의 길이를

동적계획법점화식dpi = dpi-1+dpi-2+dpi-3dpi : i를 1,2,3 의 합으로 나태내는 방법의 수i가 1,2,3 일경우 각각 1,2,4로 초기화 시켜준다.

완전탐색n이 11까지 밖에 안되므로 재귀로 완전탐색한다.vector에 선택되는 한가지 숫자를 계속 넣어주면서 진행하다가 k번째가 된다면 재귀를 빠져나와 vector에 저장된 수를 거꾸로 꺼내준다.

동적계획법n이 1,000,000 까지 커졌다.점화식dpi = dpi-1+dpi-2+dpi-3dpi : i를 1,2,3 의 합으로 나태내는 방법의 수i가 1,2,3 일경우 각각 1,2,4로 초기화 시켜준다.

동적계획법n이 10,000 까지.순서만 다른것은 같은 것으로 친다.점화식dpi = dpi - 1dpi = dpi - 2 + dpi - 2dpi = dpi - 3 + dpi - 3 + dpi - 3dp\[i]\[j] : i의 합이 j+1로 끝나는 경우의 수dp\[i]\[

동적계획법n이 100,000 까지.같은수를 두번 이상 연속해서 사용하면 안된다.점화식dp\[i]\[j] : i의 합이 j+1로 끝나는 경우의 수i가 1로 끝났을 경우 dp\[i-1]\[1]과 dp\[i-1]\[2]를 더한 값을 가진다.i가 2로 끝났을 경우 dp\[i-

동적계획법n이 100,000 까지.합이 대칭을 이루어야한다.점화식dp\[i] : i의 합을 1,2,3을 이용하여 대칭을 이루게 한 경우의 수i가 1로 끝났을 경우 dp\[i-2]을 더한 값을 가진다.i가 2로 끝났을 경우 dp\[i-4]을 더한 값을 가진다.i가 3으로

동적계획법n이 1,000 까지, m도 1,000까지n을 1,2,3의 합으로 나타냈을 때 사용한 수의 개수가 m개인 경우의 수를 구해야한다.점화식dp\[i]\[j] : i의 합을 1,2,3을 이용하여 j개로 나타낸 경우의 수i가 j개의 숫자로 나타낸 경우는i가 1로 끝났

동적계획법n이 100,000 까지n을 1,2,3의 합으로 나타냈을 때 사용한 숫자가 홀수개, 짝수개 인 경우의 수를 구분하여 출력해야한다.점화식dp\[i]\[0] : i의 합을 1,2,3을 이용하여 홀수개로 나타낸 경우의 수dp\[i]\[1] : i의 합을 1,2,3을

동적계획법n이 1,000 까지, m도 1,000까지n을 1,2,3의 합으로 나타냈을 때 사용한 수의 개수가 m개 이하인 경우의 수를 구해야한다.점화식dp\[i]\[j] : i의 합을 1,2,3을 이용하여 j개로 나타낸 경우의 수i가 j개의 숫자로 나타낸 경우(dp\[i

동적계획법그래프 탐색으로 가능한 모든 문자열을 탐색 후 각 문자열을 검사해 주면 시간초과 & 메모리초과 이다.dp\[i]\[j]의 값은 dp\[i]\[j]로 올 수 있는 dp\[i]\[j-1] 과 dp\[i-1]\[j]의 값중 최대 값을 저장한다.dp\[i]\[j]에

구현a<b 인 경우 a-b가 홀수인경우는 1을 출력하고 짝수인 경우는 2를 출력한다.a>b 인경우 b-a가 홀수인경우 2를 짝수인경우 1을 출력한다.a==b 인경우 0을 출력한다.구현버블 소트버블 소트를 진행 하되, P배열에 있는 원소를 확인 후, 현재 자리를 s

분할정복을 이용한 거듭제곱i번째 징검다리 까지 가는 방법이 2^(n-2)가지가 나온다는 것을 찾는다.i가 1,2 인경우는 예외처리 해주고 나머지 경우는 2^(n-2)를 구해 출력한다.n의 범위가 10억 까지 이므로 거듭제곱을 구해줄 때 분할정복을 이용하여 O(log n

시뮬레이션구멍을 기준으로 좌/우 를 봐준다.구멍이 선분으로 주어지는데 (x1,y1,x2,y2) 여기서 필요한 건 x1하나이다. 처음 코드를 작성할 때에는 4가지를 모두 사용하도록 구현했었는데 x1하나만 사용하므로써 코드가 많이 간결해지고 구현이 난이도가 많이 줄어든다.

정수론에라토스테네스의 체로 소수를 하나씩 선택하고(i), k를 i로 나누며 k의 소인수중 i를 밑으로 가지는 지수를 kcnt변수에 저장해 준다.그리고 그 kcnt의 수가 0이상이라면 n!가 밑을 i로 가지는 지수를 mcnt에 저장한다.이때 mcnt의 개수는 아래와 같은

교란순열교란순열을 처음 알게된 문제다.각 행과 열에는 빨간색과 파란색이 한번씩만 칠해져야할때, 모든경우의 수를 1e9+7로 모듈러 연산한 값을 출력해야한다.먼저 파란색만 행과 열이 겹치지 않게 칠한다고 했을 때 n X (n-1) X (n-2) X ... X 1 = n!

다익스트라정말 오랜만에 푸는 다익스트라 문제였다.문제에선 면접장까지 거리가 가장 먼 도시의 번호를 출력하라고 하지만 입력으로는 면접장으로 향하는 단방향 길들을 주기때문에 입력의 U와 V를 뒤집어서 저장해준다.dist 배열을 면접장이 위치하는 도시는 0으로 아니라면 1e

동적계획법dp\[i]\[j]\[k] : i번째 날, j번의 청소남음, 마지막청소했던 날 k 로 dp테이블을 구성했다.arr\[i] : i번째 날 방문하는 사람 수재귀로 끝까지 내려갔다고 올라오면서 답을 내는 방식으로 구현했다.go(now,cnt,state,dust) :

수학n의 배수중 1로만 이루어진 수중 가장 작은 자릿수를 출력해야한다. 없다면 -1을 출력한다.불가능한 경우는 1로만 이루어진 수는 약수로 2와5를 가지고있지 않다. 그러므로 n을 입력받을 때에 2나5로 나누어떨어진다면 -1을 출력해준다.1로만 이루어진 배수를 구해줄

구간합완전탐색의 접근은 시간초과다.빠른 연산을 위해 구간합 배열을 가지고 있어야하는데, 이 문제의 경우 원형으로 이어져있다. 따라서 구간합 배열의 길이를 2\*n만큼 구성하고 값을 채워준다.이렇게 구간합 배열을 구성하고 나면 1번지점 에서 3번 지점까지 시계방향으로 가

동적계획법왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나 비어있을때의 경우의 수를 구해줘야한다.n이 7인경우 경우의 수는 아래와 같다.n의 재귀적인 팰린드롬 파티션에서 정가운데에 오는 숫자가 i 일때 양 옆으로 올수 있는 재귀적인 팰린드롬은 (n-i/2)의 재귀적인

동적계획법먼저 n번째 추는 1~n-번째 추들의 무게의 합보다 크다라는 점을 알아야한다.n+1번째 추가 놓이는 경우는 크게 2가지로 구분할 수 있다. 1\. 1~n번째 추가 놓여있고, 마지막으로 오른쪽에 놓이는 경우 2\. 마지막이 아니고 오른쪽에 놓이는 경우(n+1

완전탐색입력받은 수열 B에 존재하는 원소들로 하나씩 시작해보면서 나3,곱2연산이 가능하다면(수열B에 원소가 존재한다면) 재귀적으로 연산을 수행한다.image

구현최고 높이에서 현재 높이를 뺀 값중 홀수가 하나라도 존재하면 2X1블럭을 아무리 배치해도 모든 블럭을 삭제할 수 없다.구현순서를 고려하여 3개의 원소를 뽑았을 때, 그 3개의 숫자가 팰린드롬인지 확인한다.단순히 N^2도 가능하지만 중간의 원소는 무엇이 와도 상관이

BFS체크배열을 chk\[k]\[i]\[j] : k번째 말처럼 이동할 수 있는 횟수가 남았을때 i,j 칸에 도달 했는지 여부로 정의하고 BFS를 수행한다.그 칸에 최소의 횟수로 도달했다고해서 마지막칸에 최소의 이동횟수로 도달 할 수 있는건 아니다.image

최대 공약수(0,0) 에서 보이는 점의 개수를 찾아야한다.두점을 비교한다고 가정했을 때 (0,0)에서 선을 그어보면 그 선분이 겹치면 둘 중 하나의 점은 (0,0)에서 볼수가 없는 점이다.선분이 겹친다는 의미는 기울기가 같다는의미 이며, 그 기울기가 같은 선분중 (0

동적계획법그들을 일렬로 세울 때, 맨 끝 두 병사를 제외한 나머지 병사들의 양 옆 두 병사의 키가 자신 보다 크거나 모두 자신보다 작도록 배치하는 경우의 수를 구해야 한다.양 옆보다 작은 수를 ▲ 양옆보다 큰수를 ●, 추가하려고 하는 수를 X 라고 표시하면 i번째 상태

수학BFS수의 길이가 100이하 까지 이다. 수를 표현할 다른방법이 필요하다.String 형식으로 수를 표현한다.입력받은 N의 배수 이면서 조건들을 만족해야한다.단순히 N의 배수를 계속 곱하다 보면 자료형의 범위를 초과 하므로 다른 방법이 필요하다.N의 배수를 구해 줄

동적계획법n이 10,000 이므로 $O(n^2)$ 까지 생각해볼수 있다.DP\[i] 를 i번째 건물까지 포함했을 때의 최소 비용 으로 정의했다.$DPi = min\[ DPj + max(vi.x-vj.x, maxHeight\*2) , for(j:0~i-1)]$ 의 점화식

동적계획법DP\[i]\[x]\[y]\[z]\[d]:i번째 인덱스를 x번, i+1인덱스를 y번, i+2인덱스를 z번, d방향(0:뒤,1:앞)으로 돌렸을 떄 필요한 최소 회전 수 로 정의 했다.문제 접근에있어서 d가 나타내는 방향성의 필요성에 대해 많이 헷갈렸던 문제다 지

동적계획법완전탐색DPi : i번째 인덱스의 각도까지 사용했을 때 j각도를 사용할수 있는지 여부ANSi : i 각도를 만들수 있는지 여부만들수 있는 각도를 전부 탐색하고 메모이제이션으로 시간을 줄이고 정답을 출력해 준다.DPj의 식으로 메모이제이션을 하면 탐색하는 경우가

완전탐색에라스토테네스의 채SET종이 조각으로 만들수 있는 모든 수를 체크해 준다.만든수가 소수라면 SET에 넣어준다.소수 체크에는 에라스토테네스의 채를 사용했다.image

너무 오랜만에 백준에 들어갔고 알림에 가장 위에떠있는 재채점 후 틀린 문제였다. 진짜 이문제 처음 접했을때가 이제 막 알고리즘이 이런거구나 알아가던 때였는데 세상 반갑고 세상 알고리즘 오랜만에해서 반성 많이 했다.기존의 풀이방식은 a + b + c + d = w 식을

행렬을 가지고 입력받을 때마다 업데이트를 해주는 방식으로 하면 시간복잡도가 3\*(2\*M-1)\*N번(약 4,200,000,000)의 연산이 이루어지므로 시간초과를 받게된다.행렬을 조작하지 않고 행렬의 왼쪽 첫 열과 위쪽 첫 행을 1400 길이의 배열(tmp)로 바꾸

도형을 회전하는 규칙과 스티커 저장방법만 잘 설계하고 구현해내면 해결가능한 문제였다.두개의 구조체를 사용했는데 하나는 좌표를 저장하기위한 구조체 하나는 스티커 정보를 담을 구조체 이다.sticker구조체에서 스티커가 색이 있는 부분을 좌표로 저장하게하고, 이로 인해 9

접근 방정식과 시간복잡도에 대한 고려를 해야하는 문제였다. 먼저 헨리식 표현법의 첫번째 수를 구하는 방법은 아래와 같다. $$\frac{1}{x^{1}} \leq \frac{a}{b}$$ 을 만족하는 최대의 $$x^1$$은 b와 a의 값은 알고있으므로 $$x^1$

N이 20까지 이므로, 완전탐색으로 쉽게 풀 수 있었다.go(idx,sum,cnt)함수의 매개변수는 각각 현재 먹이 인덱스,만족도,탈피에너지이다. - idx까지 진행했을때 다음단계로의 경우의수는 3가지가 있다.현재 먹이를 먹지 않고 그냥 지나가는 경우현재 먹이를 먹으면

20167-꿈틀꿈틀 호석 애벌레 - 기능성 문제의 상위 버전이다.N이 100,000까지 이므로, 완전탐색으로 접근은 불가능하고, 동적계획법을 생각해야했다.dp\[i]를 i번째 먹이까지의 최대 누적 탈피에너지 값으로 정의했다.포인터로 사용할 변수l과 r을 만족도의 함은