밤이 블로그

자료구조 - Heap * Heap이란?1. Complete binary tree이면서 : 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외하고는 다채워진, 자식이 추가될 때 왼쪽부터 추가되는 트리 2. Heap Property를 만족하는 것 1) max heap property : 부모는 자식보다 크거나 같다. 2) min heap property : 부모는 자식보다 작거나 같다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 ..

NP, NP-Hard http://www.valken.net/274

BOJ#1263 시간 관리 * 문제https://www.acmicpc.net/problem/1263 * 풀이일상 생활에서 흔히 하는 고민을 다룬 문제인 것 같습니다. 😅(내일 무슨 무슨 일을 언제까지 해야 되니까, 몇시쯤 집에서 나가면 되겠구나! ) 첫째 줄에 일의 개수 N,그 다음 N개의 줄에 T와 S가 주어집니다. ( T : 필요한 시간, S : 납기 ) 일단 S 기준으로 오름차순 정렬을 합니다. 내림차순으로 해도 상관없습니다. 3 58 141 165 20 0시 부터 일을 시작할 수 있으므로가장 마지막 일(4번째 일)을 끝내기 위해서는 15시에는 일을 시작해야 합니다. 그리고 이것은 3번째 일에 영향을 주게 됩니다. 3 58 141 16 155 20 이어서 3번째 일을 끝내기 위해서는 14시에는 일을..

순열 (PERMUTATION) - 사전순 이전 글 : 순열 (PERMUTATION) http://stack07142.tistory.com/24 순열을 사전순으로 만들려면 어떻게 해야 할까 [1, 2, 3, 4] 순열이 있을 때,---------------------------------------------------------[1, 2, 3, 4] [1, 2, 3, 4][2, 1, 3, 4][3, 1, 2, 4][4, 1, 2, 3]---------------------------------------------------------[1, 2, 3, 4][1, 2, 3, 4][1, 3, 2, 4][1, 4, 2, 3][2, 1, 3, 4][2, 1, 3, 4][2, 3, 1, 4][2, 4, 1, 3]..

알고리즘 용어 처음에는 몰랐던 알고리즘 용어들 Accepted (AC) Presentation Error (PE) Wrong Answer (WA) Runtime Error (RE) Time Limit Exceeded (TLE) Memory Limit Exceeded (MLE) Output Limit Exceeded (OLE) Compilation Error (CE) Restricted Function (RF) Internal Error (IE)

Nim 게임 * Nim 게임이란?님(Nim)은 수학적 전략 보드 게임이다. 몇개의 줄에 숫자나 자연수개의 돌을 두고 순서대로 돌아가면서 한 줄에서 정해진 수의 숫자를 제거한다. 가져오는 숫자에는 상한이 있으며 무조건 1개는 가져와야 한다. 마지막 돌을 가져오는 사람이 이긴다. (마지막 돌을 가져오는 사람이 지는 것으로 하기도 한다.) * 필승 규칙"불균형 상태를 균형 상태로 바꾼다." - 2줄인 경우 -> 균형 상태 : 두 줄의 돌의 개수가 같은 경우 -> 불균형 상태 : 두 줄의 돌의 개수가 다른 경우 - 3줄인 경우 : -> 균형 상태 : Nim Sum이 000인 경우 -> 불균형 상태 : 균형 상태가 아닌 경우 * Nim 게임 해보기http://www.transience.com.au/pearl3.h..

n명을 k개의 그룹으로 분할하는 경우의 수 (제 2종 스털링 수) 출처 : http://terms.naver.com/entry.nhn?docId=3405190&cid=47324&categoryId=47324

Manacher's Algorithm #1 : https://algospot.com/wiki/read/Manacher's_algorithm#2 : http://www.ideserve.co.in/learn/longest-palindromic-substring-manachers-algorithm 알고리즘 설명은 위 출처에 잘 되어 있습니다.- Time Complexity : O(n)- Space Complexity : O(n) * 관련 문제BOJ#10942 팰린드롬? https://www.acmicpc.net/problem/10942 * 코드 public class Manacher { public Manacher(String s) { char[] T = new char[s.length()*2 + 3]; T[..

인접행렬과 인접행렬의 거듭제곱 → 잘 설명된 블로그가 있어서 공유합니다.http://blog.naver.com/gt7461/110151975370

[공유] 알고리즘 공부를 입문할 때 읽으면 좋은 자료들 Algorithm Problem Solving 기초 http://slides.com/gangseoklee/aps-5#/