Google DSC Sookmyung

BFS, DFS BFS와 DFS는 그래프를 탐색하는 알고리즘 기법이다. 깊이 우선 탐색(Depth-First Search) DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색한다. 즉, 그래프에서 깊은 부분을 우선적으로 탐색한다. 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 스택(stack)을 사용해서 구현하며, 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다. 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다. 검사하지 않을 경우 무한루프에 빠진다. 탐색 순서 0번을 시작으로 왼쪽에 위치한 1번 노드를 우선적으로 탐색 3번 노드가 끝이기에 이전 단계로 ..

⭐ 9주차 주제: 정렬, BigO [알고리즘] 알고리즘이란? : 컴퓨터 프로그램이 어떤 문제를 해결하기 위해 필요한 명령어들의 집합 좋은 알고리즘을 찾고 언제 써야 할지 알아야 중요한 프로그램을 만들 수 있습니다. Ex) 구글 행아웃은 어떻게 실시간 영상을 전송하지? 오디오, 비디오 압축 알고리즘을 사용 구글 맵스가 어떻게 숙명여대까지의 경로를 찾지? 경로 찾기 알고리즘을 사용 픽사는 어떻게 가상 공간에 캐릭터의 3D 모델 조명을 반영해 색칠하지? 렌더링 알고리즘을 사용 나사는 태양광 패널을 어디로 언제 움직일지 알까? 최적화 & 스케줄 알고리즘을 사용 정렬 리스트의 항목을 오름차순 또는 내림차순으로 정렬해 놓으면 사람이나 컴퓨터가 리스트에서 어떤 항목을 찾을 때 이진검빠르고 편리하게 찾을 수 있습니다...

C++에서 문자열 다루기 string 클래스의 특징 - 문자의 끝에 null 문자 등이 포함되지 않음 - 배열처럼 한 문자씩 다룰 수 있음 - string 클래스끼리는 + 연산자로 문자열 합치기 가능 - 문자열 사전순 정렬 가능 - 다양한 멤버함수 존재 멤버 함수 - str.front(): 맨 앞 문자 반환 - str.back(): 맨 끝 문자 반환 - str.size() or str.length(): 문자열 길이 반환 - to_string(): 숫자>문자열 - str.capacity(): capacity 값 확인 - str.reverve(n): 미리 n byte 할당 - str.empty(): 빈 문자열인지 확인 - str.clear(): 문자열을 없앰 (capacity 값은 유지) - str1.app..

GET, POST HTTP Method HTTP Method는 클라이언트와 서버 사이에 요청과 응답을 전송하는 방식을 말한다. 주요 메소드 GET 리소스 조회 POST 요청 데이터 등록 PUT 해당 리소스 대체, 해당 리소스가 없다면 생성 (리소스 전체 변경) PATCH 리소스 부분 변경 DELETE 리소스 삭제 GET 방식 주로 데이터를 읽거나 검색할 때 사용되는 메소드이다. 데이터 조회에 대한 정보는 body에 넣지 않고 쿼리 스트링을 통해 보낸다. (*쿼리 스트링 : URL 끝에 ?뒤에 key1=value1&key2=value2 구조로 쌍을 이루는 요청 파라미터) GET /members/100?username=inpa&height=200 GET방식은 이렇게 url에 담겨가기 때문에 전송할 수 있는 ..

Cookie와 Session 6주차에서 공부했던 HTTP와 HTTPS 내용에서 HTTP는 두 가지의 큰 특징을 가졌다. 비연결 지향 (Connectionless) 클라이언트가 request를 보내고 그에 대한 response를 서버가 보내면 바로 연결 종료 상태 정보 유지X (Stateless) 연결을 끊는 순간 클라이언트와 서버의 통신은 끝나고 상태 정보를 유지하지 않음 이러한 특징때문에 HTTP프로토콜을 사용한 연결은 다음과 같은 단점을 가졌다. 모든 요청 간 의존 관계가 없음 연결을 유지하지 않기 때문에 현재 접속한 사용자와 이전에 접속한 사용자가 같은 사용자인지 아닌지 구별할 방법 없음 계속해서 연결을 유지하지 않기 때문에 통신할 때마다 클라이언트는 매 요청마다 인증을 해야 함 따라서 이러한 문제..

