baekjoon

백준 14003 <-클릭LIS알고리즘을 사용하여 최장 증가 수열을 구하는 문제이다. 1부터 5까지 있는데 5부터 풀어봤다. 1~4를 모두 확인한 것은 아니지만 기본적으로 같은 문제이고, 대신 테스트케이스의 조건이 달랐다. 해당 문제를 dp로 풀게되면 $$O$$($

백준 2098<-클릭유명한 TSP문제이다. TSP문제는 DP와 DFS로 해결 가능한데 DP로 해결하였다.DP와 더불어 방문 예정 도시를 표시하기 위해 비트 마스크를 사용하였다. 이 문제에서 도시의 개수는 16개로 제한지만 계산 중 오버플로우를 방지하기 위해 17자

백준 17387 ←클릭 CCW를 활용한 문제이다. CCW는 counter clock wise로 점 3개가 있을 때 이 점 3개를 이은 선의 방향을 알 수 있다. 방향을 알 수 있는 원리는 간단한데, 한 점을 기준으로 나머지 두 점을 잇는 직선 두개를 그린 다음, 외적

백준 9084 ← 클릭 dp를 활용한 문제이다. 변수 설정 coin: 동전의 값을 저장한 배열 dp: dp배열 아이디어 > * k원을 만들기 위해서 k-n원 +n원이 필요하다 > * for문을 돌며 모든 동전에 대해 dp배열을 업데이트 한다. 예시 동전의 개수

백준 2504 ←클릭스택을 활용한 문제이다. op_s: 연산자를 저장하는 스택이다.num_s: 숫자를 저장하는 스택이다. cur_s: 현재 사용하는 스택의 번호를 저장하는 변수이다. 처음에 -1로 초기화 되어있다. v: 괄호를 저장하는 스택인데 input으로 받은 문자

백준 17498←클릭arr: 입력 배열rst: 결과값 저장 배열s: 스택배열의 맨 오른쪽 값부터 시작하여 왼쪽과 비교한다. 배열의 값 arr\[i]와 s.top()을 비교하여 arr\[i]가 더 작으면 rst\[i]에 s.top()을 삽입배열의 값 arr\[i]와 s.

백준 1007 ←클릭벡터 매칭 문제이다. 조합을 사용하여 문제를 해결하면 brute-force 알고리즘에 비해 시간 복잡도를 상당히 줄일 수 있다.P: 점들을 저장하는 벡터minimum : 최소값을 저장b: bool값을 저장하는 벡터. 조합 구현시 사용sel: $$nC

백준 12100←클릭DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다.n: 현재 DFS의 층에 해당한다. d: 움직임의 종류이다. 0부

백준 2470←클릭투 포인터를 사용하는 문제이다. 배열을 오름차순으로 정렬하여 투 포인터를 사용하면 쉽게 풀린다. arr: 전체 배열left: 왼쪽 포인터right: 오른쪽 포인터left_ans: 작은 정답값right_ans: 큰 정답값배열을 오름차순으로 정렬한다. 배

백준 1561 ←클릭 rmd_sum: t분 후 남아있는 아이의 수 이다. floor: t = floor와 t=floor+1 사이에서 모든 아이가 탑승함. left : 이분 탐색의 왼쪽 포인터right: 이분 탐색의 오른쪽 포인터mid: 이분 탐색을 위한 중간 포인터N

백준 2618 ←클릭min_dist\[a]\[b]: 경찰차 1이 a위치, 경찰차 2가 b위치에 있을 때의 최소 거리를 저장하는 dp배열next_e: 다음에 발생하는 사건 번호dist_k: 경찰차 k가 사건 위치로 이동할 때 드는 거리 비용rstk: 경찰차 k가 이동 하

백준 13141 ←클릭dist: 플로이드 와샬 알고리즘을 수행한 결과값 저장 배열lines: 간선의 정보 저장INFO: 간선의 정보를 저장하기 위한 구조체, S(시작점), E(끝점), L(길이)로 구성max_len: 특정 노드에서 시작한 경우 해당 그래프를 모두 지우

백준 1854←클릭town_dist\[k]: k번째 마을까지 가는 거리를 저장한 우선순위 큐. size는 k로 제한하고, 내림차순이기 때문에 top()은 k번째로 가까운 거리가 유지된다. dist\[from]\[to]:from에서 to까지 간선의 길이 저장pq: 시작

백준 9376←클릭죄수 2명과 상근이의 위치를 기준으로 다익스트라를 적용하여 지도의 각 위치까지의 최소 거리를 모두 구한다. 지도의 특정 위치에서 세 최소 거리의 합은 해당 위치까지 상근이와 죄수 2명이 최소 거리로 이동했을 때 드는 비용이다. 특정 위치에 문이 있을

백준 16496 ←클릭nums\[i] : 입력된 수의 각 자리 숫자 저장cnt : 입력된 수가 몇자리 수인지pq: 정렬을 위한 우선순위 큐입력 숫자에 대해서 10자리까지 계속 반복하는 새로운 수를 만든다.예를 들어 100이면 100 100 100 1으로 반복하여 100

백준 10800 ←클릭total : 현재까지 모두 더한 전체 공의 무게 합now_total :자신보다 작은 전체 공의 무게 합 + 자신의 무게c_arr\[color] : 현재까지 특정 color에 대한 모든 무게 합공들을 무게와 색을 기준으로 오름차순먹을 수 있는 공의

백준 15591←클릭간선의 갯수가 N-1개 이므로 특정 지점에서 출발하였을 경우 다른 노드를 2번 방문할 일은 없다. 고로 단순 BFS로 구현 가능하다. BFS를 통해 mid를 계속 갱신한다. min_diststart = min(min_diststart, dist);여

백준 21609←클릭구현문제로 엄청 시간이 많이 들었다. 순서는 대략 다음과 같다. for문을 돌며 방문 처리가 안된 좌표에서 DFS를 진행한다. DFS를 통해 가장 큰 블록 집합 탐색무지개 블록은 방문처리를 해제DFS가 끝날때마다 조건을 기준으로 블록 집합을 갱신할지

문제 링크이 문제는 그냥 union-find 문제이다. union-find만 구현하면 되지만 c++의 경우 fastio를 적용하지 않으면 시간초과가 난다.

문제 링크이 문제는 union-find를 사용하는 문제이다. 다만 2가지를 고려해야한다. 숫자가 아닌 이름을 주기에 이를 숫자로 바꿀 수 있는 로직이 필요해당 root에 몇 명이 포함되어 있는지 저장하다. 이름을 string으로 바꾸기 위해 map을 사용했고, 이 로직

문제 링크처음에는 좀 해멨는데 투포인터 문제이다.먼저 눈 사람 하나를 만들고(O(N^2)) 투 포인터로 그 눈사람과 최대한 비슷한 크기로 만들면(O(N)) 된다.

문제 링크brute force 문제이다.재귀로 구현하면 된다. vectorToInt함수를 구현하면서 cmath 라이브러리의 pow를 사용했더니 의도대로 동작하지 않는 문제가 생겼었다. pow의 부동소수점 문제인 것 같다.

문제 링크역의 개수가 3000이다. 크지 않기 때문에 모든 노드에 대해서 DFS를 돌리더라도 O(N^2)이므로 시간 초과가 나지 않는다. DFS를 2번 돌렸다.DFS 1 : 특정 노드가 cycle인지 DFS 탐색 도중에 시작 노드를 다시 만나는지 확인을 했다. 모든 간

문제 링크단순 구현 문제이다. BFS로 모든 경로를 탐색하면 된다.방문 처리를 통해 방문했던 노드를 방문하는 것을 방지하면 최대 20만번 탐색하기 때문에 시간초과가 나지 않는다.

문제 링크이 문제는 1번 노드를 제외하고 나머지 노드들을 연결하는 문제이다. MST를 구성하면 되는데 MST를 구성하는 방법은 2가지 이다.크루스칼 알고리즘프림 알고리즘이 중 크루스칼 방법이 구현이 쉽기 때문에 먼저 고려를 하였는데 조건에 만족하기 때문에 크루스칼로 구

문제 링크처음에 위상 정렬 문제인가 했는데 아니다. 1번 노드가 2번 노드보다 크다고 하더라고 1번 노드와 2번 노드 사이에 다른 노드가 올 수 있기 때문이다. 이 문제는 특정 노드의 최소 등수와 최대 등수를 구해야 하므로 특정 노드보다 확실히 큰 노드의 수와 확실히

문제 링크연필을 몇번 떼어야 하는가를 구하는 문제이다.이는 총 몇개의 집합인지를 구해야 하는 문제로 치환된다. 집합의 수를 구한다 -> union-find로 푼다.어떤 사각형을 맞닿아있다고 판단할 지위 2 조건은 B가 A를 완전히 포함하는 경우 / A가 B를 완전히 포

문제 링크어떻게 풀기 고민하는 단계에서 다음과 같은 생각을 했다. Greedy - 가장 연결이 많이 된 노드부터 하나씩 선택연결된 노드의 수가 같은 경우 선택 기준이 애매하다. 예제 1번과 같은 경우 1, 2, 4번 노드가 모두 연결된 노드가 3개다. 위 예제에서는 1