구름 개발일기장

https://www.acmicpc.net/problem/1477 🐢 설명 처음에는 휴게소를 세울 때 기존 휴게소 사이에 (중간)에 세우면 되는게 아닌가 생각했다. 하지만 이부분은 거리가 300일 때 150으로 나눌순 있지만 100, 100, 100으로 나누는 방법은 제공하지 못한다.  새로운 접근 방법은 이분탐색이다. 휴게소간 사이 거리 S를 정하고 S일 때 휴게소를 몇개 세울 수 있나 확인한다. 이때 세운 휴게소의 수가 세워야 하는 휴게소 M개보다 크다면 -> 간격이 너무 좁으므로 간격을 늘려서 휴게소를 덜 짓는다. 세워야 하는 휴게소 M개보다 작거나 같다면 -> 간격을 더 줄일 수 있다는 의미이므로 간격을 줄여서 휴게소를 더 짓는다. 위와 같이 이분탐색을 통해 적절한 휴게소 사이 거리를 탐색하고,..

https://www.acmicpc.net/problem/13397 🐢 설명 처음에는 좀 막막하게 다가온 문제이다. N개의 수가 주어졌을 때 어느 구간으로 나눴을 때 구간 내 최대값의 차이가 최소인 수를 구하는 문제이다. 구간의 크기를 동적으로 바꿔줘야 하는 문제인가 했지만 이분탐색으로 풀 수 있는 문제였다. 그럼 뭘 이분탐색할지가 중요한데 바로 구간 내 값의 차이를 이분탐색하면 된다. 주어진 수는 1 ~ 10000의 수가 주어진다 하였으므로 해당 수를 이분탐색해서 mid값으로 분할을 할 수 있는지 본다. 즉 정리하면 1. 0 ~ 10001 범위에서 mid를 잡는다. 해당 mid는 구간 내 차이의 값을 의미한다. 2. 해당 mid값으로 구간을 나눠보고 전부 나눴을 때 구간의 개수를 반환받는다. 3 -1...

서블릿 서블릿은 클라이언트의 요청에 대해 멀티 쓰레드로 처리가 가능하도록 한 기술이다. 쓰레드가 서블릿을 할당받아서 수행하게 되고, 개발자는 쓰레드에 관해 신경쓰지 않아도 되게됐다. 문제는 HTML 생성이 어려웠다. 요청에 대해 동적으로 HTML 웹 뷰를 생성하는게 너무 힘들었다는 것. JSP HTML 화면을 쉽게 작성할 수 있고 + Java code도 작성할 수 있게 됐다. 결국 서블릿으로 변환되어 처리되지만 해당 부분은 개발자가 신경쓰지 않아도 되는 부분이다. 문제는 HTML 생성은 편리한데 비지니스 로직까지 담당하게 된다. 서블릿, JSP 조합 MVC 패턴 사용 모델, 뷰, 컨트롤러로 역할을 나누어 개발하게 된다. 화면을 담당하는 뷰에 너무 많은 부담을 주지 않도록 하기위해 나왔다. 이 패턴이 비슷..

자바 웹 서버에서 요청들이 오면 해당 요청들을 처리하는 것이 서블렛이다. 이 서블렛들은 싱글톤으로 관리된다 했는데 서블렛을 부르는 존재는 누구일까? 쓰레드 애플리케이션 코드를 하나하나 순차적으로 실행하는 것이 쓰레드이다. 프로그램의 수행단위가 쓰레드. 자바 메인 메서드를 처음 실행하면 main이라는 이름을 가진 쓰레드가 실행된다. 쓰레드가 없다면 자바 애플리케이션 실행 조차 불가능하다. 쓰레드는 한번에 하나의 코드라인만 수행한다. 이를 위해 각 쓰레드는 PC라는 프로그램 카운터를 갖는다. 동시 처리가 필요하면 쓰레드를 추가 생성한다. WAS에 클라이언트로부터 요청이 들어오고 -> 해당 요청에 쓰레드가 할당된다 -> 쓰레드에 요청에 맞는 서블렛을 불러와서 코드를 실행을 하게 된다. Q. 만약 쓰레드가 할당..

https://www.acmicpc.net/problem/17490 🐢 설명 원형의 호수를 둘러싼 건물들에 대해 최소 스패닝 트리를 만들어야 한다. 이때 중요한 점은 건물군(동일한 부모를 갖는 건물들)이 하나라면, 즉 건물 사이를 막는 공사가 없거나 하나라면, 아무리 다리를 만드는 비용이 비싸도 모든 다리를 만들 필요없이 모든건물들을 갈 수 있으므로 무조건 YES 이다. 위 예외 사항을 제외하면 일반적인 유니온 파인드로 문제를 풀 수 있다. 1. 각 건물들의 부모를 자신의 번호로 지정하고, 건물 사이의 공사 여부를 체크해준다. 2. 각 건물들을 돌면서 같은 건물군인지 확인하고 & 사이에 공사구간이 없다면 같은 건물군으로 묶어준다. 이때 마지막 건물은 첫번째 건물까지 확인하게 해준다. 3. 건물번호와 부모..

Caching 한정된 빠른 공간(Cache)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식 program system외에도 cache memory, buffer caching, web caching등 다양한 분야에서 사용하고 있다. 캐쉬 운영의 시간 제약 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에 적용하기가 어렵다. 마지노선 (log N) 빠르게 데이터를 가져오기 위해 사용하는 것인데, 메모리에 올리기위해 공간확보에 시간을 오래쓰게 되면 비효율적이다. Buffer caching & Web caching의 경우 → O(1) ~ O (log N) 정도까지 허용한다. 여기서 LRU, LFU 알고리즘이 사용된다. Paging S..

