⭐️ Computer Science

[PS] DP - LIS 11053 가장 긴 증가하는 부분수열

// LIS DP 공식 let n = Int(readLine()!)! let aList = readLine()!.split(separator: " ").map { Int($0)! } var dp = Array(repeating: 1, count: n) // 배열을 순회하면서 각각의 인덱스를 비교해서 어떤 기준값보다 큰 값이 있으면 기준값을 수정해주는 과정 for i in 1..

[PS] 백트래킹 - n과m(9) 15663 어려움 시간초과 이슈 악

15663 (9) 시간초과 이슈 8개 중 8개를 고를 수 있어서 8^8 시간복잡도인데 내가 푼 방식은 contains 부분에서 시간복잡도가 추가로 증가하게 된다. 그래서 시간초과 이슈가 생긴다.import Foundation let nm = readLine()!.split(separator: " ").map { Int(String($0))! } let n = nm[0] let m = nm[1] var array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by:

[PS] 백트래킹 20문제 풀기 - 0. 개념, 1. n과m(1) ~ (4)

앞으로 4/17~23 이번주는 백트레킹 문제만 조지기로 다짐했다. 이번주 20문제를 풀고 익혀보자. 이번주 헤치울 문제들 https://www.acmicpc.net/step/34 백트레킹 개념 정리 모든 경우의 수를 전부 고려하는 알고리즘으로 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘 모든 경우의 수를 전부 다 고려하는 브루트포스 (완전탐색)보다 더 시간을 절약할 수 있다. 완전탐색의 대표적인 방법 중 하나가 DFS로, 재귀를 이용해서 현재시점에서 방문할 곳을 탐색하고 방문한다. 반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색해서 가지치기라고 부른다. 백트레킹은 BFS나 DFS와 함께 구현한다. 그러나 해당 노드가 조건에 부합..

[PS] BOJ - 7576 토마토 골드5

처음에 파이썬으로 풀었던 문제라 swift로 바꾸는 것은 쉽지 않았는데 시간초과 문제가 발생했다. 파이썬은 큐 라이브러리를 제공해주는 점과 다르게 swift는 큐가 제공되지 않는데 그 과정에서 removeFirst를 쓰는 부분이 문제였다. 맨 앞 요소를 삭제하면 각 요소들이 하나씩 앞으로 이동하는데 그러면 시간복잡도가 O(n)으로 시간초과가 발생하게 된다. 그러면 어떻게 해야 하냐? 기존에 removeFirst를 통해서 가장 맨 앞 요소를 삭제하고 -> 인덱스가 하나씩 당겨졌을 것이다. 이 대신에 index를 통해서 큐의 원소에 접근하는 방법을 사용하면 된다. index는 0부터 시작이고, queue.count는 1부터 개수를 센다. 그래서 index가 더 커지는 while문을 벗어나는 방식으로 구현해주..

[PS] 3/2 - BOJ 2644 촌수계산 - DFS

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 나는 촌수계산하려면 각각 노드 간 깊이를 계산해줘야 되니까 DFS가 먼저 떠올랐는데 다른 사람들은 BFS로 풀었다고 한다. 왜 BFS라고 생각을 했을까? DFS랑 풀이법은 비슷한데 큐에 튜플을 통해서 (시작노드, cnt)를 넣어준 것이 BFS 특징 이렇게도 풀 수 있다는 걸 익혀야겠다. 우선, 하나씩 x = 7인 경우부터 노트에 다 그려보면서 이해를 했다. depth의 경우, ..

[네트워크] HTTP 헤더2 - 캐시와 조건부 요청2

https://huree-can-do-it.notion.site/HTTP-2-d77a89aabe224b58ac10f04153c7254b

[네트워크] 상태코드

https://huree-can-do-it.notion.site/d91d0ce1f3cd42d392f558bd4feb48bb 상태코드 상태코드 huree-can-do-it.notion.site

[네트워크] HTTP 메서드 활용

