안녕하세요

그래프 탐색 알고리즘 그래프의 기본 구조 1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현 graph_matrix = [[0,7,5], [7,0,INF], [5,INF,0]] print(graph_matrix) 2. 입접 리스트: 리스트로 그래프의 연결 관계를 표현 graph_list = [[] for _ in range(3)] # 노드에 연결된 노드 정보 ( 노드, 거리 ) graph_list[0].append((1, 7)) graph_list[0].append((2, 5)) graph_list[1].append((0, 7)) graph_list[2].append((0, 5)) print(graph_list) 1. DFS - 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색 - 스택 자..

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 1. 다익스트라 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘 - 가장 비용이 적은 노드를 선택하기 때문에 '그리디 알고리즘' - '음의 간선'이 없을 때 정상적으로 작동 - 실제 GPS 소프트웨어의 기본 알고리즘으로 채택 - 각 노드에 대한 최단거리를 리스트에 저장해서 갱신 다익스트라 알고리즘 소스 코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) n,m = map(int, input().split()) start = int(input()) graph = [[] for i in range(n..

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 연산 속도와 메모리 공간을 최대한 활용하는 효율적인 알고리즘! 주어진 문제가 DP 문제임을 파악하는 것이 중요! 피보나치 수열 예시 점화식을 재귀 함수를 사용해 표현했을 때 fibo() 함수를 반복해서 호출하기 때문에 연산 횟수가 2^n 이 된다. def fibo_re(x): if x == 1 or x == 2: return 1 else: return fibo_re(x - 2) + fibo_re(x - 1) print(fibo_re(4)) 이렇게 매번 계산하도록 하는 과정을 해결하기 위해서 DP 사용 조건1. 큰 문제를 작은 문제로 나눌 수 있을 때 조건2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 탑다운 방식(하향식) ..

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 정렬된 데이터에서 사용 가능 시작점, 끝점, 중간점 3가지 변수 사용 찾으려는 데이터와 중간점을 반복적으로 비교하여 원하는 데이터를 찾음 ※ 시작점, 끝점, 중간점은 배열의 인덱스!! 배열의 크기가 n일 경우 처음 탐색을 시작할 때 시작점은 0, 끝점은 n-1이 된다. 시간 복잡도 : O(logN) 한번 확인 할 때마다 원소 개수가 절반으로 줄어들기 때문에 코딩 테스트에서의 이진 탐색 간단해보이지만 실전에서 제대로 짜기 어려움 단골 문제니까 꼭 외우기 0.> 탐색 범위가 2000,0000이 넘어가면 이진 탐색 고려 ※ 데이터 단위가 천만이 넘어갈 경우 시간 복잡도 O(logN)정도가 되어야 한다. 구현 방법 1) 재귀 함수 사용 def binary_s..

아 역시 파이썬이 최고.. Java에서 방황 후 돌아왔습니다. 1. 구현? 풀이를 떠올리는 것은 쉽지만, 코드 작성이 어려운 문제 ex) 특정 소숫점으로 출력, 문자열 -> 리스트 변환 처럼 사소한 조건이 많은 경우 유형1. 완전 탐색 -> 모든 경우의 수 다 계산 유형2. 시뮬레이션 -> 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행 2. 메모리 제약사항 1) 리스트 대체로 코테에서는 128 ~ 512MB로 메모리 제한 리스트의 길이가 1,000,000 일 경우 : 약 4KB 10,000,000일 경우 : 약 40KB 이다. 따라서 리스트를 여러개 선언한다면 용량 제한으로 실패할 수 있음. 예제 1) 상하 좌우 - 시뮬레이션 유형 - 연산 횟수가 이동 횟수에 비례한다. N = int(input()..

이것이 코딩테스트다 교재 공부중 그리디 알고리즘 = 현재 상황에서 지금 당장 좋은 것만 선택 = 지금의 선택이 나중에 미칠 영행은 고려하지 않는다. 언제 사용할까? 사전에 암기하지 않아도 풀 수 있을 가능성이 높은 문제이다. - 문제를 풀기 위한 아이디어를 떠올릴 수 있는 능력 평가(창의력) - 주로 가장 큰 순서대로, 가장 작은 순서대로 같은 기준을 제시해준다. - 따라서 그리디는 정렬과 자주 짝을 이뤄서 출제된다. 예제1) 500원, 100원, 50원,10원 동전을 최소 갯수로 거슬러 주는 문제(p.87) 조건, N은 항상 10의 배수 (동전 단위도 항상 배수이다.) import java.io.BufferedReader; import java.io.IOException; import java.io.I..