동적계획법(DP) 동적계획법(dynamic programming)은 자주 볼 수 있는 디자인 패러다임 중에 하나입니다. 동적 계획법에서는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 뒤, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다. 동적계획법을 왜 사용하는 걸까요? 일반적인 재귀 방식 또한 DP와 유사하다고 볼 수 있습니다. 그러나 재귀를 단순히 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적으로 계산됩니다. 가장 많이 쓰이는 예시는 피보나치 수열입니다. 피보나치 수열을 재귀로 구현할 시 return f(n) = f(n-1) + f(n-2)이라는 단순한 식이 나옵니다. 이렇게 구현할 시, 위의 트리와 같은 호출이 일어납니다. 같은 값을 구하는 과정이 반복되서 일어나는 것을 확인..

HTTP와 HTTPS HTTP HypterText Transfer Protocal 인터넷 상에서 클라이언트와 서버가 자원을 주고 받을 때 쓰는 통신 규약 80번포트를 사용함. 따라서 HTTP 서버가 80번 포트에서 요청을 기다리고 있으며 클라이언트는 80번 포트로 요청을 보내게 됨. 팀 버너스 리에 의해 처음 설계 WWW 기반에서 세계적인 정보를 공유하는데 큰 역할을 함. 텍스트 교환이므로 누군가 네트워크에서 신호를 가로채면 내용이 노출되는 보안이슈 존재 구조 애플리케이션 레벨의 프로토콜. TCP/IP위에서 작동. 상태를 가지고 있지 않은 Stateless프로토콜 stateless프로토콜? 서버 사이드에 클라이언트와 서버의 동작과 상태정보를 저장하지 않는 형태. 서버 응답이 클라이언트와의 세션 상태에 독..

이진탐색 이진탐색은 배열 내부의 데이터가 정렬되어 있을 때, 원하는 값을 매우 빠르게 찾을 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있으며, 위치를 나타내는 변수를 총 3개 사용한다. 탐색하고자 하는 범위의 시작(start), 끝(end), 중간(mid)의 값이 필요하다. 찾으려는 데이터(target)와 중간점 위치에 있는 데이터를 비교하며 원하는 데이터를 찾아나간다. 한 번 탐색할 때마다 확인하는 데이터의 갯수가 절반씩 줄어든다는 점에서 O(logN)의 시간복잡도를 갖는다. 배열 전체의 중간값을 target값과 비교한다. 중간값이 target보다 작으면, 오른쪽 부분만 다시 탐색한다. 중간 인덱스 이전의 값은 확인하지 않고, start값을 mid 한칸 뒤로 이동시킨다..

목차 개념 정렬 알고리즘 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 그 외 정렬 알고리즘 병합 정렬 버블 정렬 힙 정렬 정렬 알고리즘의 시간 복잡도 비교 파이썬의 정렬 라이브러리 문제 10825 국영수 10814 나이순 정렬 11652 카드 18870 좌표 압축 2108 통계학 23881 알고리즘 수업 - 선택 정렬 1 스터디 저장소 개념 다음은 이것이 취업을 위한 코딩테스트다 with 파이썬에서 발췌한 내용입니다. 정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(Binary Search)이 가능해진다. 선택 정렬 출처: https://codepumpkin.com/selection-sort-algorithms/ 데이터가 ..

TCP/IP (흐름/혼잡 제어, 3-way/4-way handshake) TCP/IP TCP와 IP의 개념에 대해서 먼저 알아보자! TCP/IP는 OSI 7계층 에서 3계층과 4계층을 다루는 프로토콜(통신 규약)이다. TCP/IP는 패킷 통신 방식의 인터넷 프로토콜인 IP와 전송 조절 프로토콜인 TCP로 이루어져 있다. IP OSI 7계층에서 3계층(Network Layer) 한 EndPoint가 다른 EndPoint로 가고자 하는 경우 경로와 목적지를 찾아줌 = Routing 패킷 전달 여부 보증 X 패킷을 보낸 순서와 받는 순서가 다를 수 있음 TCP OSI 7계층에서 4계층(Transport Layer) 송신자와 수신자의 논리적 연결(Connection)을 담당, 신뢰성 있는 연결 유지하도록 도움 ..