분류 전체보기103 [알고리즘] DFS (깊이 우선 탐색) 1. Depth First Search (DFS, 깊이 우선 탐색)1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 한 루트로 최대한 깊이 탐색하는 방식 - 트리나 그래프에서 한 루트로 쭉 탐색하다가 끝에 도달하면 다시 이전으로 돌아와서 다른 루트로 가는 방식 - 미로 찾기에서 한 방향으로 쭉 가다가 막히면, 다시 이전 분기점으로 돌아와서 다른 방향으로 가보면서 모든 루트를 탐색하는 방식 2. 장점1) 저장 공간의 수요가 비교적 적다. - 현 경로상의 노드들만 기억하면 되므로2) 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다. 3. 단점1) 해가 없는 경로에 깊이 빠질 가능성이 있다. - 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못했다면, 다른 경로를.. 2024. 4. 3. [알고리즘] 배낭 문제 1. 배낭 문제 알고리즘 문제 모음집 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$,.. 2024. 4. 3. [백준 C++] 20303번: 할로윈의 양아치 1. 문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 자료 구조 그래프 이론 그래프 탐색 분리 집합 배낭 문제 3. 소스 코드 #include #include #include using namespace std; int N, M, K; int candy[30001]; int total_candy[30001]; int.. 2024. 4. 3. [백준 C++] 16724: 피리 부는 사나이 1. 문제 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 2. 알고리즘 분류 자료 구조 그래프 이론 그래프 탐색 깊이 우선 탐색 분리 집합 3. 소스코드 #include #include using namespace std; unordered_map dir; int N, M; char map[1003][1003]; // 해당 맵 포인트가 탐색이 되었는지 여부 확인 bool is_search(int y, int.. 2024. 3. 25. [백준 C++] 11049번: 행렬 곱셈 순서 1. 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스 코드 #include #include #define INF 987654321 using namespace std; pair matrix[501]; int dp[501][501]; int main() { // N : 행렬의 갯수 입력 int N, r, c, A, B, C; cin >> N; // 행렬 입력 for (int i .. 2023. 12. 9. [백준 C++] 9466번: 텀 프로젝트 1. 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 3. 소스 코드 #include #include using namespace std; int ans; int choice[100001]; bool visited[100001]; bool done[100001]; void dfs(int cur) { visited[cur] = true; int next = choice[cur]; if .. 2023. 12. 3. [백준 C++] 7579번: 앱 1. 문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 3. 소스 코드 #include #include using namespace std; int memory_table[101]; int cost_table[101]; int dp[101][10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // N : 앱의.. 2023. 12. 3. [운영체제] 메모리 계층 1. 메모리 계층 2. 레지스터(Register) CPU 안에 있는 작은 메모리 휘발성이 있으며 속도가 가장 빠름 기억용량이 적음 1) 레지스터 유형 데이터 레지스터(Data Register) : 산술 및 논리 연산에 사용되는 데이터를 보관 주소 레지스터(Address Register) : 메모리 주소를 저장하며, 이 주소에서 데이터를 가져오거나 이 주소로 데이터를 전송하는데 사용 프로그램 카운터(Progream counter) : 다음에 실행될 명령어의 메모리 주소를 보관 명령 레지스터(Instruction Register) : 현재 실행 중인 명령어를 저장 상태 레지스터(Status Register) : 플래그를 저장하며, 이전 연산의 결과에 따라 설정되거나 재설정 3. 캐시 메모리(Cache Mem.. 2023. 11. 9. [운영체제] 컴퓨터의 요소 1. 컴퓨터의 요소 2. CPU(Central Processing Unit) 산술 논리 연산 장치, 제어 장치, 레지스터로 구성되어 있는 컴퓨터 장치 인터럽트에 의해 단순히 메모리에 존재하는 명령어를 해석해서 실행 운영체제의 커널(관리자 역할) : 프로그램을 메모리에 올려 프로세스를 만드는 역할 CPU(일꾼) : 메모리에 있는 프로세스를 처리하는 역할 1) 산술 논리 연산 장치(ALU, Arithmetic Logic Unit) 덧셈, 뺼셈 같은 두 숫자의 산술 연산과 배타적 논리합, 논리곱 같은 논리 연산을 계산하는 디지털 회로 2) 제어장치(CU, Control Unit) 프로세스 조작을 지시하는 CPU의 한 부품 입출력장치 간 통신을 제어하고 명령어들을 읽고 해석하며 데이터 처리를 위한 순서를 결정 .. 2023. 10. 30. [운영체제] 시스템콜(System Call) 1. 시스템콜이란? 운영체제가 커널에 접근하기 위한 인터페이스 주로 하드웨어 접근, 시스템 리소스를 관리, 입출력 작업 수행, 프로세스간 통신 등을 목적으로 사용 1) 유저 모드 - 유저가 접근할 수 있는 영역을 제한해둔 모드 - 컴퓨터 자원에 함부로 침범하지 못하는 모드 2) 커널 모드 - 모든 컴퓨터 자원에 접근할 수 있는 모드 3) 커널 - 운영 체제의 핵심 부분 - 시스템 콜 인터페이스를 제공 - 보안, 메모리, 프로세스, 파일 시스템, I/O 디바이스, I/O 요청 관리 등 운영체제의 중추적인 역할 2. 동작 과정 유저 프로그램이 I/O 요청 트랩(Trap)이 발동 올바른 I/O 요청인지 확인 유저 모드가 시스템 콜을 통해 커널 모드로 변환 해당 I/O 요청 실행 3. 시스템콜의 목적 사용자 프.. 2023. 10. 28. 이전 1 2 3 4 5 6 7 ··· 11 다음