클라이언트에서 서버로 데이터 전송 데이터 전달 방식은 2가지 1. 쿼리 파라미터를 통한 데이터 전송 - GET - 정렬 필터(검색어) query=\(검색어) 2. 메시지 바디를 통한 데이터 전송 - POST, PUT, PATCH - 회원가입, 상품주문, 리소스 등록, 리소스 변경 1. 정적 데이터 조회 - 쿼리 파라미터 미사용 추가적인 데이터를 전달하는 게 없고, URI 경로만 넣으면 추가적 데이터가 필요 없어서 이미지 리소스를 클라한테 보여줌 - 이미지, 정적 텍스트 문서는 단순 조회라서 GET 사용 - 쿼리 파라미터 없이 리소스 경로로 단순하게 조회 가능 ⭐️ Path Parameter 바이브 api/v1/post/(postId) 2. 동적 데이터 조회 - 쿼리 파라미터 사용 검색어 같은 추가 데이터..

[운영체제] CPU 스케줄링, 프로세스 상태, CPU 스케줄링 기법

CPU 스케줄링 준비 상태의 프로세스들이 순서에 따라 CPU를 할당 받으면 실행 상태가 되는데 이때 CPU를 누구한테 먼저 줄 것인지 순서를 정하는 것을 CPU 스케줄링이라고 한다. 다양한 기준과 방식들이 있겠지? 여기서 조금 하나 먼저 짚고 들어갈 것은 다중 프로그래밍은 하나의 메모리에 올라가 있는 여러 프로세스에게 CPU가 할당되는 거니까, 어떤 하나의 프로세스가 완전히 끝나버리고 -> 그 다음 프로세스가 처리되는 게 아니라는 점이다. (FIFO기법상 그럴수도..?) 그렇다면, 여기서 CPU를 스케줄링의 단위는 바로 스레드인 것을 알 수 있다. 프로세스는 CPU 할당 단위이고, 프로세스보다 더 작은 단위인 스레드가 CPU 스케줄링 단위인 것이다. 결과적으로, 스레드가 CPU를 할당 받는데 중요한 단위..

[운영체제] 운영체제에 들어가기 앞서

운영체제의 역할은 사용자 인터페이스와 자원관리를 위한 것이다. 일괄처리는 다수개의 프로그램을 읽어 저장해 놓되, 한 번에 한 개씩의 프로그램을 실행시켜 주는 방식이다. 왜 다수개의 프로그램을 읽어서 저장해두고, 하나씩 처리하는 것이냐? 면접을 예시로 들면, 여러 명의 면접자를 대기시켜두고, 순서대로 면접 보는 것과 같은 맥락이다. 한 명 끝나고 또 오라고 하고 기다리는 것보다는 여러명을 대기시켜두는 게 소모되는 시간을 줄이고, 스무스하게 연결짓는 거다. 이게 운체에서는 job-to-job의 transition을 스무스하게 한다라고 한다. 그래서 요즘은 일괄처리를 하되, 다중 프로그래밍을 통해서 한 번에 하나씩이 아닌, 한 번에 여러개의 일을 동시에 처리하는 Batch로 발전했다. 운영체제는 다중 프로그래..

[운영체제] 질문1. 프로세스와 스레드

프로세스 및 스레드 관련 질문 프로세스와 스레드의 차이는 무엇인가요? 프로세스는 실행 중인 프로그램으로 작업의 흐름 단위를 말하고, 스레드는 프로세스 내에서 실행되는 흐름 단위를 말한다. 프로세스 내에 작업의 단위를 좀 더 작게 나눈 것이 스레드이다. 각각의 프로세스는 메모리에 올라가 서로 자원과 주소공간을 공유하지 않지만, 스레드는 프로세스 내의 stack을 제외한 메모리 영역을 다른 스레드와 공유한다. 스택을 스레드마다 독립적으로 할당하는 이유는 무엇인가요? (= 스레드가 스택만 공유하지 않는 이유는 무엇인가요?) 스택은 함수에 필요한 매개변수, 반환값, 함수 내에 선언되는 변수가 저장되는 공간이다. 즉, 함수와 관련된 메모리 공간이다. 우리가 흔히 함수는 동작을 실행하기 위해 호출하는데, 스택 영역..

[네트워크] URI와 웹 브라우저 요청 흐름, HTTP

