[CS] 컴퓨터 네트워크의 기본 개념
·
CS/네트워크
1️⃣인터넷과 프로토콜, 데이터 전송 방식(회선/패킷 교환)🚀인터넷인터넷은 전 세계적으로 연결된 네트워크의 집합으로, LAN 사이를 상호 연결하여 전 세계 규모로 확장한 네트워크이다.인터넷은 종종 '네트워크의 네트워크' 또는 '세계에서 가장 큰 WAN' 으로도 불린다.  🚀프로토콜네트워크에서 데이터를 원활하게 주고받기 위해 통신에 참여하는 주체들(송신자, 수신자)가 따라야 하는 규칙을 의미한다.즉, 데이터를 어떻게 포맷하고, 송수신하며, 오류를 감지하고 수정할지 등에 대한 약속이다. 🚀데이터 전송 방식네트워크에서 데이터를 전달하는 방식에는 회선 교환과 패킷 교환이 있다. 회선교환통신이 시작되면 송신자와 수신자 간의 전용 회선을 설정하여 데이터를 전송하는 방식ex) 전화 통신 (전화 연결이 유지되는 ..
[Algorithm] 백준_특정한 최단 경로_1504번 (JAVA) 투포인터 알고리즘
·
Algorithm
📝문제https://www.acmicpc.net/problem/2559티어: 실버3💡풀이문제 유형투포인터 알고리즘 걸린 시간20분 시간 복잡도  풀이 방법 도출연속적이고, 범위가 계속 오른쪽으로 이동하는 문제여서 투포인터를 바로 떠올릴 수 있었다.left = 0, right = K 로두고 right가 N이하일때 까지 반복하는 반복문을 작성한다.이때 결과값인 max는 int범위의 최소값으로 설정해야 한다. 입력 받는 정수의 범위가 -100 ~ 100이기 때문에!이후 left부터 right까지의 arr의 합을 구해 max와 비교해주면 답을 도출할 수 있다.import java.util.*;import java.io.*;class Main{ public static void main(String[] ..
[Algorithm] 백준_안전 영역_2648번 (JAVA)
·
Algorithm
📝문제https://www.acmicpc.net/problem/2468티어 : 실버1 💡풀이 문제 유형dfs 걸린 시간37분 시간 복잡도O(N^2)최악의 경우 -> O(100*100*100) => 1000000번의 연산 => 1초 안에 ok 풀이 방법 도출구역 나누기 => dfs로 풀이 가능h를 증가시키면서 가장 큰 값이 나오는 경우를 저장해 두는 방법을 사용했다.h=0으로 두고 while 반복문을 돌린다.이때 구역의 수를 count로 두고 count가 0이 되면 반복문을 빠져나온다.  => 모든 위치를 다 방문함현재 위치의 높이가 h보다 높거나 같고, 방문하지 않은 위치라면 dfs를 돌려 현재 위치부터 사면을 검사해 방문을 체크해 준다.정답 max와 count 중 더 큰 값을 max에 저장하고 답을..
[Algorithm] 프로그래머스_바탕화면 정리 (JAVA)
·
Algorithm
📝문제https://school.programmers.co.kr/learn/courses/30/lessons/161990 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다. 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화..
[Algorithm] LeetCode_605. Can Place Flowers (JAVA)
·
Algorithm
📝문제You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.💡풀이 문제 유형..
[Algorithm] 백준_케빈 베이컨의 6단계 법칙 _1389번 (JAVA) 플로이드 워셜
·
Algorithm
📝문제민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨..
[Algorithm] 백준_Z_1074번 (JAVA) 분할정복
·
Algorithm
📝문제https://www.acmicpc.net/problem/1074Z 1074번티어 : 골드 5💡풀이문제 유형분할정복 걸린 시간40분? 50분? 시간 복잡도O(N) 풀이 방법 도출r과 c가 현재 사이즈를 사등분 후 왼쪽 위인지, 오른쪽 위인지, 왼쪽 아래인지, 오른쪽 아래인지 판단하는 문제다.우선 size = 2^N으로 정의 가는하고, 이를 사등분하려면 newSize = size/2가 된다.그럼 이때 (0,0)을 기준으로 0 + newSize, 0 + newSize와 r,c를 비교 검사해 위치를 구한다.이후 왼쪽 위인 경우는 count를 그대로, 오른쪽 위인 경우 count에 newSize*newSize를 더해준다. 왼쪽 아래인 경우는 newSize*newSize*2,  오른쪽 아래는 newSiz..
[Algorithm] 백준_구간 합 구하기 5_11660번 (JAVA)
·
Algorithm
📝문제https://www.acmicpc.net/problem/11660구간 합 구하기 5 : 11660번티어 : 실버 1 💡풀이문제 유형다이나믹 프로그래밍 걸린 시간80분.. 시간 복잡도  풀이 방법 도출전에 비슷한 문제를 풀었어서 어렴풋한 기억을 가지고 풀었다.일단 arr 배열에 입력 받은 값들을 넣어주고dp 배열을 생성한다. dp[i][j] = (1,1) 부터 (i,j)까지의 합이때 dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; 의 규칙을 갖는다.dp배열을 완성하면 (x1,y1)에서 (x2,y2)까지의 합을 구할 준비가 되었따.구간 합 식은 다음과 같다. sum = dp[x2][y2] - (dp[x1 - 1][y2]..
[Algorithm] 백준_최소비용 구하기 2_11779번 (JAVA)
·
Algorithm
📝문제https://www.acmicpc.net/problem/11779최비용 구하기 2 : 11779번티어 : 골드3💡풀이문제 유형다익스트라 걸린 시간110분 시간 복잡도  풀이 방법 도출이제 가중치가 다른 경로 사이의 최소 비용 구하기 하면 바로 다익스트라가 떠오른다.이틀 전에 풀었던 최소비용 구하기 문제와 거의 흡사하나 출력 조건에 몇가지 추가 되었다 (https://girokeulhaja.tistory.com/135)우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해준다.지나간 경로 출력 하는 방법을 모르겠어서 지피티한테 물어봤다,,그리고 StringBuilder 의 reverse() 메서드를 사용하려고 했으나 1 10 100으로 들어온 경우001 01 1이 출력 되므로 Ar..
[Algorithm] 백준_거짓말_1043번 (JAVA) 유니온 파인드
·
Algorithm
📝문제https://www.acmicpc.net/problem/1043거짓말: 1043번티어: 골드 4💡풀이문제 유형유니온파인드 걸린 시간60분 시간 복잡도O(N+M) 풀이 방법 도출1. 이 문제의 키포인트: 진실을 알고있는 사람끼리 묶기2. hashset에 진실을 알고 있는 사람을 add한다.3. 같은 파티에 있는 사람들은 모두 같은 집합으로 묶는다. union4. 진실을 아는 사람의 최상위 부모를 새로운 set에 넣고5. 파티 별 사람들을 검색해 사람들의 최상위 부모가 set에 포함되어있는지 확인한다.import java.util.*;import java.io.*;class Main{ static int[] parent; public static void main(String[] arg..