Redddy's Devlog

이진 탐색 (Binary Search) 이진 탐색이란 정렬되어 있는 데이터에서 특정 데이터를 찾을 때 사용된다. 이진 탐색 말고도 탐색법은 여러개가 있는데, 그중 순차 탐색은 리스트에 저장된 데이터를 처음부터 끝까지, 즉 첫번째 인덱스부터 마지막 인덱스까지 순서대로 탐색하는 방법이다. 이진 탐색의 탐색 방법은 우선 데이터의 중간값과 타겟을 확인한다음 만약 중간값이 타겟값보다 작다면 이제 중간값보다 더 큰 데이터들만 확인하고, 만약 중간값이 타겟값보다 크다면 중간값보다 작은 데이터들만 확인하면 된다. 다시말해 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 우리가 어렸을 때 했던 업앤다운 숫자찾기 게임도 이진 탐색을 사용하면 순차탐색보다 빠르게 찾아낼 수 있다. 1부터 10까지의 자연수 중 하나를..

정렬 (Sorting) 정렬은 데이터를 특정한 기준에 따라서 순차적으로 나열하는 것이다. 흔히 사용하는 내림차순이나 오름차순 역시 이 정렬을 통해 이루어진다. 이진탐색이라는 탐색기법은 정렬과정을 거친 후에만 사용이 가능하다. 정렬알고리즘은 Comparison Sorting Algorithm(비교방식 알고리즘)과 non - Comparison Sorting Algorithm 이렇게 크게 두가지로 나눌 수 있다. 비교방식 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등이 있고, non-비교방식 알고리즘에는 계수 정렬이 있다. 선택 정렬 (Seletion Sort) 선택 정렬은 배열에서 가장 작은 데이터를 선택하여 다른 데이터와 자리를 바꾸는 알고리즘이다. 일반적으로 쉽게 떠올릴 수 있다. 정렬되지 않은 배열에서..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..

그래프 : Graph DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자. 우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 그래프를 표현하는 방법은 크게 두가지가 있다. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하..

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 아래와 같은 함수가 재귀 함수이다. def recursive_function(): print("재귀 함수를 호출합니다.") recursive_function() recursive_function() 그러나 이 코드를 실행시킨다면 "재귀 함수를 호출합니다." 라는 문장을 출력하다가 어느 순간 에러를 내며 멈출 것이다. RecursionError: maximum recursion depth exceeded while calling a Python object 이 오류 메세지는 재귀의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 그 한계를 벗어났기에 다음과 같은 메세지를 출력한 ..

구현이란? 구현(Implementation)이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. 물론 어떤 문제를 풀던 간에 소스코드를 작성하는 과정은 필수이다. 그러나 구현이라고 따로 분류하는 문제들은 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 완전 탐색과 시뮬레이션은 모두 구현이 핵심이 되는 경우가 많다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 이것이 코딩테스트다를 읽고 정리한 내용입니다.

그리디 알고리즘이란? 한국어로 탐욕이라는 뜻의 그리디 알고리즘(Greedy Algorithm)은 단순하만 강력한 문제 해결 방법이다. 탐욕적으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이 바로 탐욕법, 그리디 알고리즘이다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 다른 알고리즘과는 달리 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 유형의 문제이다. 다음번에 다룰 최단 경로, 정렬 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 ..

표준화 기구의 종류는 이전글에서 설명했으니 넘어가도록 하고 그중 가장 주목받고 있는 것은 국제표준화기구(ISO)와 전기전자기술자협회(IEEE)이다. 국제 표준화 기구(ISO)는 과학, 기술, 지적활동 등등의 세계 상호간의 협력을 위해 1946년에 설립되었다. ISO가 OSI(Open System Interconnction) 7 계층을 제안하였다. (주목받게 된 이유중 하나!) 📌OSI 7계층 물리계층 데이터 링크계층 네트워크계층 전송계층 세션계층 표현계층 응용계층 이렇게 7계층이 있다. 7계층으로 나눈 이유는 네트워크에 문제가 발생했을시 오류가 발핸하는 구역만 건드리고 다른 단계의 장비 및 소프트웨어는 건들이지 않기 위해서이다 ❗1계층 - 물리계층(Physical Layer) 물리계층에서는 어떤 데이터를..

📌프로토콜의 기능 단편화(Segmentation)와 재조립(Reassembly) : 너무 큰 데이터를 이동에 용이한 크기로 자르는 것이 단편화 이것을 다시 복귀시키는 것이 재조립 캡슐화(Encapsulation) : 캡슐안에 숨기는 것처럼 은닉시키는 것을 캡슐화라고 한다. 데이터를 은닉하는 이유는 파손방지 즉 안정성을 위함. 데이터 앞에 제어정보(header)를 부착. 또다른 이유는 보안! 연결제어(Connection Control) : 연결(세션)을 제어한다. 비연결형과 연결형이 있다. 비연결이란 연결이 되어 있지 않아도 데이터를 보낼 수 있고 반대로 연결형은 연결이 되야만 네트워크가 가능하다. 연결형의 예로는 통화가 있고, 비연결의 예는 편지가 있다. 흐름제어(Flow Control) : 통신속도 등..

📌데이터(Data) 실제 생활의 많은 일들을 간단히 문자, 숫자, 기호 등으로 표현하여 사람이나 컴퓨터가 처리할 수 있도록 만든 자료 📌정보(Information) 데이터를 가공하거나 특정한 의미를 부여하여 사람들 사이의 의사 결정 도구로 활용할 수 있는 값 예를 들어 20이라는 숫자 데이터가 있는데 다른 사람에겐 아무 의미 없는 데이터일수 있지만 나에게는 나이라는 정보가 된다. 범위는 데이터가 더 크고 그 다음이 정보 그리고 가장 위에는 지식이 있다. 📌정보통신의 3대 목표 정확성, 효율성, 보안성 📌정보통신의 3요소 정보원(송신원), 전송매체(전송기기), 정보처리원(수신원) 출처: https://slidesplayer.org/slide/14534524/ 📌네트워크의 발전과정 음성 회선 공중 교환 전화..