알고리즘
알고리즘 펜윅 트리
알고리즘 펜윅 트리
2024.08.11시작펜윅 트리, 세그먼트 트리에서 변형된 형태입니다. 대표적으로 구간 합 알고리즘을 O(N)보다 빠르게 풀고자 할 때 펜윅 트리를 사용합니다.일반적으로 구간 합을 구할 때 O(N) 정도의 시간이 걸립니다.펜윅 트리(BIT = Binary Indexed Tree) 이용하게 되면 O(logN) 으로 시간 복잡도를 감소 시킬 수 있습니다. 전체 노드의 부분 합 즉, 0~K 합을 구해 두게 되면 원하는 구간 합 S~D를 구하는 것이 가능해 집니다. (Start ~ Destination)O(logN) 의 수행시간 만으로 구간합을 구할 수 있게 됩니다. 구간 합 외에도 같은 원리로 업데이트도 수행할 수 있게 됩니다. 펜윅트리 구조일반적으로 펜윅 트리 구조는 아래와 같이 세그먼트 트리를 응용한 형태로 구조를 정형화..
BOJ_2110_공유기설치
BOJ_2110_공유기설치
2021.11.15**백준_공유기 설치 개인 정리글 입니다. https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아니 딱 절반씩 계속 보면 되는것이 아닌가? 처음에 접근한 것은 저 문장 그대로 코드를 구현하였다. 예상대로 시간초과가 났다. 어떻게 접근해야 할까? 이 문제 접근은 아주 간단하다. 공유기 개수 이다. 처음에 생각한 아이디어는 이분 탐색이었나, 굳이 그럴필요 없다고 생각했다. 왜냐하면 정렬하고 중간값을 ..
프로그래머스_순위
프로그래머스_순위
2021.11.14** 프로그래머스_순위 개인 정리 글입니다. https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제를 읽고 바로 의문이 들었던 것은 어떻게 하면 선수의 순위를 확정할 수 있는지에 대한 의문이 먼저 들었다. 아래 예시를 먼저 보면, 2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 각 선수별로 인덱스를 두고 보면 {0,0,0,0,0} 이다. 이때, {패배, ??, 패배, 패배, 승리} 에서 나머지 4개의 선수에 대한 결과값이 포함되어 있으면 한 선수..
Codeforces 풀이를 위한 JAVA 문법 정리-1
Codeforces 풀이를 위한 JAVA 문법 정리-1
2021.06.13시작 Codeforces를 위해 간단히 몇가지 사항들을 정리해봅니다. 1에서 알아볼 건 기본 입출력, 자료형, 반복문, Call By Value ❌ Call By Reference 입니다. 입출력 Java 입출력에는 BufferedReader 버퍼를 이용해서 쓰는 함수를 활용합니다. 이외에도 Scanner를 사용하기도 하지만 속도가 상대적으로 빠르기 때문에 BufferedReader를 사용합니다. 특히, 공식문서에서 입력 스트림에서 문자를 읽을때 효율적으로 읽기 위해 문자를 버퍼에 저장하는것을 권하고 있습니다. 관련해서는 하기 링크를 참조 부탁드립니다. https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html BufferedReader ..
알고리즘106 :: BOJ_11726_2XN타일링
알고리즘106 :: BOJ_11726_2XN타일링
2020.09.27두가지 접근 방식으로 문제를 해결하였습니다. 1) Bottom-up 과 2) Top-down 으로 접근하였습니다. 기본적으로 이 문제는 피보나치 수열에 대한 이해를 근본으로 하고 있습니다. 1) 바텀업 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 package backjun; import java.util.*; public class BOJ_11726_2n타일링 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n+2]; dp[1] ..
알고리즘104 :: 최소 스패닝 트리(MST)
알고리즘104 :: 최소 스패닝 트리(MST)
2020.09.24최소 스패닝 트리란 무엇일까요? 그래프가 트리형태 인것을 의미합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 입니다. 여기서 최소 스패닝 트리는 스패닝 트리중에서 선택한 간선의 가중치의 합이 최소인 트리를 의미합니다. 대표적으로 MST를 구현하는 방법으로 프림, 크루스칼이 있습니다. 여기서 사이클을 제작하지 않는 범위에서 구현해야 합니다. 왜냐하면, 트리는 사이클이 존재하지 않기 때문입니다. 1)프림 초록색점은 선택한 노드 흰색은 선택하지 않은 노드 입니다. 선택과 선택하지 않은 노드 사이의 간선에서 가중치 값이 가장 작은 값을 갖는 2를 추가합니다. 간선2를 선택하게 됩니다. 선택한 노드와 선택하지 않은 노드 사이에 간선들은 3, 1, 3, 4 가 됩니다. 간선 1이 선택됩니다. 노드 5는 이..
알고리즘101 :: 프로그래머스 - 소수찾기
알고리즘101 :: 프로그래머스 - 소수찾기
2020.09.21소수찾기는 크게 3가지 세션으로 나눠볼 수 있습니다. 1) 주어진 number를 문자로 쪼개기 2) 문자로 쪼갠것으로 모든 경우의 수를 만들기 3) 에라토스테네스체를 이용해 소수인지 검증하기 1의 경우에는 String str = "17" 인경우 String[] number = str.split("") 이용해서 1, 7로 쪼갤 수 있습니다. 2의 경우에는 string[] number, boolean[] picked, StringBuilder sb 를 활용합니다. number는 1의 경우에서 구한것이므로 넘어가고 boolean[] picked = new boolean[number.length]; 로 선언 StringBuilder sb = new StringBuilder() 로 선언 HashSet dff = ..
알고리즘32 :: BOJ_3568_ISharp
알고리즘32 :: BOJ_3568_ISharp
2019.10.08이 문제에 대한 접근은 다음과 같습니다. 1. 공백 또는 , 으로 자릅니다. 2. 처음에 위치한 덩어리는 default 이므로 두고 3. 그 뒤에 문자인 경우와 특수문자 인경우를 잘 둬서 처리해주면 됩니다. 4. 문자는 reverse 했고, 특수문자는 default 덩어리에 append 했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 package backjun; i..
알고리즘23 :: 블러드 필 알고리즘 전형적인 예제
알고리즘23 :: 블러드 필 알고리즘 전형적인 예제
2019.02.28#include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] = {{1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응 bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int n = 7, m = 10; // n = 행의 수, m = 열의 수 int..
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
2019.02.28어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. BOJ :: 2667 단지 번호 붙이기 문제가 대표적이다. 연결요소 를 고려해보면 된다. 단지의 개수와 크기를 구하면 된다. 이차원 배열 상에서 상, 하, 좌, 우 를 고려한 배열이기 때문에 추가적인 자료구조가 필요하지 않다. BOJ_2677_단지번호붙이기가 대표적인 예이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include using namespace std; int ..
알고리즘10 :: 쇠막대기
알고리즘10 :: 쇠막대기
2019.01.04123456789101112131415161718192021222324#include #include #include #include using namespace std; int solution(string str) { vector st; int result = 0; for(int i=0; i