CS지식
-
JAVA 자료구조 (배열) 2 - 빗물 트래핑CS지식/자료구조 2023. 12. 21. 11:50
빗물 트래핑 풀이 1- 투 포인터를 최대로 이동 이 문제는 높이와 너비 모든 공간을 차례대로 살펴 보면 O(n²)에 풀이가 가능하다. 그러나 시간 복잡도가 너무 높기 때문에 좀 더 효율적인 풀이를 찾아야 한다. 투 포인터나 스택으로 O(n) 풀이가 가능할 것 같다. 그림 7-5에서 가장 높이가 높은 막대를 한번 살펴보자 위 그림에서는 최대 높이는 3인 곳이 가장 높은 막대이지만 최대 높이가 100이어도 관계는 없다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다. volume += leftMax - height[left]; ... volume += rightMax - height[rigth] 전체 중에 최대 높이 3을 기점으로 왼쪽 막대 ..
-
JAVA 자료구조 (배열) 1 - 덧셈 하여 타깃을 만들 수 있는 배열의 두 숫자CS지식/자료구조 2023. 12. 20. 15:55
풀이1 - 블루트 포스로 계산 위 문제에 대한 풀이를 한번 생각해 보자. 배열을 두 번 반복하면서 모든 조합을 더해서 일일이 확이해보는 무차별 대입 방식인 브루트 포스(Brute-Force)로 그림 7-3과 같은 방식을 떠올릴 수 있다. 이 그림에서는 정답을 찾기 위해 2부터 시작해 다른 엘리먼트들인 6,11,15를 차례대로 모두 비교한다. 즉 2 + 6, 2+ 11, 2+ 15와 같은 식으로 마지막 엘리먼트까지 모두 차례대로 더한 값을 비교해가며 정답을 찾을 때 까지 계속 진행한다. 이 방식이 바로 무차별 대입 방식인 브루트 포스로, 앞으로 문제를 풀 때 비효율적인 풀이법에서 꼭 한 번씩 첫 번째 풀이로 등장할 것이다. public int [] solution(int [] nums ,int target..
-
Java 자료 구조 - 배열CS지식/자료구조 2023. 12. 20. 12:49
배열 자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나누니다. 배열은 이 중 연속 방식의 가장 기본이 되는 자료형이다. 배열의 값은 집합으로 구성되며, 하나 이상의 인덱스 또는 키로 식별한다. 추상 자료형(Abstrac Data Type, 이하 ADT)의 실제 구현은 대 부분 배열 또는 연결 리스트를 기반으로 한다. 스택은 연결리스트로 구현하고 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 충분히 가능하다. C언어를 기준으로(C는 자료구조의 가장 기본적인 형태를 소개하기에 가장 적합한 언어이다.)배열 설명을 보면, 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, ..
-
시간의 복잡도 - 빅오 (Big-O)2CS지식/자료구조 2023. 12. 19. 12:23
빅오 (Big-O) 빅오를 계산하는 실용적인 방법 한눈에 빅오를 계산할 수 있으면 가장 좋지만 사실 웬만큼 알고리즘에 익숙하더라도 헷갈릴 때가 많다. 팩토리얼(n!) 계산 같은 게 그런 예다. 다음은 팩토리얼을 재귀로 구현한 코드이다. public int factorial(int n){ if( n>= 1){ return n * factorial(n-1); }else{ return 1; } } 얼핏 봐서는 팩토리얼 계산이고 재귀도 있고 하니 시간 복잡도는 O(n!) 쯤 될거 같다. 하지만 자세히 살펴보면 재귀는 n, n-1, n - 2, ... 순으로 한 번씩만 구하면 되기 때문에 시간의 복잡도는 O(n)에 불과하다. 자칫 헷갈리기 쉬운 부분이다. 그렇다면 어떻게 하면 정확하게 계산할 수 있을까? 다음과 ..
-
시간의 복잡도-빅오(Big-O)1CS지식/자료구조 2023. 12. 19. 09:47
빅오 (Big-O)1 알고리즘은 궁극적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있기 때문이다. 파일 크기에 따른 소요시간 간단한 예를 들어보자. 디스크에 저장된 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자 여기서 교통비 드 물리적인 비용은 전혀 고려하지 않고 단순히 시간만 따진다고 해보자. 이때 파일 크기가 작다면, 즉 n이 작다면 O(n)의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다. ..
-
운영체제 - OS, Operating SystemCS지식/운영체제 2023. 11. 2. 20:02
운영체제란 하드웨어 위에 설치되어 하드웨어 계층과 다른 소프트웨어 계층을 연결하는 소프트웨어 계층이다. 컴퓨터 시스템의 자원을 관리하고, 사용자가 컴퓨터를 사용할 수 있는 환경을 제공하는 역할을 수행한다. CPU, 메모리 같은 컴퓨터 자원은 제한적이라서 이러한 자원을 관리하는 일은 매우 중요하다. 또한 사용자와 컴퓨터 간 인터페이스를 제공해 사용자가 컴퓨터를 편리하게 사용할 수 있는 환경을 제공한다. 운영체제 목적 OS는 앞서 말한 것과 같이 한정된 컴퓨터 자원을 관리하는 시스템이다. 이러한 역할에 기반해 OS는 4가지 목적있다. 처리 능력(throughput) 향상 : OS는 자원 관리를 총해 일정 시간 내에 시스템이 처리하는 일의 양을 향상시킨다. 반환 시간(turnaround time)단축 : OS..
-
서버 기술 기초 요약 - 리눅스 쉘 사용법 6CS지식/운영체제 2022. 5. 1. 16:50
초간단 VIM 사용법 VIM 에디터 이해 및 설치 VIM : Vi improved에서 앞 글자를 빼내어 만든 이름이다. Vi : 전통적인 유닉스 에디터(개발자: 빌 조이) Visual Editor의 줄임말이다. Vim은 Vi에 자동화, 시각화 메뉴등을 추가한 프로그램이다. Vim이외에 이맥스(Emacs,GNU프로젝트 설립자 리차드 스톨마이 개발)라는 유명한 에디터가 있다. 일단 어떤 설정을 바꾸려면, 터미널 환경이기 때문에, 마우스로 클릭해서, 바꿀 수 없다. 보통의 설정은 file로 되어있다. 그 설정file을 수정해서 설정을 변경 할 수 있는 것이다. 그래서 무언가 수정을 하려면, editor가 필요하다. 근데, 리눅스에서 사용하는 editor은 생각보다 사용법이 불편하다. 윈도우,맥os Vim 설치..
-
서버 기술 기초 요약 - 리눅스 쉘 사용법 5CS지식/운영체제 2022. 5. 1. 15:55
우분투 패키지 관리 도커에서 image를 만들때 리눅스 image를 만들 것이고, 여기에 여러가지 프로그램을 설치해야한다. 그래서 우분투로 해당 프로그램을 설치하는 방법에 대해 알고 있어야 하기 때문이다. 원래는 리눅스 운영체제는 리눅스 커널이라는 핵심 운영체제 프로그램과 함께 사용자에게 명령을 받을 수 있는 bash 쉘외에도 여러가지 프로그램들 파일들이 하나로 묶여진 set이다. 이런 set의 합을 어떻게 만드느냐에 따라 여러가지 배포판이 생겨나는 것이다. ubuntu 배포판 다양한 배포판 중 하나 데비안 배포판을 기반으로 캐노티컬사가 우분투 배포판 개발 데비안 배포판은 apt 프로그램을 이용해서 소프트웨어 설치 및 업데이트를 간편하게 한 패키지 우분투 의미 : 남아프리카 부족 언어로 '너가 있으니 나..