알고리즘

[트리] 리트코드(Leetcode)/2265 - Count Nodes Equal to Average of Subtree

PROBLEM Count Nodes Equal to Average of Subtree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com N = 서브트리의 합의 평균과 그 서브트리의 루트값과 같을 때를 카운트한 값 RETRY FLAG Y - 재귀에 대한 이해 다시 적립 필요 - 멍한 상태로 디버깅 하지말기 MY SOLUTION 아래는 전역변수로 관리하는 방식이고 마지막에 값이 들어가게 되는 최상단 루트인 4에서 node==null로 들어간 상태로 값을 돌려받는거라..

[트리] 리트코드(Leetcode)/1584 - Min Cost to Connect All Points

시행착오 최소 비용이라길래 BFS를 떠올림 두 점 사이의 거리를 뭔가 수학적으로 접근할 수 있을거란 생각을 함 BFS로 구현해보고자 2차원배열을 107 사이즈로 해당 좌표에 값을 채워넣는 초기화로 시작했으나 잘 안돼서 결국 힌트를 봄..ㅠㅠ

[BFS] 프로그래머스/1844 - 게임 맵 최단거리

[자료구조] 우선순위 큐와 힙

우선순위 큐(Priority Queue) 큐 형태로 우선순위가 높은 데이터가 먼저 나가는 자료구조 cf ) 큐(Queue) 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 ADT(Abstract Data Type) - 객체 우선순위를 가진 요소들의 모음 - 연산 insert(x) 우선순위 큐에 요소 x 추가 remove() 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환 find() 우선순위 큐에서 가장 우선순위가 높은 요소를 반환 구현 방법 배열 또는 연결리스트를 이용 > 삽입 또는 삭제 연산을 위한 시간복잡도는 O(n) ( ∵ 선형 구조의 자료구조 ) 힙 트리 이용 > 힙트리의 높이는 log₂(n+1)이며 힙의 시간복잡도는 O(log₂n) (..

Collection 함수 정리

정렬 관련 Arrays.copyOfRange() 전달받은 배열의 지정된 범위에 해당하는 요소만을 새로운 배열로 복사하여 반환 public static int [] copyOfRange (int [] 복사할 원본 배열, int 원본 배열에서 복사할 범위의 시작 인덱스, int 원본 배열에서 복사할 범위의 끝 인덱스) 반환값 원래 배열에서 지정된 범위를 포함하는 새 배열. (필요한 길이를 얻기 위해 잘리거나 0으로 채워짐) 예외 ArrayIndexOutOfBoundsException - 초기 인덱스, 즉 (from_index)가 원래 배열의 범위를 벗어난 경우 발생 IllegalArgumentException - form_index > to_index 인 경우 NullPointerException - 원래 ..

[DP] 백준 11052 - 카드 구매하기

더보기 - 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고..

[DP] 백준 11727 - 2×n 타일링 2

더보기 - 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. - 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 2 8 12 - 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 3 171 2731 - 정의 D[N] = 1×2, 2×1과 2×2 타일로 채우는 방법의 수 = D[1*2] + D[2*1] + D[2*2] = 2*D[N-1] + D[N-2] (XXX) = D[N-1] + 2*D[N-2] (OOO) 2*2를 하나짜리로 쳐서 1개의 타일이라고 생각했는데 크기 2가 빠지니까 n-2이다. (2*1를 2개 놓는 꼴이니까 n-2과 같은..