programmingu

스택(Stack)이란? 아이템 추가/삭제 연산이 항상 한 쪽 끝(top)에서만 나타나는 자료 구조이다. LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다. 스택의 구현체는 주로 Single Linked List. Array List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(n) Linked List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(1) 응용 예 그래프의 깊이 우선 탐색(DFS)에서 사용 재귀적(Recursion) 함수를 호출 할 때 사용 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 함수의 콜스택 10진수를 2진수로 바꿀 때 코..

버블 정렬 알고리즘의 개념 서로 인접한 두 원소를 검사해 정렬하는 알고리즘 ⇒ 인접한 2개의 원소의 대소를 비교해 크기가 원하는 순서대로 (오름/내림차순 혹은 사용자가 정의한 Comparator) 되어 있지 않으면 서로 교환 제자리 정렬 : 정렬하고자 하는 배열 안에서 교환하는 방식. 입력 배열 (정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 ⇒ 공간복잡도 O(N) 과정 설명 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동 ⇒ 1 회전에서는 맨 끝에 있는 자료는 정렬에..

OSI 7계층이란? OSI(Open System Interconnection) 7계층은 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것이다. 네트워크 프로토콜 디자인과 통신을 계층으로 나눠 설명한 것이다. 각 계층은 하위 계층을 사용, 현재 계층의 기능을 포함해 상위 계층에 제공. 위에서 바라보았을 때 아래층이 안보이는 구조라 할 수 있다. OSI 계층을 나눈 이유 역할별로 계층을 분리(독립적인 역할) ⇒ 문제 발생시 어떤 계층에 문제가 생겼는지 파악하기 쉽다. ⇒ 이상이 생긴 단계만 고칠 수 있다. 흐름을 알기 쉽다. 데이터 캡슐화 사용자 데이터가 각 계층을 지나면서 하위 계층은 상위 계층으로부터 온 정보를 데이터로 취급하며, 자신의 계층 특성을 담은 제어정보(주소, 에러 제어 등)를 헤더화 시켜..

문제 문제 설명 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다. 민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다..

문제 문제 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. 은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다. 어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다. 먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 ..

문제 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계..

최소 신장 트리(MST) 그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 찾기! 어디에서 시작하는 지 상관없이 모든 정점이 다 이어질 수 있도록 팔을 뻗는다고 생각하면 된다. 간선이 적을 때 => KRUSKAL(간선 중심) 간선이 많을 때 => PRIM(정점 중심) Kruskal 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 모든 간선을 가중치에 따라 오름차순으로 정렬 (최초 한번) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 *** 사이클을 형성하는 간선은 선택 x!** ⇒ union-find 알고리즘을 이용한다. n-1 개의 간선이 선택될 때까지 반복해서 선택 사이클을 형성하는 방법 ⇒ union-find 추가하고자하는 간선의 양끝 정점이 같이 집합에 속해있..

문제 문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다. 격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다. 상어의 마..