전송 계층이란? 전송 계층(Transport layer)은 계층 구조의 네트워크 구성요소와 프로토콜 내에서 송신자와 수신자를 연결하는 통신 서비스를 제공한다. 전송 계층은 연결 지향 데이터 스트림 지원, 신뢰성, 흐름 제어, 그리고 다중화와 같은 편리한 서비스를 제공한다. 오류를 점검하고, 오류 발생 시 데이터를 재전송하도록 요청 전송된 데이터의 목적지를 식별 대표적인 전송 계층 프로토콜로는 TCP, UDP가 있다. TCP 는 연결형, UDP는 비연결형 통신이다.

응용계층에는 메일을 송수신하기 위한 프로토콜이 있다. 메일을 송신하는데에 SMTP , 메일을 수신하는데에 POP3나 IMAP4을 사용한다. 1. SMTP (Simple Mail Transfer Protocol) 사용자 컴퓨터에서 메일 서버로 송신, 메일 서버 사이의 통신에서 사용된다. SMTP는 25번 포트를 사용한다. SMTP 동작 흐름 세션 시작을 통지한다. 송신자의 메일 주소를 통지한다. 목적지 메일 주소를 통지한다. 메일 본문 전송을 통지한다. 메일 본문을 송신한다. 세션 종료를 통지한다. SMTPS SMTP Secure로 SMTP에 보안을 적용한 프로토콜이다. SMTP는 메일 내용이 암호화되지 않아 스니핑을 통하여 쉽게 확인할 수 있다. 2. POP3 (Post Office Protocol) P..

파일 전송 프로토콜(File Transfer Protocol)의 약자로 TCP/IP 네트워크 상에서 컴퓨터들이 파일을 교환하기 위해 1971년에 최초로 공개된 통신 규약이다. 네트워크 상에서 컴퓨터들이 파일을 교환하기 위한 목적으로 개발되었다. FTP에는 20번, 21번 포트를 사용하는데 20번 포트는 데이터 전송을 위해 사용되고, 21번 포트는 명령과 응답 등의 제어정보를 위해 사용된다. FTP 전송모드 전송모드 기본 값은 Active Mode이고 클라이언트가 Active 또는 Passive 모드를 선택할 수 있다. 데이터 포트 요청은 Active의 경우 클라이언트가, Passive의 경우 서버가 요청한다. 1) 능동 연결 (Active mode) 클라이언트가 서버의 21번 포트로 접속 후 명령을 송수..

웹 페이지에 접속하기 위한 프로토콜로 HTTP가 있다. HTTP(Hypertext Transfer Protocol)는 웹에서 이루어지는 모든 데이터 교환의 기초이며 클라이언트-서버 프로토콜이다. HTTP 기반 시스템의 구성요소 HTTP는 응용 계층의 프로토콜로 TCP/IP 위에서 작동한다. 클라이언트는 웹 사이트를 보기 위해 서버의 80포트를 사용해서 HTTP 통신을 한다. 클라이언트에서 HTTP 요청을 보내고 서버에서 HTTP 응답을 반환한다. 요청과 응답 사이에는 게이트웨이 또는 캐시 역할을 하는 프록시 등이 있다. 1. 클라이언트 : 사용자 에이전트 사용자를 대신하여 동작하는 모든 도구, 주로 브라우저가 수행 페이지를 표시하기 위해서 HTML 문서를 가져오기 위한 요청, 파일 내의 하위 리소스를 위..