본문 바로가기

전체보기

 (126)
주소창에 URL을 입력하면 일어나는 일 자세하게 설명하는 것이 아닌 대략적인 흐름을 간단하게 정리해보았다. 웹 브라우저에 주소를 입력하게 되면, 먼저 'google.com'에 해당하는 DNS서버를 조회하여 IP정보를 얻어온다. 또한, 생략된 포트 번호를 파악하기 위해 https의 포트인 443을 찾아내 http 요청 메시지를 생성한다. 요청을 보내기 전, 먼저 소켓 라이브러리를 통해 IP와 포트정보를 사용해 3-way-handshake를 통해 연결을 확립한다. 요청 메시지가 전송 계층에 전달되어 TCP헤더가 붙게 되고 => 세그먼트 네트워크 계층에 전달되어 IP헤더가 붙게 된다 => IP 패킷 브라우저는 만들어진 패킷을 서버에 전달하게 되고, 서버는 받은 패킷의 헤더를 제거하고 해석을 하고 요청을 처리한다. 처리된 결과를 통해 HTTP 응답 ..
URI vs URL vs URN URI Uniform Resource Identifier, 통합 자원 식별자라는 뜻을 가지고 있다. 여기서 식별자는 다른 항목과 구분할 수 있는 정보로 사람으로 치면 주민번호와 같은 것이라고 할 수 있다. URL은 Locator(로케이터)와 Name(이름)으로 분류할 수 있는데 이것이 URL과 URN이다 따라서, URL과 URN은 URI의 부분집합이 된다. URL Uniform Resource Locator, 리소스가 있는 구체적인 위치이다. 일반적으로 우리가 인터넷에서 많이 보는 형태이다. https://www.naver.com www.google.com/search?q=naver 등 URL의 문법 scheme://[userinfo@]host[:port][/path][?query][#fragment] ..
[프로그래머스] 다트 게임 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 다트 게임 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 📝 풀이 과정 다트 게임의 결과가 일정한 패턴을 가진 String로 들어오게 된다. String을 하나씩 끊어가며 처리하는 방법도 있겠지만, 숫자의 경우 10이 들어오게 되면 처리가 불편해지기 때문에 Pattern과 Matcher class를 사용하기로 했다. (참고 : [Java] Pattern, Matcher Class로 정규식 활용하기) Pattern pattern = Pattern.compile("([0-9]+)([SDT])([*#]?)"); Matcher matcher = pattern.matcher(dartResult);..
[프로그래머스] 비밀지도 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 비밀지도 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 📝 풀이 과정 지도 두 장을 겹쳐 둘 중 하나라도 벽('1')일 경우 결과 값에 벽('1')이 나오는 것을 보고 OR연산이 떠올랐다. 1010 | 1100 = 1110 Integer.toBinaryString(arr1[i] | arr2[i]).replace('1', '#').replace('0', ' ') 입력은 정수 배열의 형태로 들어오기 때문에 하나씩..
[백준] 1786번: 찾기 - JAVA 🔗 문제 링크 BOJ 1786번: 찾기 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 📝 풀이 과정 주어진 문자열(T)에서 패턴 문자열(P)를 찾아 인덱스를 구하면 되는 간단한 문제이다. 하지만, 범위가 각각 $1,000,000 = 10^6$이므로 단순하게 문자열을 찾는 이중반복문으로 문제를 해결하려고 하면 $O(NM) = 10^{12}$으로 시간초과가 발생하게 된다. 따라서, 효율적으로 문자열을 찾는 알고리즘인 KMP 알고리즘을 사용해야 한다. 처음 문제를 풀 때, 기존 KMP에서 인덱스를 저장하는 ..
[문자열 검색] KMP 알고리즘 단순하게 문자열을 찾는 방법을 생각해 보면 한 칸씩 비교해가며 일치하는지 확인하는 방법이 있다. ABABABC에서 ABAB가 몇 번 들어가는지 확인하는 예시이다. ⇒ 일치 ⇒ 불일치 ⇒ 일치 ⇒ 불일치 위와 같은 방식으로 찾게 되면 전체 문자열(len = N)에서 찾고자 하는 문자열(len = M)을 하나씩 비교해야 하므로 $O(NM)$의 시간복잡도를 갖게되어 비효율적인 알고리즘이 된다. 하지만, KMP 알고리즘을 사용하게 되면 시간복잡도가 $O(N+M)$으로 획기적으로 줄어들게 된다. 먼저 KMP 알고리즘을 배우기 전에 접두사와 접미사의 개념에 대해 알아야 한다. 예를 들어, apple의 접두사(prefix)는 a ap app appl apple 접미사(subfix)는 e le ple pple appl..
[백준] 1238번: 파티 - JAVA 🔗 문제 링크 BOJ 1238번: 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1️⃣ 플로이드-와샬 📝 풀이 과정 학생(i)가 이동하는 경로는 i -> X -> i이다. 따라서 이동하는데 걸리는 시간은 (i -> X) + (X -> i)이므로 학생마다 걸리는 시간을 모두 구할 수 있는 플로이드-와샬 알고리즘이 생각났다. ⏱ 시간 복잡도 플로이드 와샬의 경우 시간복잡도가 $O(N^3)$인데, 학생의 수는 최대 1000이므로 세제곱을 하여도 $10^9$ 이므로 1초이내에 해..
[백준] 1149번: RGB거리 - JAVA 🔗 문제 링크 BOJ 1149번: RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📝 풀이 과정 만약, N번 집의 색이 빨간색이라면, N + 1의 집의 색깔은 초록색이나 파란색으로 칠하는 경우밖에 존재하지 않는다. 다시 말하면 N번 집의 색이 빨간색이라면 N - 1의 집의 색은 초록색이나 파란색이라는 의미가 된다. 따라서, i번째에서 가장 적은 비용으로 빨간색을 칠하는 경우는 $dp[i][0] = Min(dp[i-1][1], dp[i-1][2]) + cost[i][0]$가 되고..

티스토리툴바