코딩테스트

삽입, 삭제

Disjoint = 교집합이 공집합인 상황make-set(u): u하나인 집합 하나 만들기find-set(u): u가 들어있는 집합의 root를 returnunion(u,v): 두집합을 합쳐주세요p\[u]: u번 요소의 부모의 Index를 return

모든 노드를 덮었고, 간선갯수 = 노드개수-1input graphspaning tree는 이 input그래프를 바탕으로 사이클이 없는 트리를 만들어내는 것input tree: 방향없고, 가중치 있음, 모든요소가 연결되어있음cost: 선분에 대한 값들의 합프림 알고리즘크

방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다(그리디 알고리즘).해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(다이나믹 프로그래밍).모든 노드를 방문하면 종료 -> 노드개수만큼 반복1\. 최소지점을 선택한다값이 max_integer가 아니라는것은

인접행렬로 풀었었다. 그런데 인접행렬로풀면 메모리 + 시간이 오래걸린다(nxn번을 다 확인해야하니)인접행렬말고 이웃한것들만 리스트로 저장하면 훨씬 메모리 + 시간절약이된다

https://dev-dain.tistory.com/155위의 커리큘럼대로 진행하여 대략 100개정도의 문제를 2-3달 안에 푸는것을 목표로 정했다.쉬운문제는 하루에 세문제, 어려운문제가껴있다면 하루에 두문제 정도로 한다.다음과 같이 주어진다sliver: 40

시간복잡도: 최악의 경우를 생각했을때 n^2으로도 풀 수 있다.문제는 n개 수가 각자 소수인지를 찾아야한다. 각 수는 1000이하의 수이다. 그러면최악의 경우의 수를 생각해보면1000번까지의소수판별을 100회를 진행해야한다.즉, 1000000정도의 시간이 필요하다. 1

24 18둘중 작은 수를 택한다(18)작은수~1까지 반복하여 24를 나눈다.나눠지는 가장 첫번째수가 최대공약수 -> 6최소공배수구하는 방법\-> 둘중 하나의 수 x 나머지수/최대공약수\-> 시간복잡도는 O(n), 공간복잡도는 O(1)안에 끝난다

11653 소인수분해 9020 골드바흐추측 처음시도 두번째 시도(정답)

부분수열알고리즘을 어떻게만들지?일단은 뭐든간 정렬뒤에 부분수열을 만들것같긴한데..

이전처럼 푸는문제라고생각했다.근데 이번에는 순서를 바꿔야하는 문제이다.예전에는 "조합"을 풀었다면 이번엔 "순열"을 계산해야하는문제였다.둘의 차이는 알지만 코드적으로는 어떤차이가있을까?에 대해 궁금해졌다.기존코드를 분석해보자.이코드는 왜 조합에는 사용가능하지만 순열에서

1 21 31 42 12 32 43 13 23 44 14 24 3오름차순으로 고르기만 하는것1 21 31 42 32 43 4isPrinted\[i] 의 유무for문이 1부터 시작하느냐 idx부터 시작하느냐의 차이for문이 idx부터 시작하고, idx는 매번 재귀호출때

1초가 100 000 000번의 연산이니 0.5초는 50 000 000.에라토스테네스의 체 + while문 연산nlon(logn)대략 1 000 000 x 상수 + O(n)1 000 000정도니까 시간안에 완료될것같다1초후에 1칸을 간다고 치면 동생을 찾을수있긴하다.근

자세히보면 () 에서만 레이저가 나가고 있다.)앞에 (가 있다면 레이저가 나가는것이고, 레이저가 나가면 여러 나무조각을 자르게 된다. 그 나무조각은 앞에 (의 개수만큼이다또한 ))이 연속으로 나오게 된다면 그것은 나무조각이 하나 더생김을 의미한다. 나무조각이 하나더생기

배열로 풀면안되는 문제다. 왜냐하면 문자열이 n개고 명령어가 m개일때 매번 대략n개정도의 이동이 m번일어난다고 가정할때 nm정도의 연산이 필요한데 그럼 1억번을 넘기기 때문이다.배열말고 연결리스트로 구현해야할듯하다.중간에 있는 요소를 삭제하는 기능중간에 어떤 데이터를

처음 이문제를 봤을땐 stack으로 왜풀어야하는지 잘모르겠었다.가장큰숫자가 되려면각 숫자를 num\[]에 저장한다고 가정했을떄num\[i-1] 과 num\[i]를 비교하여 만약에 뒤에나오는것이 더 크다면isPrint\[i-1] = false;를 춰서 후에 이 boole

