알고리즘

문제입력 게이트 번호 : a 1~a의 게이트 중에 가장 큰 번호의 게이트부터 도킹을 하기 위해 find로 도킹 가능한 가장 큰 번호의 게이트 번호를 찾는다. 0일 경우 가능한 게이트가 없으므로 종료. 0이 아닐 경우 도킹 가능한 가증 큰 번호 게이트-1과 a를 unio

문제

문제이분탐색을 위해 먼저 나무 높이들을 정렬해준다.절단기 높이에 대한 이분탐색 진행 시작: 0 ~ 끝: 가장 높은 나무mid1은 절단기의 높이현재 절단기 높이의 lower bound 인덱스(e)를 찾아준다.누적합 배열 sum에서 e~n-1까지 구간합을 구한 후 (절단기

문제처음 풀이모든 노드에서 dfs를 시작해 가장 긴 거리를 찾았다.개선된 풀이아무 노드를 잡아서 dfs를 진행해 가장 먼 노드를 찾아준다.찾은 노드에서 dfs를 시작해 가장 먼 거리를 찾아주면 정답이다.\#dfs

문제dfs로 라이언이 화살을 맞히는 모든 경우의 수를 완전탐색을 진행했다.\#dfs

문제다익스트라로 마을별 최단 거리를 구해주고 k이하의 마을을 카운트\#다익스트라

문제진출 지점 기준으로 오름차순 정렬하여 탐욕법을 적용\#그리디

문제오른쪽과 아래로만 이동하기 때문에 현재 위치에서 위에서 오는 경우와 왼쪽에서 오는 경우를 더해준다. 대신 웅덩이에서는 0으로 해준다.\#dp

문제정규표현식을 사용하여 제재아이디에 해당하는 id를 찾아 조합을 구해서 HashSet에 담아 중복처리를 하였다.\#dfs #Set

문제크루스칼 알고리즘을 통해 MST(최소신장트리)를 구했다. 유니온 파인드를 통해 사이클을 판별했다.\#MST #union-find #크루스칼

문제주어진 모든 항공권을 사용해야 하는 조건이 있기 때문에 완전탐색 진행모든 경로를 구해주고 정렬을 해서 알파벳 순 가장 빠른 경로 리턴\#dfs

문제느리게 갱신되는 세그먼트 트리 lazy propagation을 알아야 풀 수 있는 문제\#세그먼트 트리 #lazy propagation

inversion counting 세그먼트 트리를 사용해서 풀었다.공장 두번째 라인의 인덱스 번호를 빠르게 조회하기 위해 HashMap을 사용하였다.\# 세그먼트트리

문제점수가 높은 순으로 우선순위 큐에 넣어준다.과제를 최대한 마감일에 가까운 날짜에 해준다.\#우선순위큐 #그리디

문제tree를 만들기 위해서 root를 알아야 한다.A부모 B자식 순으로 노드 쌍을 주기 때문에 levelb++을 해주면levelnode==0인 노드가 루트이다.트리를 만들어준 후 lca 알고리즘을 통해 공통 조상을 찾아준다.\#lca

문제먼저 배열을 정렬해준다.배열 원소를 차례대로 방문해서 시작 0 끝 n-1 로 지정해서 투 포인터를 ㅏ사용해서 두 수의 합이 방문한 배열 원소와 같은지 확인해준다.주의할 점은 l==i, r==i인 경우를 좋다로 체크하면 안된다.\#투포인터

문제병합 정렬 과정에서 numl >= numr 인 경우는l ~ mid 까지는 numr보다 크다는 뜻이므로 정답에 mid-l+1을 더해준다.\#병합정렬(merge sort)

문제임의의 노드에서 dfs로 가장 먼 노드를 찾아준다.찾은 노드에서 dfs를 한번 더 진행하면 지름이 구해진다.\#dfs

문제 풀이 https://kibbomi.tistory.com/203 풀이 참고한 블로그 루트 노드를 0으로 시작 0 ~ N-1 각 노드의 번호(x)의 부모 노드는 (x-1)/k이다.

문제우선 배열을 오름차순 정렬해준다.0~n-2까지 투포인터를 통해 최소 특성값을 구해준다.numsi 고정 l=i+1, r=n-1 로 시작numsi+numsl+numsr이 0보다 작으면 l++0보다 크면 r--\\

문제1\. 십진수를 이진수 문자열로 바꾼다.2\. 0을 채워서 포화이진트리로 바꾼다.3\. 부모 노드가 0이고 자식노드가 1이면 불가능한 경우이다.}

문제타임라인을 초로 변환해준다.모든 log를 조회하여 각 초마다 재생시간을 누적시켜준다.광고 시간만큼 슬라이딩 윈도우를 통해 누적합이 가장 큰 구간을 구해준다.

