BUILD_SSO

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) 풀이하며 엄청 헤맸던 문제 중 하나이다.. 단순..

🔵구현(시물레이션과 완전탐색(brute force)) #구현 - 머리속에있는 알고리즘을 소스코드로 바꾸는 과정 - 구현 유형의 문제란? => 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 뜻함 - 일반적으로 알고리즘 문제에서의 2차원 공간은 '행렬(matrix)'의 의미로 사용된다. => 행렬에서는 왼쪽상단이 (0, 0) 지점이다. - 시물레이션 및 완전탐색 문제에서는 2차원 공간에서의 '방향 벡터'가 자주 활용돤다. => 세로축; x(위 방향;- / 아래 방향; +), 가로축; y(좌; - / 우; +) => dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0] 🔵브루트포스(brute force) - 가능한 모든 조합을 다 탐색한다.(답이 나올때까지) -답을 무조건 찾을수는..

🔵탐욕법 #1 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 정당성 분석이 중요 => 문제에서 요구하는 최적의 해를 구할 수 있는지 검토하는 것이 중요하다. #2 - 내 상황에서 가장 큰값을 고르는 알고리즘이라고 볼 수 있다. #3 - 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. - 코딩테스트에서는 그리디알고리즘, 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 출제하는 경우가 많다. 거스름돈 n = int(input()) #1260원 일 때 count = 0 array = [500, 100, 50, 10] for i in array: #화폐의 종류만큼 for문이 반복된다. count += n // i #1. 500원으로 2번만큼 거슬러줄 수 있다. n %= i ..

문제링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제 입력: 4 6 101111 101010 101011 111011 예제 출력: 15 풀이 과거에 풀었던 문제를 DFS/BFS 복기할겸 다시 풀어보았다. 최단거리라고 생각해서 DFS문제라고 생각했는데 과거에도 똑같은 방식으로 실수했던 기록이 있었다...(도대체 왜?) 문제를 다시 파악하고 BFS로 풀이하였다. 좌측 상단(1, 1)에서 우측 하단(4, 6)으로 이동하는 최소의 칸 수를 구하는 문제이다. 이것을 pyth..