이왕 발 디딘 이승, 원없이 즐겨야하지 않겠소?

백준 온라인 저지 1992번 '쿼드트리' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복 사실은 정말 쉬운 개념이다. 복잡한 문제를 해결할 수 있는 작은 단위로 나누어 처리하고 이것을 합치면 된다. 이 문제를 풀면 백준 1780번 문제 종이의 개수도 아주 쉽게 풀 수 있을 것이다. (유사한 문제 풀기 -> 백준 1780번 문제종이 https://developer-mac.tistory.com/38) 그리고 쿼드트리는 단순히 노드가 4개 있는 것이라고 생각하면 된다. 즉, 4개로 쪼개서 4개의 노드가 생겨난다고 생각하면 된다. 먼저 입력을 받은 후 divide 함수에서 재귀적으로 동작하고 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면..

Study/Algorithm 2022. 3. 19. 23:10

완전탐색 (Brute-Force) BP라고 불리는 완전탐색은 단어 그래로 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 강력한 방식이지만, 시간은 최대로 들어간다. 예를들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0 ~ 9999까지 다 해보면된다. 경우의 수는 10,000가지이다. 만약 한 숫자당 1초가 걸린다고 하면 10,000초 = 2.7시간정도가 걸린다. 따라서 완전탐색을 풀기위해서는 대표적으로 4가지를 생각해볼 수 있다. for문 사용 순열, 조합 사용 재귀함수 사용 비트마스크 사용 2309번 일곱 난쟁이 조합을 이용해서 풀면된다. 1476번 날짜 계산 나머지를 이용 14500번 테트로미노 노가다 문제... 1966번 프린터 큐 큐 개념도 연습할 수 있다. 2231번 분해합 순열(..

Study/Algorithm 2022. 3. 19. 23:07

동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 ..

Study/Algorithm 2022. 3. 19. 23:07

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:06

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:01

스택 (STACK)이란? 📌 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 📌 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자..

Study/Algorithm 2022. 3. 19. 23:00

래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 📌여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. 그래프와 트리의 차이가 궁금하다면? 👇🏻 큰 특징만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프 를 트리라고 말합니다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분..

Study/Algorithm 2022. 3. 19. 22:58

프로그램 구조 Java package hello; public class HelloWorld { public static void main(String[] args) { String name = "Java"; // 매개변수를 확인 if (args.length == 1) name = args[0]; System.out.println("Hello, " + name + "!"); } } C# using System; namespace Hello { public class HelloWorld { public static void Main(string[] args) { string name = "C#"; // 매개변수를 확인 if (args.Length == 1) name = args[0]; Console.Wri..

Study/Language 2022. 3. 18. 20:39