ComputerScience

정수론과 조합론

유클리드 호제법 : 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다. 1. a % b = r 2. gcd(a, b) = gcd (b, r) static long gcd(long a, long b) { while(b != 0) { long r = a % b; a = b; b = r; } return Math.abs(a); } 확장 유클리드 호제법 : 특정 방정식을 만족하는 해를 구할 수 있다. public class P3955 { static int T; static long A, B; public static void main(Stri..

자료구조

자료구조(Data Structure)란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법을 이야기 한다. 자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다. - 선형 자료구조 : 데이터가 일렬로 나열되어 있음. * 배열 (Array) * 연결리스트 * 스택 * 큐 - 비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음. * 트리 * 그래프 배열 : 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조. * 배열의 특징 - 데이터 접근이 용이. - 데이터 삽입 / 삭제가 어려움 (뒤로 1칸식 밀어주어야함. 최악의 경우 O(n)) - 구조가 간단하여 프로그램 작성이 쉬움. 연결리스트 : 각 노드가 데이터와 포인터를 가지고 일렬로 연결..

알고리즘 기초

### 알고리즘이란? 고대 페르시아의 수학자 알콰리즈미에서 유래되어 문제를 해결하기 위한 여러 동작들의 모임. 알고리즘을 이용하기 위해서는 복잡한 구조의 코드를 정확하게 구현할 수 있는 구현력이 필요하다. ### 알고리즘의 조건 - 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. - 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. - 입력 : 정의된 입력을 받아들일 수 있어야 한다. - 출력 : 답으로 출력을 내보낼 수 있어야 한다. - 유한성 : 특정 수의 작업 이후에 정지해야 한다. - 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 깊이우선탐색 (Depth First Search) - 그래프 탐색 방법의 한가지로 한 경로로 탐색하다 특정 상황에서 최대한 깊숙하게 들어..

백준 1713번 Java 풀이

후보 추천하기성공출처분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 4956 1579 1271 33.351% 문제 월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다...

블록체인이란?

블록체인(영어: block chain, blockchain) 근본적으로 분산 데이터 저장기술의 한 형태로, P2P[1] 방식의 네트워크에서 '블록'이라고 하는 소규모 데이터들을 체인 형태로 연결 지어 분산 데이터 저장 환경(블록체인)에 저장한 것이다. 누구라도 임의로 수정할 수 없고, 누구나 변경의 결과를 열람할 수 있는 특징을 갖고 있다. 블록체인은 다수가 데이터를 저장, 증명하기 때문에 중앙관리자가 존재하지 않고(탈중앙화), 임의의 사용자가 수정을 하기 몹시 어려운 구조로 되어 있어(데이터 신뢰성) 효과적인 기술이다. 블록체인 기술을 기반으로 비트코인은 2008년 10월 사토시 나카모토(가명)가 개발하여, 2009년1월에 소스가 배포되었다. 사토시는 암호학적 증명에 기반해, 개인 대 개인간의 거래에서..

11. 라우터 (ROUTER)

라우터(Router) 서로 다른 네트워크간 통신하기 위해서, 브로드캐스트 영역을 나눠주기 위해서 사용한다. 한마디로 ‘지능을 가진 경로배정기’라고 말할 수 있다. 예를 들어, 외부의 어떤 인터넷 사이트를 찾아가는 데이터가 있다면 라우터는 이 데이터를 목적지까지 가장 빠르고 효율적인 길을 스스로 찾아 안내해 주는 능력을 가지고 있다. 라우터의 2가지 역할 1. 경로 설정(Path Determination) : 데이터 패킷이 목적지까지 갈 수 있는 길을 검사하고 어떤 길로 가는 것이 가장 적절한지를 결정함. 2. 스위칭(Switching) : 그 길이 결정되면 그쪽으로 데이터 패킷을 스위칭 해줌. 라우터는 가장 좋은 길을 찾기 위해서 라우팅 알고리즘, 즉 라우팅 프로토콜이 사용된다. 라우팅 테이블이란 것도 ..

10. VLAN(Virtual LAN)

VLAN : 한 대의 스위치를 마치 여러 대의 분리된 스위치처럼 사용하고, 또 여러 개의 네트워크 정보를 하나의 포트를 통해 전송할 수 있다. 하나의 스위치에 연결된 장비들도 브로드 캐스트 도메인이 서로 다를 수 있음. VLAN 적용 전 VLAN 적용 후 회사의 3개의 네트워크가 존재 한다면, 라우터에서는 3개의 이더넷 인터페이스가 나와야 하고, 서로 다른 스위치에 연결되어야 한다. 본관이 아닌 별관의 네트워크를 구성한다면, 별관에 스위치를 따로 설치하고 같은 네트워크에 속한 스위치끼리 연결해 주어야 한다. 하지만 VLAN을 사용한다면, 스위치로 하나의 링크만을 이용해서도, 3개의 네트워크 정보를 실어 보낼 수 있다. 스위치도 여러 개의 브로드 캐스트 영역을 나누어 줄 수 있게 된다. VLAN은 스위치에..

9. 스패닝 트리 알고리즘 (STP)

스패닝 트리 프로토콜 네트워크당 하나의 Root Bridge를 갖는다. Non root Bridge는 무조건 하나 씩의 Root port(Root와 연결된 링크의 포트)를 갖는다. Segment(브리지 또는 스위치 간에 서로 연결된 링크)당 하나씩의 지정포트(Designated port)를 갖는다. 다음 단계로 순서를 정함 1. 누가 더 작은 Root Bridge ID를 가졌는가? 2. Root Bridge까지의 Path Cost 값은 누가 더 작은가? 3. 누구의 BID(Sender BID)가 낮은가? 4. 누구의 포트 ID가 더 낮은가? 스패닝 트리 정보를 자기들끼리 주고받기 위해 BPDU(Bridge Protocol Data Unit) 프레임을 사용. Root BID, Root Path Cost, ..