https://www.acmicpc.net/problem/12764 🐢 설명 싸지방 컴퓨터를 사용하는 순서가 주어졌을 때 최소 몇개의 컴퓨터가 있어야 대기없이 컴퓨터를 사용할 수 있는지 구하는 문제이다. 이때 사용가능한 컴퓨터 중에서 번호가 가장 빠른 컴퓨터 사용한다는 점이 중요하다. 1. 모든 컴퓨터의 이용시간을 시작 시간을 기준으로 user_우선순위큐에 넣는다. 2. 사용하는 컴퓨터를 담는 usingCom_우선순위큐에는 끝나는 시간을 기준으로 담는다. 2-1. 만약 usingCom이 없다면 컴퓨터 자리를 새로 만들어서 추가한다. 2-2. 만약 usingCom이 있다면 자신의 시작 시간과 컴퓨터의 사용가능한 시간대를 확인하고 가능한 컴퓨터의 자리는 좌석순서_우선순위큐에 담는다. 2-2-1. 좌석순서_우..

Demanding Page 실제로 필요할 때, page를 메모리에 올리는 기법으로 아래와 같은 장점이 있다 I/O 양의 감소 Memory 사용량 감소 빠른 응답 시간 더 많은 사용자 수용 Vaild / Invalid bit의 사용 invalid의 의미는? → 사용되지 않는 주소영역인 경우 (참고로 가상 메모리 대부분은 사용하지 않는 공간이다) → Page가 현재 물리적 메모리에 없는 경우 (Swap Area에 있는 경우일 것이다) 처음에는 모든 Page Entry가 invaild로 초기화 되어있다 address translation 시에 invaild bit가 set되어 있으면? → "Page Fault" 즉, 현재 메모리에 올라와 있지 않은 것이므로, swap area에서 메모리에 올려야하는 것이고, ..

Data Link Layer 유/무선의 Physical Layer를 통해 송/수신하는 데이터들에 대해서 reliable한 통신을 위한 link를 제공한다. 통신과정에서 필연적으로 error등의 잡음이 발생할 수 밖에 없는데 이를 제어해준다. Network Layer가 Router to Router 간 통신이였다면 Data Link Layer는 데이터가 hop by hop으로 전송되는 모든 단일 링크를 관리한다. 라우터 사이에도 여러 node가 존재할 수 있으며 각 링크를 책임지게 된다. 따라서 출발지에 도착지로 패킷을 보낼 때 IP주소는 그대로인 반면 MAC 주소는 계속해서 변하게 된다. Alice -> Bob으로 데이터를 송신할 때 Alice는 먼저 Bob의 IP주소를 DNS 프로토콜을 이용해서 알아낸..

https://www.acmicpc.net/problem/2174 🐢 설명 로봇들이 2차원 공간에 존재하고 주어진 명령에 따라 움직인다. 이때 주의할 점은 좌표평면의 원점이 좌측 하단이라서 일반적인 2차원 배열의 인덱스와 다르다는 점이다. 하지만 굳이 신경쓰지 않고 그대로 사용해도 문제는 없는데 다만 그렇게 하려면 움직이라는 명령에서 방향은 변경을 해줘야 한다. 동, 서 쪽은 위아래가 반대여도 그대로이니 상관이없고 북쪽은 남쪽으로 / 남쪽은 북쪽으로 변경해주면 좌표값은 그대로 사용해도 무방하다. 로봇이 로봇이 부딫힌 경우에는 해당 로봇의 번호도 알려줘야 하므로 맵에 각 로봇의 번호를 적어놨고 이동할 때 같이 수정하도록 했다. 로봇들은 배열에 담아 놓은 후 주어진 로봇 번호로 접근하여 로봇을 움직이게 했다..

https://www.acmicpc.net/problem/5427 🐢 설명 벽이 있는 방에서 불이나 탈출해야하는 문제이다. 이때 불은 빈공간으로만 퍼진다는 특징이 있고, 사람도 빈공간으로만 다닐 수 있다. 불이 났거나 날 공간으로는 이동할 수 없다는 조건이 있다. 방 모습이다. 이 경우 5회의 이동끝에 탈출한다. ###.### #*#.#*# #.....# #.....# #..@..# ####### 먼저 불이 난 좌표를 불 큐에 넣어주고 내가 존재하는 위치를 저장해 뒀다. 이후 탈출자 먼저 BFS탐색으로 이동을 하고 불에 대해 BFS 탐색 후 이동하도록 했다. 이때 큐에 담은 불이나 탈줄자의 개수만큼만 탐색을하고 번갈아 가면서 하도록 했으며 사람이 먼저 이동하고 불이 이동하도록 했다. 만약 사람이 이동한 ..

Host의 IP 주소의 할당 방식은 두가지가 존재한다. 고정 IP 주소 방식으로 직접 IP, 서브넷 마스크, 게이트웨이를 설정하는 방식이다. DHCP를 이용해서 동적으로 필요할 때 IP 주소를 할당받는 방식이다. 일반 사용자들은 대부분 2번을 사용하며 학교나 관공서에서 1번을 사용한다. 1번을 사용하면 IP추적을 통해 특정 컴퓨터를 특정할 수 있다. DHCP 프로토콜 사용의 장점 사용을 할 때만 할당받아서 사용하게 된다. 고정적으로 컴퓨터마다 일일히 IP를 구성해줄 필요가 없다. 호스트(노트북, 폰) 등의 이동성을 지원해준다. 이동한 위치에서 새로 IP를 발급해주면 된다. DHCP host가 네트워크 망에 접속할 DHCP 서버와의 통신을 통해서 사용 가능한 IP를 묻고 사용 가능한 IP 주소를 받아서 H..