BUILD_SSO

시간복잡도와 공간복잡도에 대해 설명해 주세요. 알고리즘의 성능 평가를 위한 척도라고 할 수 있다. 알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용하는데, 이때 시간복잡도와 공간복잡도가 사용된다. 복잡도가 낮을수록 좋은 알고리즘으로 평가한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리(공간) 사용량 분석 시간복잡도 표기법 빅오, 빅오메가, 빅세타를 설명해 주세요. Big-O(빅 오) 표기법 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다. Big-Ω(빅 오메가) 표기법 알고리즘 최상의 실행 시간을 표기한다. Big-θ(빅 세타) 표기법 알고리즘 평균 실행 시간을 표기한다..

전위 중위 후위 표기법(Prefix, Infix, Postfix) 에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해 주세요. 전위표기법(Prefix) 형태: +AB 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법이다. 중위표기법(Infix) 형태: A+B 연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법이다. 후위표기법(Postfix) 형태: AB+ 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법이다. 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장한다. 스택을 사용한 계산 방법 숫자를 만나면 전부 스택에 집어 넣는다. -> 연산자가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 집어 넣는다. 스..

스택과 큐 Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있다. 스택과 큐 사용사례를 설명해주세요. Stack 주로 FILO가 필요한 환경에서 사용된다. 자바의 Stack 메모리 영역: 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out)구조를 가진다. 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) Queue 주로 데이터가 입..

Array vs List 차이점 Array와 List 모두 선형자료구조이지만, Array는 메모리 상에 데이터가 연속적으로 저장되고, List는 메모리 상에 데이터가 비연속적으로 저장된다. Array는 선언할 때 크기와 데이터 타입을 지정해야 한다. 대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다. List는 array처럼크기를 정해주지 않아도 된다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요하다. 하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다. Array vs ArrayList vs LinkedList의 차이점과 특징 Array는 index로 빠르게 값을 찾는 것이 가능함 LinkedLis..

파일 시스템 컴퓨터에서 파일이나 자료를 쉽게 발견할 수 있도록, 유지 및 관리하는 방법이다. 저장매체에는 수많은 파일이 있기 때문에, 이런 파일들을 관리하는 방법을 말한다. 👉🏻File Descriptor 에 대해 설명해 주세요.(Linux) 파이프, FIFO, 소켓, 터미널, 디바이스, 일반파일 등 종류에 상관없이 모든 열려있는 파일을 참조할 때 쓴다. 유닉스 시스템에서 프로세스가 이 파일들을 접근할때 파일 디스크립터(File Descriptor)라는 개념을 이용한다. 👉🏻0 1 2 stdi / stdo / err 프로그램이 프로세스로 메모리에서 실행을 시작 할 떄, 기본적으로 할당되는 파일 디스크립터들이 있다. 바로 표준 입력, 표준 출력, 표준 에러이다. 이들에게 각각 0,1,2라는 정수가 할당되며..

페이징 교체 알고리즘 페이징 교체 알고리즘이란 페이지 부재가 발생했을 때, 새로운 페이지를 할당해야 하는데 이때 현재 할당된 페이지중 어떤 것을 교체할지 결정하는 방법이다. 👉🏻Page Fault를 줄이는 방법에 대해서 설명하세요. Page Fault 란? 프로그램을 실행하기 위해 요청한 page가 메모리에 있는지 없는지를 확인하기 위해 page table에 valid-invalid bit를 추가하여 확인한다. 만약 있다면 valid고 없다면 invalid로 세팅되는데, 없을 때를 page fault라고 부른다. (cache에서의 miss와 유사하다.) 이렇게 보면 page fault가 발생했을 때 생각보다 너무 많은 overhead가 발생된다. 메모리의 접근이 너무 많이 일어난다. page fault를..

Paging vs Segmentation 페이징과 세그멘테이션은 둘 다 가상메모리를 관리하는 기법이다. 프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 실제 메모리에 할당하는 메모리 관리 기법이다. 간단하게 말해 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 뜻한다. 👉🏻세그멘테이션과 페이징의 차이점은? 둘의 차이는 프로그램을 분할하는 방식이다. 페이징과 세그멘테이션 모두 프로그램을 실행하기 위해 디스크에 있는 내용을 분할하여 메모리에 적재하는 불연속 메모리 관리 기법이지만, 페이징의 경우 프로그램을 같은 크기의 페이지로 분할하는 데에 비해, 세그멘테이션은 논리적 의미를 기준으로 세그먼트를 분할한다. 👉🏻세그멘테이션과 페이징의 두 가지 장단점 페이징 장점 - 논리 메모리는 물리 메..

문제링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 예제 입력: 3 1 예제 출력: 1 2 3 🔵백트래킹 백트래킹 이론을 아무리 봐도 이해가 가지 않아 N과M 문제의 코드를 먼저보고 분석해보았다. 백트래킹이란 DFS에 기반을 두고 있는 전략으로, 불필요한 경우를 배제하며 원하는 답에 도달할 때까지 탐색하는 알고리즘이다. DFS를 기반으로 하고있기 때문에 스택(stack)을 이용해 퇴각하며 다음 탐색을 진행한다. 백트래킹 같은 경우 기본..

문제링크:https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 예제 입력: 4 0 1 2 3 4 0 5 6 7 1 0 2 3 4 5 0 예제 출력: 0 예제 입력: 6 0 1 2 3 4 5 1 0 2 3 4 5 1 2 0 3 4 5 1 2 3 0 4 5 1 2 3 4 0 5 1 2 3 4 5 0 예제 출력: 2 문제유형: 백트래킹, 조합 풀이 스타트팀과 링크팀의 능력치 차이의 최솟값을 구하는 문제이다. + 백트래킹은 아직 감이 안 잡혀서 처음에 백트래킹 유형이라는 것을 ..

문제링크:https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 예제 입력: 2 5 6 0 0 1 0 예제 출력: 30 30 문제유형: 백트래킹, 구현, DFS 풀이 사칙연산의 모든 경우를 탐색하여 최댓값과 최솟값을 구하는 문제이다. 문제에서 구하고자 하는 것은 주어진 사칙연산을 이용하여 만들 수 있는 모든 결괏값 중 최대와 최소이다.(output) 풀이하며 엄청 헤맸던 문제 중 하나이다.. 단순..