문제모든 출발지에서 산봉우리까지의 다익스트라 진행하여 가장 최소 intensity를 찾아준다.인접리스트 구성할 때 출입구, 산봉우리, 일반로 구분해줬다.\#다익스트라

문제처음 BFS로 했다가 시간 초과 발생DFS로 d l r u 사전 순으로 먼저 이동테스트케이스 31번에서 시간 초과 발생k보다 거리가 짧으면 왔다갔다를 해야돼서 짝수로 떨어져야함

문제1\. 센서 오름차순 정렬2\. 센서 간 구간 거리를 계산3\. 구간 거리 오름차순 정렬4\. 뒤에서부터 k-1개 제외하고 거리들을 합산

문제리스트 초기값 0숫자가 리스트 가장 맨 끝 숫자보다 크면 리스트 끝에 추가작으면 리스트에서 이분탐색으로 크거나 같은 숫자 인덱스 찾아서 replace\#이분탐색#LIS

문제1\. 석순과 종유석 up down 배열로 나눠서 저장2\. 석순 종유석 정렬3\. 이분탐색 lower bound로 개수를 구해준다.

문제1\. 서류 순서로 오름차순 정렬2\. 시작 비교대상은 서류 순위 1등3\. 면접 순위 높은 대상이 나타나면 비교 대상을 바꿔주고 카운트 +1\#그리디

문제l=1 , r= 가장 긴 랜선 길이로 이분탐색 진행해서 만들 수 있는 랜선 개수를 확인한다.n 이상이면 l=mid+1 미만이면 r=mid-1\#이분탐색

문제l=1 , r= 가장 큰 예산 금액 이분탐색 진행해서 총 예산안 초과하는지 체크\#이분탐색

문제x가 행 y가 열로 된 것 주의!x,y 까지의 누적합 구해주기x2,y2 까지의 누적합= x2,y2 - x2,y1-1 - x1-1,y2 + x1-1,y1-1\#누적합

문제투 포인터로 s 이상인 경우 찾고 가장 짧은 길이 갱신s 이상인 경우 없으면 0으로 출력하기\#투포인터

문제1\. 배추를 1으로 두고 배추의 위치들을 리스트에 저장2\. 배추 위치 순차적으로 탐색하는데 방문 배열이 0이면 bfs 실행\#bfs

문제물고기 우선 순위 주의하기bfs 진행해서 먹을 수 있는 물고기가 있으면 후보 리스트에 추가물고기 후보 리스트 정렬물고기 먹으면 초기화 후 다시 bfs 진행먹을 수 있는 물고기가 없으면 종료\#bfs

문제dfs는 느리니까 bfs로 해주기방문 처리는 Set으로 했다.음수, 20만 이상 넘어가는 것 조건 처리정답 찾으면 즉시 종료\#bfs

문제루트 노드에서 깊이 탐색 시작해서 지울 노드는 탐색 진행 X\#트리#dfs

문제1\. 이진 검색 트리 구성노드 개수를 알려주지 않아서 배열로 트리를 만들지 않고 클래스를 만들어 left, right를 만들어줌후위순회 진행\#트리

문제정렬, 해시, 트라이 여러 풀이가 있는데 트라이 공부를 위해 트라이 자료구조를 사용하여 풀이\#트라이

문제1\. 후위순회에서 가장 맨 뒤는 root2\. 중위순회에서 root 위치 찾기3\. root 기준으로 왼쪽 서브트리 오른쪽 서브트리 구분4\. 후위순회에서 왼쪽 서브트리 분리해서 재귀 진행5\. 후위순회에서 오른쪽 서브트리 분리해서 재귀 진행\#트리

문제1\. cctv들의 위치를 list에 저장2\. 모든 cctv와 각 cctv 번호에 맞게 모든 방향 완전탐색check() 함수는 감시 가능 구역 체크change() 함수는 - undo() 함수는 백트래킹 -1을 다시 0으로\#구현

문제위아래로 굴렸을 때 바꿔줄 배열 ud왼오로 굴렸을 때 바꿔줄 배열 lr방향에 따라 배열을 돌려주었다. 배열의 3번 인덱스가 주사위의 바닥 1번 인덱스가 상단\#구현

문제1\. 정상인 경우와 색약인 경우의 그림을 따로 할당.2\. bfs 진행하여 구간 개수 구하기.\#bfs

문제1\. 트리를 구성하기 위한 간선 정보를 인접리스트에 담아둔다.2\. 루트 노드를 시작으로 트리를 만들어준다.3\. 서브트리 사이즈를 구해준다.처음에 매번 쿼리마다 사이즈를 구했을 때 시간초과 발생리프노드부터 부모에 자식의 서브트리 사이즈를 더해서 한번에 모든 노드

