본문 바로가기

전체 글

 (147)
Every CS - Network 03 - 네트워크 계층과 전송 계층 network 03 - 네트워크 계층과 전송 계층1. 네트워크 계층 - IP1. IP의 목적과 특징IP의 목적 : 주소지정과 단편화주소지정 : 네트워크 간의 통신 과정에서 호스트를 특정하는 것단편화 : 데이터를 여러 IP패킷으로 올바르게 쪼개어 보내는 것IP의 특징 : 신뢰할 수 없는 통신, 비연결형 통신1. 주소 지정과 단편화주소 지정은 IP주소를 통해 이루어지며, 이는 IP 패킷 해더를 통해 알 수 있다.| 참고로, 오늘날의 IP는 IPv4와 IPv6의 2가지 종류가 있고, 둘 중 IPv4가 더 많이 사용된다.송신지 IP 주소와 수신지 IP 주소 필드에는 송수신지를 식별할 수 있는 IP 주소가 명시된다.하나의 IP주소는 총 32비트의 크기로 구성되고, 0~255 범위의 10진수 4개로 표기된다.이 때..
Baekjoon 16946. 벽 부수고 이동하기 4 / Python 16946. 벽 부수고 이동하기 4난이도 : 골드 2소요 시간 : 40분날짜 : 2024.12.24언어 : 파이썬알고리즘 유형 : bfs, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 센다.2. 해결 방식시간 줄이기*맵의 크기가 최대 1000 * 1000 이기 때문에 그냥 bfs를 돌리면 시간복잡도가 10^12로 시간초과가 난다.시간을 줄이기 위해 집합과 인덱싱을 사용한다.인덱싱 -> 유니온파인드 알고리즘과 유사한 방법풀이벽인 곳을 찾는다.벽의 상하좌우에서 벽이 아닌 곳을 찾는다.벽이 아닌 곳에서 bfs를 돌린다.이 때, bfs를 돌려서 이동가능한 공간에 인덱스 번호를 부여하고,인덱스 번호에 맞는 리스트를 만들어..
Every CS - Network 02 - 물리 계층과 데이터 링크 계층 Network 02 - 물리 계층과 데이터 링크 계층01. 이더넷이더넷이란 통신 매체를 통해 신호를 송수신하는 방법, 데이터 링크 계층에서 주고받는 데이터 형식등이 정의된 기술을 말한다.현재 대부분의 LAN은 이더넷을 기반으로 구현되어 있다.이더넷 표준이더넷은 IEEE 802.3이라는 이름으로 국제 표준화된 기술이다.IEEE 802.3은 '이더넷과 관련된 다양한 표준들의 모음'이라고 할 수 있고, 뒤의 알파벳을 통해 버전을 나타낸다.이더넷의 종류를 외울 필요는 없다.밑의 2가지만 기억하면 된다.오늘날의 LAN 대부분이 이더넷 표준을 따르기 때문에 대다수의 LAN 장비들이 특정 이더넷 표준을 따른다.이더넷 표준이 달라지면 통신 매체의 종류를 비롯한 신호 송수신 방법, 나아가 최대 지원 속도가 달라질 수 있..
알고리즘 유형공부 - 연결 리스트 (Linked List) 연결리스트1. 개요연결리스트란 메모리 상에서 비연속적으로 존재하는 데이터 구조로, 각 데이터(노드)가 다음 데이터의 주소를 포함하고 있다.배열과 달리 고정된 크기가 없고, 동적으로 크기를 조절할 수 있어 데이터 삽입과 삭제가 용이하다.하지만 순차 접근만 가능하여 탐색 속도가 느릴 수 있다.1-0. array와 비교 및 시간 복잡도arraylinked list장점무작위 접근 가능빠른 자료 삽입, 삭제, 자유로운 크기 조절단점느린 자료 삽입, 삭제, 크기 조절 불가능순차 접근만 가능, 메모리 추가 할당 필요시간복잡도탐색 (Search): O(N) (순차 접근 필요)삽입 (Insert): O(1) (노드 추가 시)삭제 (Delete): O(1) (노드 삭제 시)1-1. 단순 연결 리스트단순 연결 리스트는 각 ..
Baekjoon 2143. 두 배열의 합 / Python 2143. 두 배열의 합난이도 : 골드 3소요 시간 : 25분날짜 : 2024.12.23언어 : 파이썬알고리즘 유형 : 이분탐색, 누적 설명 보기전에 문제 풀어보러 가기1. 문제 설명정수 t와 배열 a, 배열 b 가 주어진다.배열 a와 배열 b에서 각각 모든 원소가 연속된 배열을 선택한다.선택된 배열들의 숫자의 합이 t 가 되는 경우의 수를 구한다.2. 해결 방식배열a 와 배열 b 에서 나올 수 있는 모든 합을 구해서 딕셔너리형태로 저장했다.배열a 를 순회하여 그 값(key)과 개수(value)를 구하고 배열 b에서 t - key의 value(개수)를 찾아서 곱한 후, 결과에 누적한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/pyth..
Baekjoon 15681. 트리와 쿼리 / Python 15681. 트리와 쿼리난이도 : 골드 5소요 시간 : 10분날짜 : 2024.12.23언어 : 파이썬알고리즘 유형 : dfs, dp 트리, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명트리 구조의 그래프가 주어지고, 루트 노드가 지정된다. 각 노드 u를 루트로 하는 서브트리의 정점 수를 계산한다. 2. 해결 방식자기 자신을 포함 자식노드를 탐색하고 결과를 누적시킨다. 3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")sys.setrecursionlimit(1e10)# input = sys.stdin.readlinen, r, q = map(int, input().split()) # 2 ≤..
Baekjoon 2098. 외판원 순회 / Python 2098. 외판원순회난이도 : 골드 1소요 시간 : 45분날짜 : 2024.12.22언어 : 파이선알고리즘 유형 : 비트마스킹, dp, dfs설명 보기전에 문제 풀어보러 가기1. 문제 설명n 개의 도시가 주어진다.도시의 연결은 비용으로 연결된 비대칭그래프이다.최소의 비용으로 모든 도시를 순회하고 돌아와야 한다.2. 해결 방식비트마스킹과 DP....(그리고 dfs)DP 배열 설명 : dp는 2차원 배열로써 dp[i][j] 는 도시 i에 도달했고, 방문 상태 j 일 때의 최소비용을 나타낸다.비트마스킹 : 방문 상태 j 는 비트마스킹으로 나타낸다. n의 범위가 2 dfs에서의 가지치기 3-1. 모든 도시를 방문 한 경우 : 최소값을 갱신할 수 있다. 3-2. 최소비용이 이미 있는 경우 : 그 값을 재사용한다...
Baekjoon 1562. 계단 수 / Python 1562. 계단 수난이도 : 골드 1소요 시간 : 20분날짜 : 2024.12.21언어 : 파이썬알고리즘 유형 : 비트마스킹, 비트집합, 다이나믹프로그래밍설명 보기전에 문제 풀어보러 가기1. 문제 설명계단수 = 인접 한 수 끼리의 차이가 1은 수길이 N인 계단 수의 개수를 구하는 문제0으로 시작하면 안된다.2. 해결 방식비트와 dp를 사용한다.dp[i][j][k]의 값은 i자리, j로 끝나는, 비트 k 를 가진 수 이다.이 때, 비트 k라는 것은, 10자리의 비트로써, 0부터 9까지의 수를 체크하는 역할이다. -> 모두 1인 1111111111이 되어야 계단수의 조건을 만족한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/i..
Every CS - Network 01 - 네트워크 개요 네트워크 01 - 네트워크 개요네트워크 : 여러 대의 장치가 그물처럼 연결되어 정보를 주고받는 통신망1. 네트워크 개요1-1. 네트워크의 기본 구조네트워크의 형태 : 노드와 간선으로 이루어진 그래프의 형태노드와 노드 사이의 연결 구조를 네트워크 토폴로지 라고 한다. 이 노드의 배치 방식에 따라 망형, 트리형, 링형, 성형, 선형 등으로 나눈다. 이때, 네트워크의 가장자리에 위치하면서 네트워크를 통해 주고받는 정보를 최초로 송신, 최종적으로 수신하는 노드를 호스트라고 한다. 요청을 보내는 클라이언트와 응답을 보내는 서버간에 정보를 주고 받는다.1-2. LAN과 WANLAN(Local Area Network) : 근거리 네트워크 -> 공유기를 기준으로 구축된 네트워크WAN(Wide Area Network) ..
알고리즘 유형공부 - 이분탐색(Binary Search)과 투포인터(Two Pointer) 이분탐색과 투포인터목차이분탐색 1-1. 개요 1-2. 알고리즘 원리 1-3. 예시 1-4. 시간복잡도 1-5. Bisect 라이브러리 1-6. 추천문제 투포인터 2-1. 개요 2-2. 알고리즘 원리 2-3. 예시 2-4. 시간복잡도 2-5. 추천문제 이분탐색과 투포인터 비교이분탐색과 투포인터1. 이분탐색1-1. 개요이분탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 사용되는 효율적인 탐색 알고리즘이다.배열의 중간 값을 기준으로 탐색 범위를 절반으로 줄여가며 값을 찾는다.1-2. 알고리즘 원리배열의 중간 값을 선택한다. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료한다. 중간 값이 찾고자 하는 값보다 크면 왼쪽 절반을 탐색한다. 중간 값이 찾고자 하는 값보다 작으면 오..

티스토리툴바