11866 1966: 프린터 큐

두 수를 비교하는 방식만 다른것이지 로직은 똑같다위의 코드에서 compage이라는 메서드를띠로 정의하기만하면된다

처음시도는 맞았지만 여러 메서드를 정의해서 메서드를 stack에 쌓고 하면 시간이 조금 더들어서그런건지?(유의미하게 시간이 더 걸리는 지는 잘 모르겠다) 시간초과가 뜬다s대신 e를 사용해도는 되지만 왜 시간초과가 뜨는진 잘 모르겠다조금더 시간이 널널한 문제(2750)에

왜시간 초과가 나는지 모르겠었다flush를 해서 제대로 함수가 종료된줄알았는데 아니였다while문을 계속돌고있었다for문을 돌면서 분명 isRepeat에 false가 넣어졌을것이다그런데 나중에 12345여도, isRepeat가 true로 변경되는 일이 없기때문에 계속w

왜시간 초과가 나는지 모르겠었다flush를 해서 제대로 함수가 종료된줄알았는데 아니였다while문을 계속돌고있었다for문을 돌면서 분명 isRepeat에 false가 넣어졌을것이다그런데 나중에 12345여도, isRepeat가 true로 변경되는 일이 없기때문에 계속w

피보나치를 재귀를 활용하면 2^n이지만 dp를 사용하면 o(n)에 끝낼 수 있다\-> 재귀를 하나 들어갈때마다 값이 결정된다.재귀를 n번들어가면 n개의 값이 결정되고, 그렇기때문에 o(n)에 풀수있다이 문제는 2^40이 되면 시간초과가 나기때문에 dp를 사용해야한다

(A+B+C+D)%E = A%E + B%E + C%E + D%E즉, 다 더한다음에 E로 나누면 overflow나니까 계산결과가 나올때마다E로 나눠준다숫자를 하나씩 만들어간다고 생각하자. 가장중요한 수는 맨뒷자리수다. 맨뒷자리수가 무엇이냐에 따라 다음에 올 수가 결정된다

idx=1일때를 생각해보면idx=1일때 결과가 1 하나만 출력이돼야한다. 근데 1일떄 1,2,3모두 출력된다.이런식이면 idx=2일때도 결과가 출력된다는얘기다. 그러므로 이 코드는 틀렸다.그리고 remove의 위치도 문제가된다.size=m일때만 제거를 하는것이니 1로출

저코드가 있으면 안되는 이유는 일단 q에 넣은 값을 start로 잡아야하는데 start에 대해서 두번 검색을 하기때문이다. 일단 생각한것이랑 다르게 동작하고 있으므로 오답이 나올 수 있다.

18352 한노드 -> 다른노드로 가는 최단경로 + 가중치 양수 -> 다익스트라 11404 왜 숫자범위 적당히 크게 하면되는거지. 어느정도인지 내가 어떻게 알지? 어느정도까지 크게해야하는지 어떻게알지?

distance범위주의distance는 최대 몇인지를 잘 모르겠다.;

가장최소값만을 찾는데.. 가장최솟값만을 찾는게 합이 최소인것을 보장해주지않을때도있을것같다왜냐하면 가장최솟값을 visited처리해줌으로써 그다음 최솟값을 처리못할수도있기때문에 합이 최소인것을 찾기위해선 저코드말고 다르게 짜야할것같다.

xm == ynXm 위치와 Yn 위치의 문자가 동일하면 두 시퀀스에서 공통 문자를 찾았다는 의미입니다.LCSi-1 테이블의 "이전 대각선 값"은 (m-1)번째 및 (n-1)번째 문자까지 두 시퀀스의 LCS 길이를 나타냅니다. m번째 및 n번째 위치에서 일치 항목을 찾았

목적: 큐사용해서 구현해보기stack사용해서 구현해보기퀵정렬, 계수정렬 구현법 알아와오기대충 유형만 파악해보기(한점~다른점까지의 최소 거리)모든 경로의 최단경로가 n\*n매트릭스에 저장됨전체 빅오는 n^3

처음 이 문제를 그냥 BFS로 풀려고 하니 답이 안나왔다. 왜냐하면 대륙1, 대륙2, 대륙3은 서로 다른 대륙이기에 동시에 진행해버리면 서로 서로에게 가까워지면서 실제 시간보다 빠르게 나오기때문이다. 독립적인 실행이 가능하게 해야했다. 즉, 대륙1에서만 BFS를 진행하