분류 전체보기49 [알고리즘] 누적합 알고리즘 (Prefix sum algorithm) 누적합 (Prifix sum)나열된 수의 누적된 합배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있도록 함 구간 합 구하기N개의 원소로 이루어진 배열에서 구간 합을 구하는 방법반복문을 통한 구간 합배열의 i번째 원소부터 j번째 원소까지 순회하며 값을 더함구간 [i, j]의 합 = arr[i] + arr[i+1] + ... + arr[j]시간복잡도: O(N)구간의 길이에 비례하여 시간이 증가하기 때문에 여러 번 구간 합을 구해야 할 때 비효율적 누적합 알고리즘 사용미리 배열의 누적합 배열을 계산누적합 배열 S에서 S[k]는 배열의 0번째 원소부터 k번째 원소까지의 합을 의미구간 [i, j]의 합 = S[j] - S[i - 1]시간복잡도: O(1)누적합 배열을 미리 계산하는 데 O(N)이후 각 구간 합.. 2024. 11. 5. [알고리즘] 이분탐색/이진탐색 Binary Search 이분 탐색오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘찾고자 하는 값과 중간값을 반복적으로 비교해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함변수 3개(high, low, mid) 사용 처음 리스트의 중간값을 임의의 값으로 선택 mid = (low + high) / 2그 값과 찾고자 하는 값의 크고 작음을 비교처음 선택한 중앙값이 만약 찾는 값보다 크면(mid > key) 그 값은 새로운 최댓값이 됨 (high = mid - 1) 작으면(mid ) 그 값은 새로운 최솟값이 됨 (low = mid + 1)같으면 (mid == key) 중간값 리턴 후 종료 장점검색이 반복될 때마다 탐색 범위가 반으로 줄어들어 목표값을 찾을 확률이 두 배가 되므로 속도가 빠름시간 복잡도: O(log N)비교.. 2024. 8. 13. [IP주소] 클래스풀 / 클래스리스, 서브넷마스크, 서브네팅 클래스풀 배경IPv4는 32비트로 이루어진 인터넷 주소네트워크 주소와 호스트 주소로 나뉨네트워크 주소호스트들을 모아놓은 네트워크네트워크 주소가 동일하다면 로컬 네트워크에 속하는 것호스트 주소호스트를 구분하기 위한 주소 네트워크 호스트는 컴퓨터 네트워크에 연결된 컴퓨터나 기타 장치를 의미 네트워크에 속하는 컴퓨터나 장치를 구분하기 위한 주소 Classful IP addressing네트워크 주소를 매기고 그에 따라 네트워크 크기를 다르게 구분하여 클래스를 할당하는 주소체계구분하는 첫기준자(1옥텟, 2옥텟, 3옥텟 등)을 서브넷마스크라고한다. 클래스 D와 E의 경우, 각각 멀티캐스트 및 예비 사용을 위해 따로 구분된 것우리가 일반적으로 네트워크를 구성하는데 고려해야할 것은 Class A-C 각각의 클래스는 첫.. 2024. 7. 8. [자바/오류] incompatible types: char cannot be converted to string 원인String 변수에 char 값을 넣으려고 하는 경우 발생 해결String.valueOf() 함수를 이용해 char을 String으로 형변환 한다. 프로그래머스에서 문제를 푸는데 실행해보니 저런 오류가 떴다.사실 백준에서 주로 StringBuilder를 쓰다보니 char값을 형변환 없이 바로 집어넣는 거에 익숙해져 있었음...왕초보 문제도 자주 풀어봐야겠다. 지식에 구멍난 부분이 너무 많네 2024. 7. 4. [IP주소] IP주소와 MAC주소, ARP와 RARP, IPv4와 IPv6 IP 주소 (Internet Protocol address)논리적 주소 (변하는 주소)컴퓨터 네트워크에서 장치들이 서로를 인식하고 통신을 하기 위해서 사용하는 특수한 번호IP 주소 밑에 있는 MAC 주소를 통해 통신 MAC 주소 (Media Access Control address)네트워크 인터페이스에 할당된 고유 식별자네트워크에서 장치를 식별하는 고유한 하드웨어 주소변경할 수 없도록 하드웨어(NIC)에 고정돼서 출하보통 장치의 NIC(LAN 카드)에 할당총 48비트로 구성8비트씩 6개로 구분하여 표기24비트의 OUI(Organizationally Unique Identifier) - 제조사 고유 코드24비트의 UAA(Universally Administered Address) - 기기 고유 코드보통의 .. 2024. 7. 3. [백준 9935/자바] 문자열 폭발 https://www.acmicpc.net/problem/9935 문자열의 최대길이가 100만이기 때문에 문자열 메소드 replaceAll을 사용하면 메모리초과가 발생한다고 한다... ✨ 참고https://loosie.tistory.com/317 풀이스택 사용 스택에 입력받은 문자열을 한 글자씩 집어넣음스택의 크기가 폭발 문자열의 길이와 같거나 길이보다 클 경우 폭발 문자열이 포함 돼있는지 확인스택의 최상단에서 폭발 문자열 길이까지만 get 함수를 이용해 앞에서부터 차례대로 확인한다만약 폭발 문자열이 포함 돼있으면 그 길이만큼 pop 수행 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader.. 2024. 7. 3. [백준 2606/자바] 바이러스 https://www.acmicpc.net/problem/2606 BFS에 익숙해져보려고 계속 하는데 익숙해지지가 않음더 공부해야 할 듯 ✨ 참고인접 리스트 - https://ko.wikipedia.org/wiki/%EC%9D%B8%EC%A0%91_%EB%A6%AC%EC%8A%A4%ED%8A%B8풀이BFS 및 인접 리스트 사용 📌 인접 리스트그래프 이론에서 그래프를 표현하기 위한 방법 중 하나그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법인접 행렬에 비하여 변이 희소한 그래프에 효율적이다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import.. 2024. 7. 3. [라우팅] 라우팅, 라우터, 라우팅 테이블 라우팅네트워크에서 데이터를 보낼 때 최적의 경로를 선택하는 과정요청과 응답이 빠르게 도달할 수 있도록 함라우터라는 네트워크 장치가 이를 수행 데이터는 출발지에서 목적지를 가는 동안 여러 개의 라우터를 거치며 여러 번의 라우팅을 수행함라우팅은 보통 초당 수백만번 일어남 라우터네트워크 사이에서 데이터를 전달하는 장치보통 둘 이상의 서로 다른 네트워크에 연결데이터를 목적지로 보낼때 최적의 경로를 결정하고, 경로가 결정되면 해당 경로로 데이터를 넘겨주는 일(라우팅)을 수행라우팅 테이블을 기반으로 데이터를 다음 목적지에 전달 라우팅 테이블IP 주소를 기반으로 라우터의 위치를 저장한 테이블 또는 데이터베이스다양한 네트워크에 대한 정보와 해당 네트워크에 연결하는 방법이 포함되어 있음 외부 네트워크(여러 개의 라우터.. 2024. 7. 3. [TCP] 연결 성립과 해제 3-way HandShake연결하고자 하는 두 장치(클라이언트, 서버) 간의 논리적 접속을 성립하기 위해 사용하는 연결 확인 방식TCP/IP 프로토콜을 이용해 통신하는 응용 프로그램이 정확한 전송을 보장하기 위해 데이터 전송 전에 상대 컴퓨터와 사전에 세션을 수립함TCP 연결을 초기화 할 때 사용 클라이언트가 서버에 연결 요청 (SYN)서버가 연결 허락 (SYN + ACK)클라이언트-서버 연결 설정(ACK) 4-way HandShake데이터 송수신이 완료되고 TCP 연결을 해제하는 과정세션을 종료하기 위해 수행되는 절차 클라이언트가 서버에 종료 요청(FIN)서버가 클라이언트에게 확인 메시지(ACK)를 보내고 자신의 통신이 끝날 때까지 기다림(CLOSE_WAIT)추가로 전송할 패킷이 남아있으면 이어서 전송.. 2024. 7. 1. 이전 1 2 3 4 ··· 6 다음
