본문 바로가기

알고리즘

 (3)
[Java] 표현 가능한 이진트리(프로그래머스) 완전상세분석 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 본 문제는 입력값으로 주어진 10진수의 값이 주어진 조건에 의해 이진법 형태로 변경 후 이진트리의 형태로 구현될 수 있는가를 묻는 문제이다. 주어진 예시를 다시 한 번 살펴보면 다음과 같다. 예시 1) [7,42,5] 7은 이진법으로 111로 나타낼 수 있다. 이것을 완전이진트리로 나타내면 아래와 같이 간단하게 표현할 수 있다. 42는 이진법으로 101010 로 나타낼 ..
펜윅 트리(1차원 펜윅 트리, Fenwick Tree, Binary Indexed Tree) ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 위와 같은 1차원 배열이 있다. 해당 배열에서 ary[3]~ary[7] 구간합을 구하고자 한다. 가장 기본적인 코드는 아래와 같이 하나씩 모두 더하는 것이다. 해당 코드의 시간복잡도는 O(N) 이다.(연산의 수가 M일 경우 O(MN)) 펜윅트리를 사용하게 되면 이를 O(logN) 으로 감소시킬 수 있다. 그렇다면 펜윅트리가 무엇인지 알아보자. 1. 펜윅트리란 무엇인가? 펜윅트리는 Binary Indexed Tree, BIT 라고도 하며, 쉽게 말해 구간합을 빠르게 구하기 위한 자료구조이다. 2. 트리만들기(초기화) 입력받은 배열 ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 를 이용해 펜윅트리를 만들어 보자. 펜윅트..
2차원 펜윅트리 이해하기(2-dimentional Fenwick Tree) 펜윅트리는 비트연산을 통해 빠른 시간에 구간합을 구하는 배열 형태의 트리이다. 이 글에서는 2차원 펜윅트리만을 설명하고 있다. 1차원 펜윅트리에 대한 이해가 필요하면 블로그 내 펜윅트리 글(https://uldada.tistory.com/5)을 참고하자. 2차원 펜윅트리 우선 2차원 펜윅트리의 Update와 Sum 함수를 보자. 코드를 보면 x축(여기에선 열을 의미)으로 펜윅트리가 동작하며, 그 안에 while문을 통해 y축(행을 의미)으로 펜윅트리가 동작한다. 일단 update를 통해 초기화(입력받은 배열을 통해 펜윅트리 채워나가기)를 진행해 보자 초기화는 update 함수를 통해 진행된다.(1차원 펜윅트리와 동일한 방식) 입력받은 배열은 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

티스토리툴바