baekjoon
1.백준 14003 가장 긴 증가하는 부분 수열 5
백준 14003 <-클릭LIS알고리즘을 사용하여 최장 증가 수열을 구하는 문제이다. 1부터 5까지 있는데 5부터 풀어봤다. 1~4를 모두 확인한 것은 아니지만 기본적으로 같은 문제이고, 대신 테스트케이스의 조건이 달랐다. 해당 문제를 dp로 풀게되면 $$O$$($
2.백준 2098 TSP
백준 2098<-클릭유명한 TSP문제이다. TSP문제는 DP와 DFS로 해결 가능한데 DP로 해결하였다.DP와 더불어 방문 예정 도시를 표시하기 위해 비트 마스크를 사용하였다. 이 문제에서 도시의 개수는 16개로 제한지만 계산 중 오버플로우를 방지하기 위해 17자
3.백준 17387 CCW
백준 17387 ←클릭 CCW를 활용한 문제이다. CCW는 counter clock wise로 점 3개가 있을 때 이 점 3개를 이은 선의 방향을 알 수 있다. 방향을 알 수 있는 원리는 간단한데, 한 점을 기준으로 나머지 두 점을 잇는 직선 두개를 그린 다음, 외적
4.백준 9084 동전
백준 9084 ← 클릭 dp를 활용한 문제이다. 변수 설정 coin: 동전의 값을 저장한 배열 dp: dp배열 아이디어 > * k원을 만들기 위해서 k-n원 +n원이 필요하다 > * for문을 돌며 모든 동전에 대해 dp배열을 업데이트 한다. 예시 동전의 개수
5.백준 2504 괄호의 값
백준 2504 ←클릭스택을 활용한 문제이다. op_s: 연산자를 저장하는 스택이다.num_s: 숫자를 저장하는 스택이다. cur_s: 현재 사용하는 스택의 번호를 저장하는 변수이다. 처음에 -1로 초기화 되어있다. v: 괄호를 저장하는 스택인데 input으로 받은 문자
6.백준 17298 오큰수
백준 17498←클릭arr: 입력 배열rst: 결과값 저장 배열s: 스택배열의 맨 오른쪽 값부터 시작하여 왼쪽과 비교한다. 배열의 값 arr\[i]와 s.top()을 비교하여 arr\[i]가 더 작으면 rst\[i]에 s.top()을 삽입배열의 값 arr\[i]와 s.
7.백준 1007 벡터 매칭
백준 1007 ←클릭벡터 매칭 문제이다. 조합을 사용하여 문제를 해결하면 brute-force 알고리즘에 비해 시간 복잡도를 상당히 줄일 수 있다.P: 점들을 저장하는 벡터minimum : 최소값을 저장b: bool값을 저장하는 벡터. 조합 구현시 사용sel: $$nC
8.백준 12100 2048(Easy)
백준 12100←클릭DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다.n: 현재 DFS의 층에 해당한다. d: 움직임의 종류이다. 0부
9.백준 2470 두 용액
백준 2470←클릭투 포인터를 사용하는 문제이다. 배열을 오름차순으로 정렬하여 투 포인터를 사용하면 쉽게 풀린다. arr: 전체 배열left: 왼쪽 포인터right: 오른쪽 포인터left_ans: 작은 정답값right_ans: 큰 정답값배열을 오름차순으로 정렬한다. 배
10.백준 1561 놀이 공원
백준 1561 ←클릭 rmd_sum: t분 후 남아있는 아이의 수 이다. floor: t = floor와 t=floor+1 사이에서 모든 아이가 탑승함. left : 이분 탐색의 왼쪽 포인터right: 이분 탐색의 오른쪽 포인터mid: 이분 탐색을 위한 중간 포인터N
11.백준 2618 경찰차
백준 2618 ←클릭min_dist\[a]\[b]: 경찰차 1이 a위치, 경찰차 2가 b위치에 있을 때의 최소 거리를 저장하는 dp배열next_e: 다음에 발생하는 사건 번호dist_k: 경찰차 k가 사건 위치로 이동할 때 드는 거리 비용rstk: 경찰차 k가 이동 하
12.백준 13141 Ignition
백준 13141 ←클릭dist: 플로이드 와샬 알고리즘을 수행한 결과값 저장 배열lines: 간선의 정보 저장INFO: 간선의 정보를 저장하기 위한 구조체, S(시작점), E(끝점), L(길이)로 구성max_len: 특정 노드에서 시작한 경우 해당 그래프를 모두 지우
13.백준 1854 K번째 최단경로 찾기
백준 1854←클릭town_dist\[k]: k번째 마을까지 가는 거리를 저장한 우선순위 큐. size는 k로 제한하고, 내림차순이기 때문에 top()은 k번째로 가까운 거리가 유지된다. dist\[from]\[to]:from에서 to까지 간선의 길이 저장pq: 시작
14.백준 9376 탈옥
백준 9376←클릭죄수 2명과 상근이의 위치를 기준으로 다익스트라를 적용하여 지도의 각 위치까지의 최소 거리를 모두 구한다. 지도의 특정 위치에서 세 최소 거리의 합은 해당 위치까지 상근이와 죄수 2명이 최소 거리로 이동했을 때 드는 비용이다. 특정 위치에 문이 있을
15.16496 큰 수 만들기
백준 16496 ←클릭nums\[i] : 입력된 수의 각 자리 숫자 저장cnt : 입력된 수가 몇자리 수인지pq: 정렬을 위한 우선순위 큐입력 숫자에 대해서 10자리까지 계속 반복하는 새로운 수를 만든다.예를 들어 100이면 100 100 100 1으로 반복하여 100
16.백준 10800 컬러볼
백준 10800 ←클릭total : 현재까지 모두 더한 전체 공의 무게 합now_total :자신보다 작은 전체 공의 무게 합 + 자신의 무게c_arr\[color] : 현재까지 특정 color에 대한 모든 무게 합공들을 무게와 색을 기준으로 오름차순먹을 수 있는 공의
17.백준 15591 MooTube (Silver)
백준 15591←클릭간선의 갯수가 N-1개 이므로 특정 지점에서 출발하였을 경우 다른 노드를 2번 방문할 일은 없다. 고로 단순 BFS로 구현 가능하다. BFS를 통해 mid를 계속 갱신한다. min_diststart = min(min_diststart, dist);여
18.백준 21609 상어중학교
백준 21609←클릭구현문제로 엄청 시간이 많이 들었다. 순서는 대략 다음과 같다. for문을 돌며 방문 처리가 안된 좌표에서 DFS를 진행한다. DFS를 통해 가장 큰 블록 집합 탐색무지개 블록은 방문처리를 해제DFS가 끝날때마다 조건을 기준으로 블록 집합을 갱신할지