포비 포비

https://school.programmers.co.kr/learn/courses/30/lessons/43165  문제풀이1아이디어- 모든 경우의 수를 살피기 위해 BFS 방식을 사용한다- 저장구조는 큐를 사용한다- 큐에 인덱스와 값을 저장하여 현 단계와 현재까지의 합을 저장한다코드import java.util.*;class Solution { public int solution(int[] numbers, int target) { int answer = 0; Queue queue = new LinkedList(); queue.add(new int[]{0, 0}); while (!queue.isEmpty()) { i..

https://school.programmers.co.kr/learn/courses/30/lessons/12914내 문제 풀이1아이디어- 피보나치 수열 성질을 이용한다.- 피보나치 수열 일반항을 이용한다. 코드class Solution { public long solution(int n) { long answer = Math.floor((1/Math.sqrt(5)*((Math.pow((Math.sqrt(5)+1)/2,n+1))-(Math.pow((-Math.sqrt(5)+1)/2,n+1))))); return answer % 1234567; }} (자바를 통해 풀면 자료형 범위 제한때문에 BigDecimal을 사용해야 파이썬을 이용하면 자료형 없이 쉽게 풀 수 있다.)..

문제 설명XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다. 예를 들어, 정현이가 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며, XYZ 마트에서 14일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나인 경우에 대해 알아봅시다. 첫째 날부터 열흘 간에는 냄비가 할인하지 않기 때문에 첫째..

그래프란? 노드와 그 노드를 연결하는 간선으로 이루어진 구조. 모든 노드가 연결되어있지 않아도 그래프에 속한다 트리 또한 그래프의 일종이다. 그래프 용어 정리 - 정점 : 노드 - 간선 : 노드와 노드를 연결하는 선 그래프의 종류 무방향 그래프 : 노드간의 순서가 없음, A->B 또는 B>A 상관없이 이동 가능, 이 경우 (A,B) 또는 (B,A)로 표현 방향 그래프 : 노드간의 순서가 있음, A->B는 가능하나 B->A는 불가, 이 경우 로 표현 - 자기 간선 그래프 : 정점 자기 자신에서 나와 자기 자신으로 돌아오는 간선이 존재하는 그래프 - 다중 그래프 : 한 정점에서 특정 정점으로 가는 간선이 두개 이상인 경우가 존재하는 그래프 - 완전 그래프 : 모든 정점이 서로 연결되어있는 그래프(ex G1)..

우선순위 큐란? 우선순위의 개념을 큐에 접목시킨 자료구조. 즉 우선순위가 높은 요소가 먼저 들어오고 먼저 나가는 자료구조다. 구현 방법 선택 우선순위 큐를 구현하는 방법은 배열, 리스트, 힙 3가지가 있는데, 그중 힙이 가장 효율적이다. 힙(heap)이란? - 완전 이진 트리의 일종이며 우선순위 큐를 위해 만들어졌다. 즉, 각 요소들의 우선순위를 비교하여 트리로 정리해놓은 것이다. - 힙은 최대힙과 최소힙으로 나뉜다. 최대 힙 : 부모의 값 >= 자식의 값 인 완전 이진 트리 최소 힙 : 부모의 값 자식으로만 갈 수 있지 자식->부모로는 갈 수 없다. 힙의 노드 생성을 구현하려면 리프 노드에서 생성되어 자식과 부모의 값을 비교하며 위로 올라갈 수 있어야 하는데 연결리스트는 이를 수행하지 못한다. - 우선..

일반 트리에서 이진 트리로 변환하는 법 왼쪽 자식-오른쪽 형제 표현을 활용한다 일반트리를 이진트리로 변환하려면 한 노드당 가진 자식을 2개 이하로 줄여야 한다. 그러기 위해 왼쪽 자식-오른쪽 형제 표현을 활용한다. 이 표현은 위 그림과 같이 각 노드에 값(data), 왼쪽자식의 주소(left child), 오른쪽 형제의 주소(right sibling)를 담는 방법이다. 노드 클래스를 만들 때 이 세 멤버변수를 넣는다. 표현을 적용 하면 아래 그림과 같이 트리가 그려지고, 그 트리를 45도로 회전시키면 이진트리 모양으로 바뀐다. 이로써 일반트리가 노드당 두개의 자식만 가지게 되었다. 하지만 해당 트리를 활용할 때 실제로 오른쪽 노드는 자식이 아닌 형제관계임을 인지해야 한다. 이진 트리 노드 구현 이진 트리..

트리란? 1개 이상의 노드를 갖는 집합. 하나의 노드를 중심으로 나머지 노드들이 뻗어나가는 구조다. 트리의 필요성 - 트리는 빠른 탐색에 강점을 보인다. 연결리스트는 특정 노드로 찾아가려면 노드의 처음부터 탐색해야 해서 시간이 꽤 걸리는데, 트리가 이 문제를 보완해준다. - 노드 간의 순서가 있거나 노드들이 포함관계일 때 트리는 그 관계를 통해 노드를 찾을 수 있다. 트리 용어 노드 : 한 정보 아이템 + 다른 노드로 뻗어진 가지 부모( 자식) : 부속 트리를 가진 노드 (ex E의 부모는 B) 형제 : 같은 부모를 가진 노드 (ex E의 형제는 F) 루트 : 최상위에 있는 노드 (ex 루트는 A) 노드의 차수 : 특정 노드의 자식 수 (ex B의 차수는 2) 트리의 차수 : max(노드의 차수) (ex..

큐란? 가장 먼저 저장한 자료가 가장 먼저 호출되고, 가장 나중에 저장한 자료가 가장 나중에 호출되는 구조. 한 쪽에서 들어와서 다른 쪽에서 나오는 빨대와 같다 사용 예시 - 컴퓨터 운영체제의 작업 스케줄링(Task Scheduling) 중 빠른 시작시간 우선 스케줄링 - 너비 우선 탐색(BFS) 큐 구현 첫번째 방법 : 기본 배열로 구현하는 방법 원소 삽입하는 법 : 마지막 위치 뒤에 원소를 삽입한다. 원소 삭제하는 법 : queue[0]에 있는 원소를 삭제한다. 하지만 이 방법은 원소를 삭제할 때마다 뒤의 나머지 원소들을 왼쪽으로 한칸씩 이동해야 한다. (삭제할 때의 시간복잡도는 O(n)) 두번째 개선된 방법 : 첫번째 원소의 위치를 옮기는 방법 원소 삽입하는 법 : 마지막 위치 뒤에 원소를 삽입한다..