백준 1561 놀이 공원
백준 1561 ←클릭 rmd_sum: t분 후 남아있는 아이의 수 이다. floor: t = floor와 t=floor+1 사이에서 모든 아이가 탑승함. left : 이분 탐색의 왼쪽 포인터right: 이분 탐색의 오른쪽 포인터mid: 이분 탐색을 위한 중간 포인터N
프로그래머스 연속 펄스 부분 수열의 합(dp)
연속 펄스 부분 수열의 합 ←클릭누적 합 이외에 dp를 사용한 문제 풀이이다. new1: 이전 dp배열과 현재 sequence배열의 합이다. dp: dp배열 i번째 인덱스까지 최선의 연속 펄스 부분 수열의 합answer: dp배열의 최대값dp\[0]에 sequence\
프로그래머스 연속 펄스 부분 수열의 합(누적 합)
연속 펄스 부분 수열의 합 ←클릭원래는 다르게 푸는 문제 같지만 쉽게 풀 수 있는 규칙을 찾았고, 다른 사람의 글을 참고하니 누적 합 방법인 것 같다. p_s: pulse_sequence배열으로 원래 배열의 펄스 누적 합이다. p_s\[0]에는 0을 삽입한다. p_s\
백준 2470 두 용액
백준 2470←클릭투 포인터를 사용하는 문제이다. 배열을 오름차순으로 정렬하여 투 포인터를 사용하면 쉽게 풀린다. arr: 전체 배열left: 왼쪽 포인터right: 오른쪽 포인터left_ans: 작은 정답값right_ans: 큰 정답값배열을 오름차순으로 정렬한다. 배
백준 12100 2048(Easy)
백준 12100←클릭DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다.n: 현재 DFS의 층에 해당한다. d: 움직임의 종류이다. 0부
백준 1007 벡터 매칭
백준 1007 ←클릭벡터 매칭 문제이다. 조합을 사용하여 문제를 해결하면 brute-force 알고리즘에 비해 시간 복잡도를 상당히 줄일 수 있다.P: 점들을 저장하는 벡터minimum : 최소값을 저장b: bool값을 저장하는 벡터. 조합 구현시 사용sel: $$nC
백준 17298 오큰수
백준 17498←클릭arr: 입력 배열rst: 결과값 저장 배열s: 스택배열의 맨 오른쪽 값부터 시작하여 왼쪽과 비교한다. 배열의 값 arr\[i]와 s.top()을 비교하여 arr\[i]가 더 작으면 rst\[i]에 s.top()을 삽입배열의 값 arr\[i]와 s.
백준 2504 괄호의 값
백준 2504 ←클릭스택을 활용한 문제이다. op_s: 연산자를 저장하는 스택이다.num_s: 숫자를 저장하는 스택이다. cur_s: 현재 사용하는 스택의 번호를 저장하는 변수이다. 처음에 -1로 초기화 되어있다. v: 괄호를 저장하는 스택인데 input으로 받은 문자
백준 9084 동전
백준 9084 ← 클릭 dp를 활용한 문제이다. 변수 설정 coin: 동전의 값을 저장한 배열 dp: dp배열 아이디어 > * k원을 만들기 위해서 k-n원 +n원이 필요하다 > * for문을 돌며 모든 동전에 대해 dp배열을 업데이트 한다. 예시 동전의 개수
백준 17387 CCW
백준 17387 ←클릭 CCW를 활용한 문제이다. CCW는 counter clock wise로 점 3개가 있을 때 이 점 3개를 이은 선의 방향을 알 수 있다. 방향을 알 수 있는 원리는 간단한데, 한 점을 기준으로 나머지 두 점을 잇는 직선 두개를 그린 다음, 외적
백준 2098 TSP
백준 2098<-클릭유명한 TSP문제이다. TSP문제는 DP와 DFS로 해결 가능한데 DP로 해결하였다.DP와 더불어 방문 예정 도시를 표시하기 위해 비트 마스크를 사용하였다. 이 문제에서 도시의 개수는 16개로 제한지만 계산 중 오버플로우를 방지하기 위해 17자
백준 14003 가장 긴 증가하는 부분 수열 5
백준 14003 <-클릭LIS알고리즘을 사용하여 최장 증가 수열을 구하는 문제이다. 1부터 5까지 있는데 5부터 풀어봤다. 1~4를 모두 확인한 것은 아니지만 기본적으로 같은 문제이고, 대신 테스트케이스의 조건이 달랐다. 해당 문제를 dp로 풀게되면 $$O$$($
SWEA 1855 영준이의 진짜 BFS
SWEA 1855 <-클릭LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다.아이디어를 간단하게 요약하면 다음과 같다 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 d
SWEA 1249 보급로 문제
SWEA 1249 <-클릭 최저 비용으로 경로를 탐색하는 문제다. 문제의 조건을 2차원 배열 map으로 받았다. 또한, 특정 위치로 갈 때의 최소의 비용을 저장하는 2차원 배열을 cost로 하였다.예) costi는 (i,j)로 가는 (지금 껏 계산한) 최소한의