문제dp 기초 문제한 칸 적은 곳에서 1칸 점프로 오는 경우와 두 칸 적은 곳에서 2칸 점프로 오는 경우dpi=dpi-1+dpi-2\#dp

문제1\. hashMap을 사용해 귤 사이즈당 개수를 구해준다.2\. 개수가 많은 순으로 정렬3\. k개 이상 될때까지 체크

문제1\. 배열을 이어붙여 원형배열을 구현ex) 7,9,1,1,4 -> 7,9,1,1,4,7,9,1,12\. 누적합을 구해준다.3\. 부분 수열 크기 1~n 까지의 부분합들을 Set에 넣어준다.\#부분합 #누적합

문제회전시킨 문자열 하나씩 검사문자 하나씩 차례대로 스택에 넣고 다시 꺼내면서 검사한다.스택에서 이전에 나온 문자를 기록해두고 비교해준다.\#스택

문제도로는 양방향이므로 destination에서 다익스트라 진행하면 각 source별 최단거리를 구할 수 있다. \#다익스트라

문제1\. Deque를 이용해 0-1 bfs 진행2\. 다음 갈 곳이 빈 방이면 cnt 그대로 덱 앞에 삽입 벽이면 cnt+1 덱 뒤에 삽입3\. n,m 도달하면 종료\#bfs

문제점화식 dpn = dpn + dpn-현재 동전 크기노트에 직접 써보면서 하니까 이해가 됐다.\#dp

문제1\. dp 배열을 먼저 최대 개수인 k+1로 채운다.2\. dp금액 현재 금액에 필요한 동전 개수랑 dp금액-현재 동전 크기+1 비교3\. dpn=MIN(dpn,dpn-coin+1) 이렇게 점화식이 성립된다.\#dp

문제1\. map이란 2차원 배열에는 인구수들이 저장2\. 0,0부터 n-1,n-1까지 인구 이동이 일어나는지 while문을 통해 반복 확인3\. 인구 이동은 bfs를 통해 진행한다.4\. 인구 이동이 일어나지 않으면 while문 종료bfs함수에서 인구 이동이 일어나면

문제1\. n이 최대 40까지니까 40번 좌석까지 경우의 수를 미리 구해둔다.2\. 경우의 수를 구하는 점화식은 dpn=dpn-1+dpn-2이다.3\. vip 좌석이 생기면 vip 좌석을 기준으로 구간이 나뉘게 된다. 나뉘어진 구간들의 경우의 수를 곱해주면 정답 도출\

문제투포인터 기본 문제\#투포인터

문제1\. 숫자 정렬2\. l=0 r=n-1부터 투포인터 진행3\. 두 용액 더했을 때 절댓값이 작으면 정답 갱신, 더한 값이 0보다 작으면 l++ 0보다 크면 r--\#투포인터

문제처음에 Set을 이용하여 구현했지만, 집합에 같은 번호 스시가 여러개 포함되어 있을 때 remove를 하면 한번에 삭제되는 문제가 있었다.그래서 DAT로 변경하여 개수로 체크해줬다.원형을 고려해서 인덱스를 % n 을 해줘서 인덱스 에러 방지\#슬라이딩윈도우

문제1\. 이분탐색B 배열만 정렬해주고 A 배열 각 원소마다 이분탐색 진행원포인터A,B 둘다 정렬 원포인터 사용ai 원소보다 큰거나 같은 것 발견할때까지 포인터 이동, 멈추면 다음 원소로 포인터부터 시작해서 다시 진행\#이분탐색

문제1\. 물건들을 무게순으로 오름차순 정렬2\. dp 2차원 배열의 행은 물건 열은 무게3\. dp 배열의 값은 해당 무게에서 가치의 최댓값이다.4\. j-물건의 무게가 0 이상과 0 미만일 경우 구분해서 구해준다.\#dp

문제1\. 우선순위큐를 사용하여 크루스칼 알고리즘 구현2\. 유니온파인드를 통해서 연결된 노드를 한 그룹으로 묶어줬다.\#MST #유니온파인드

문제1\. pre 배열에는 본인보다 앞에서 서야 하는 학생의 수를 저장2\. v 배열은 학생이 줄에 섰는지 체크3\. posti에는 i번째 학생이 선행되어야 하는 학생들의 번호를 저장4\. prei==0인 선행되어야 하는 학생 수가 0인 학생들을 반복적으로 확인해주며

문제DFS, BFS 두 방식 다 제출했는데 비슷한 속도로 통과했다.BFSDFS\#dfs #bfs