알고리즘

문제링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/?envType=daily-question&envId=2024-03-03 Maximum Odd Binary Number - LeetCode Can you solve this real interview question? Maximum Odd Binary Number - You are given a binary string s that contains at least one '1'. You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary..

문제링크: https://leetcode.com/problems/maximum-odd-binary-number/description/?envType=daily-question&envId=2024-03-01 Maximum Odd Binary Number - LeetCode Can you solve this real interview question? Maximum Odd Binary Number - You are given a binary string s that contains at least one '1'. You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number..

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/131537 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 SELECT DATE_FORMAT(SALES_DATE,"%Y-%m-%d"), PRODUCT_ID, USER_ID, SALES_AMOUNT FROM (SELECT SALES_DATE, PRODUCT_ID, USER_ID, SALES_AMOUNT FROM (SELECT * FROM ONLINE_SALE WHERE SALES_DATE BETWEEN '2022-03-01' AND '20..

개요 본문에서는 파이썬의 sort() 및 sorted() 함수에 적용된 TimSort 알고리즘에 대해 설명하고자 합니다. TimSort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)의 특성을 결합하여 구현된 고도로 효율적인 정렬 알고리즘입니다. 이 글에서는 TimSort의 작동 원리와 그 구성 방식에 대해 간략히 소개하겠습니다. Binary insertion sort 특징 안정 정렬 비교 횟수가 Insertion sort에 비해 적음 Insertion sort 는 비교하는 연산에 최대 O(N^2) 시간이 소요됩니다. 반면 Binary insertion sort는 이러한 비교 연산 O(NlogN) 으로 줄일 수 있는데 어떻게 줄일 수 있는지 insertion sort의 특징과 ..

개요 Union-Find 는 그래프 G가 주어졌을때 상호 배타적 집합(Disjoint-Set)을 표현할때 사용되는 그래프 알고리즘입니다. 임의의 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용됩니다. 연산 Union (합치기): 두 원소가 속한 집합을 하나로 합침 Find (찾기): 해당 원소가 속한 집합을 반환 Find 본인이 속한 집합을 찾기 위한 연산으로 기본 방법과 경로 최적화 방법이 존재합니다. 기본 방법: 최악의 경우 시간복잡도 O(N) int find_parent(int x) { if(x == parent[x]) return x; else return find_parent(parent[x]); } 경로 최적화: 시간복잡도 O(1) int find_parent(int x) { if(..

이진 트리 (Binary Tree) 자식 노드의 개수가 최대 2개인 트리 포화 이진 트리 (Full Binary Tree) 모든 레벨에 노드가 포화 상태로 차 있는 바이너리 트리 최대 노드 개수인 (2^(h+1) -1) 의 노드를 가진 Binary Tree 루트를 1번으로 하여 2^(h+1) -1 까지 정해진 위치에 대한 노드 번호를 가짐 완전 이진 트리 (Complete Binary Tree) 높이가 h 이고 노드 수가 n 일때 Full binary Tree 의 노드 1번부터 n 번까지 빈자리가 없는 binary tree 편향 이진 트리 한쪽으로만 쏠려 있는 트리 Array 로 트리를 표현하기 자식노드 = i*2, i*2+1 부모노드 = i / 2 높이가 h 인 Binary Tree 를 위한 Array..

문제 문제링크: https://www.acmicpc.net/problem/30961 풀이방법 문제의 요구사항은 길이가 "1" 이상인 모든 부분수열 각각의 합을 구하여 모두 XOR한 합을 구하는 것이다. 해당 문제를 보자마자 바로 에드 훅 문제라는것을 생각했지만. 생각보다 푸는데 오랜시간이 소요되었다. 우선 문제를 풀기 위해 XOR 의 특징을 이용하기로 했다. 같은 수 X 를 2^N 번 XOR 연산하면 그 수는 0이 된다. 해당 문제에서 정의하는 부분수열은 인접하지 않아도 되었기 때문에 입력으로 주어진 배열을 오름차순으로 정렬하여 배열을 분석할 수 있다. 2, 3, 1 -> 1, 2, 3 풀이를 좀더 쉽게 생각하기 위해 아래와 같은 배열이 있다고 가정한다 1, 2, 3, 4, 5 최대값의 위치를 M 최소값..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이시간 설계: 160분 구현: 20분 문제 종류 스택, 자료구조 풀이 방법 이 문제의 요구사항은 다음과 같이 정의된다. 1. 두개의 인덱스를 결정한다. (A,B) 2. 두개의 인덱스 사이에 있는 값들은 arr[A] > val and arr[B] > val 을 동시에 만족해야한다. 예를들어 배열이 4,2,3,5 와 같은 형태의 경우 가능한 쌍은 아래와 같다 (4,2),(4,..