목록컴퓨터과학 (42)
넘치게 채우기
통신 및 네트워크 개요 통신을 한다는 것은, 정보다 네이터를 공유하는 것이다. 네트워크란? 네트워크(network): 상호 연결이 가능한 통신 장치의 집합체이다. 통신 장비란 컴퓨터, 데스크톱, 스마트iot장치, 스마트폰, 스마트워치 등의 호스트(host)도 있고, 이외에도 라우터, 스위치, 모뎀 등의 연결 장치(connectiong device)도 있다. 네트워크의 평가기준은 다음과 같다: 성능(performance) - 전달시간, 응답시간 등. 흔히 처리율(throughtput)과 지연(delay)이라는 두 가지 척도로 평가된다. 신뢰성(reliability) - 고장의 빈도수, 해결시간, 안정성 등.. 보안(security) - 데이터 보호, 정책, 침해나 손실시 복구절차 등. 네트워크의 종류 LA..
스택은 LIFO, 큐는 FIFO 자료구조이다. 어떻게 하면 두 개의 스택으로 하나의 큐를 구현하는데, 대부분의 경우에서 O(1)으로 구현할 수 있을까? 하나를 입력용 스택, 하나를 출력용 스택이라고 해보자. 입력용 스택은 입력만 받는다. 출력용 스택은 출력만 한다. 단, 출력용 스택이 empty인 경우, 입력용 스택의 원소들을 pop하여 출력용 스택에 push하면 된다. 이때 출력용 스택에는 입력의 역순으로 들어오게 되어 기존의 출력 순서가 반대로 되어 FIFO가 된다. 이 경우만 제외하고는, O(1)의 시간복잡도를 가진다. class MyQueue { stack i,o; public: MyQueue() { } void push(int x) { i.push(x); } int pop() { int x; i..
프로그래밍 언어에서 if문을 자주 이용하곤 한다. 아래의 코드에서 어떤 결과가 나올까? def funcA(): print("A") return False def funcB(): print("B") return True if funcA() and funcB(): print("참") else: print("거짓") A B 거짓 A 거짓 거짓 정답은 2번이다. and논리연산을 할 때, 앞의 오퍼랜드가 false인 경우, 뒤의 오퍼랜드를 확인하지 않는다. 이 방법을 통해서 더 간결하고 가독성이 좋은 코딩을 할 수 있다. 반대로, or의 경우도 그렇다. or논리연산을 할 때, 앞의 오퍼랜드가 true인 경우, 뒤의 오퍼랜드를 확인하지 않는다. 실제 사용 예시: 알고리즘 문제풀이에서 슬라이딩 윈도우를 구현할 때 L..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bKaNj8/btsBaWfOUS0/Pr2aHV0rEfxD9eKpFyhK30/img.png)
#include int countOnesInDecimal(int n) { int count = 0; while (n) { std::cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cPXoHZ/btsybuPoXKt/nQyqed2HANHbWafi8sESHK/img.png)
프로그램이 실행되기 위해서는, 프로그램이 메모리에 로드가 되어야 합니다. 프로그램에서 쓰이는 변수들을 저장할 메모리도 필요합니다. 컴퓨터의 운영체제는 프로그램의 실행을 위한 다양한 메모리 공간을 제공합니다. 프로그램은 4가지의 메모리 공간을 제공받습니다. 1.코드(code)영역 2.데이터(data)영역 3.스택(stack)영역 4.힙(heap)영역 코드 영역(code) 실행될 프로그램의 코드가 저장되는 영역입니다. 텍스트(code)영역이라고도 불립니다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리합니다. 데이터 영역(data) 전역 변수, 정적 변수가 저장됩니다. 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램의 종료와 함께 소멸됩니다. 데이터 영역은 세 가지로 나뉩니다: .dat..
https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/ Introduction to Disjoint Set (Union-Find Algorithm) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.o..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/EZ8xG/btstyg8vKC6/x2k8hRoK0c6HMaT26Uegv1/img.png)
벨만-포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과의 비교 다익스트라 알고리즘은 양수일 때에만 사용이 가능하지만, 벨만포드 알고리즘은 음수에서도 사용이 가능하다. 시간 복잡도는 다익스트라 알고리즘이 더 효율적이다. 벨만포드 알고리즘 1. 시작 노드를 설정한다. 2. 시작 노드를 제외한 모든 노드의 거리를 INF로 구성한다. 3. 현재 노드의 모든 인접 노드를 탐색하며 기존의 연결 관계보다 현재 노드를 거치고 가는 것이 더 짧을 경우 갱신한다. 4. 모든 노드에 대해 반복한다. 5. 모든 노드에 대해 반복하고 나서도 갱신된다면, 그건 음수 사이클이 존재한다는 의미이다. 벨만포드 알고리즘 예시 1.노드 A에서부터 시작한다. 2 < INF, 4 < IN..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ujynY/btstCXHk2n6/J7ErqDrmRaNQnhBe3bdta1/img.png)
순서가 정해져 있는 일련의 알고리즘을 수행해야 할 때 사용되는 알고리즘이다. '사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것' 이다. 대표적으로 선수학습 과목 등의 예시가 있다. 진입차수와 진출차수 진입차수(indegree): 특정 노드로 들어오는 간선의 개수(노드로 오기 전의 조건) 진출차수(outdegree): 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정 반복: 큐에서 원소를 꺼내서 그 노드가 향하는 노드의 진입차수를 1 낮추기(그 간선 방문처리) 진입차수가 0이 된 노드를 큐에 넣기 위상 정렬 알고리즘의 예시 1. 진입차수가 0인 노드부터 큐에 넣고 시작한다. 큐에서 요소를 하나 꺼낸다. 꺼내진 요..
컴퓨터는 이진수를 사용한다. 비트 연산을 통해서 우리는 더 빠른 연산을 할 수 있다. 비트마스킹의 장점 1. 빠른 연산 - 비트마스킹 연산은 상수 시간에 연산된다. 2. 간결한 코드 - 비트마스킹을 통해 간결한 코드 표현이 가능하다. 3. 적은 메모리 사용 - 큰 크기의 숫자를 적은 메모리로 표현이 가능하다. 비트 연산들 and(&) 둘 다 참일 때에만 1 반환 ex) 1010 & 1111 = 1010 or(|) 둘 중 하나만 참일 때 1 반환 ex) 1000 | 1101 = 1101 xor(^) 둘이 서로 다를 때 1반환 ex) 1010 ^ 1111 = 0101 not(~) 반대 값을 반환 ex) ~1010 = 0101 시프트 연산() 비트 자릿수를 옮김. 001101
십진수를 이진수로 표기하고, 이진수 표기에서 1을 구하고 싶다면, 십진수 i를 2로 나눈 값 i/2의 1의 개수에, i가 홀수면 1을 더하고, 짝수인 경우 더하지 않으면 된다. #include // 십진수를 이진수로 변환하고 1의 개수를 구하는 함수 int countOnesInBinary(int n) { int count = 0; while (n > 0) { count += n % 2; // 현재 비트가 1이면 count에 1을 더함 n /= 2; // 십진수를 2로 나눔 } return count; } int main() { int i = 25; // 예시로 25를 사용 int binaryCount = countOnesInBinary(i); std::cout