URI와 웹 브라우저 요청 흐름, HTTP URI 웹 브라우저 요청 흐름 HTTP 클라이언트 서버 구조 Stateful, Stateless 비연결성 HTTP 메시지 URI (Uniform Resource Identifier) - Uniform : 리소스를 식별하는 통합된 방식 - Resource : 자원, URI로 식별할 수 있는 모든 것 (제한 없음) - 실시간 교통 정보 등 - Identifier : 다른 항목과 구분하는데 필요한 정보 - 주민번호 등 URI는 주민번호로 식별하듯이, 자원 자체를 식별하는 방법이고 로케이터, 이름 또는 둘 다 추가로 분류될 수 있다. - URL : Uniform Resource Locator - (위치) 리소스가 여기 있어요~ (김영한이 여기 살고 있어요~) - URN..

[운영체제] 3. 프로그램과 프로세스, 스레드, PCB, Context Switching

프로그램과 프로세스, 스레드 면접에서 중요하단다. 기초적인 것! 우리가 맥북으로 음악도 듣고, 블로그도 쓰고, 유튜브도 켜고, 개발도 하고 동시에 여러개의 작업을 할 수 있는 이유 예전에는 게임을 다운 받는 동안에 화면이 멈추고 다 다운 받고서야 움직일 수 있는 그런 환경이었음 운영체제는 프로세스에 적절한 메모리를 할당한다. 운영체제 = 관리자 CPU = 일꾼 메모리 = 공장부지 프로세스 = 일감 관리자는 해당 일을 공장부지 어느 곳에 하면 좋을지 할당하는 것임 그러면 장난감공장의 곰인형담당일꾼은 곰인형일을 하고, 세부적으로 곰인형의 눈을 붙이는 일 / 곰인형의 팔을 붙이는 일 .. 이렇게 하는 것임 - 프로세스는 컴퓨터에서 실행 중인 프로그램, 프로그램으로부터 인스턴스화된 것, 메모리에 올라가 있는 프..

[운영체제] 2. 메모리계층, 가상메모리, 스와핑, 페이지폴트, 스레싱

메모리 계층 레지스터, 캐시, 메모리, 저장장치 위로 갈수록 속도가 빠르지만, 단위 공간 당 가격이 비싸고 용량이 적다. 아래로 갈수록 속도가 느리고, 단위 공간 당 가격이 싸고 용량이 많다. 휘발성 : 전원이 나가면 데이터가 사라진다. 비휘발성 : 전원이 나가도 데이터가 사라지지 않는다. CPU는 바이트 단위로 접근 가능한 매체이어야 접근이 가능하다. Primary : CPU가 직접 접근해서 실행 가능한 매체(Executable) - 바이트 단위 하드디스크의 단위는 섹터 단위로 접근할 수 있어 CPU가 접근하지 못한다. Secondary : CPU가 직접 접근하지 못하는 매체 - 섹터 단위 레지스터 : 휘발성, 작은 메모리, 속도는 가장 빠름, 용량은 가장 적음 캐시메모리 : L1, L2, 캐시 / L..

[운영체제] 1. 운영체제와 컴퓨터, 인터럽트, 시스템콜과 modebit

운영체제의 4가지 역할 후리장난감공장이 있다. 관리자 이름은 운영체제고, 일꾼은 CPU, 보조일꾼은 DMA 컨트롤러다. 공장부지는 메모리라고 한다. 일꾼의 뇌는 제어장치이며, 일꾼은 계산할 때 산술논리연산장치로 한다. 1. CPU의 스케줄링과 프로세스 관리 cpu의 소유권을 어떤 프로세스에게 할당할 거고, 프로세스의 생성과 삭제, 자원 할당과 반환을 관리한다. ex. 넷플릭스 실행 버튼을 눌렀을 때, 넷플릭스가 실행되는 그 과정 속에서 cpu 소유권을 넷플릭스에게 넘겨주는 관리자가 운영체제 - 먼저 들어왔다고 먼저 할당해줄까? 아니겠지? 2. 메모리 관리 한정된 메모리를 어떤 프로세스에 얼만큼 할당하는가 / 효율적인 관리 메모리라고 할 때, 우리는 보통 주메모리 RAM을 말하는 것인데 이 한정된 메모리를..