14940번 - 쉬운 최단거리

1. 문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 2. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. 3. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 4. 풀이 1) 입력이 2인 지점을 초기 위치로 설정 2) BFS를 통해 초기 위치로 부터 최단 거리 구하기..

• format_list_bulleted Problem Solving/C++
• · 2023. 7. 7.
• textsms

[운영체제] 운영체제의 시작과 발전

1. 운영체제 개념 1) 운영체제 정의 운영체제 : 컴퓨터 사용자와 컴퓨터 하드웨어 사이에서 중계 역할을 하면서, 프로그램 실행을 관리하고 제어하는 시스템 소프트웨어 컴퓨터가 켜질 때 처음으로 적재되어 나머지 모든 프로그램의 실행을 제어하고 사용자의 요청을 처리하는 소프트웨어 컴퓨터의 자원을 독점적으로 관리하는 특별한 소프트웨어 2) 운영체제의 목적과 기능 운영체제의 목적 컴퓨터 사용의 편리성 컴퓨터 자원관리의 효율성 운영체제의 기능 CPU/프로세스 관리 메모리 관리 파일 시스템 관리 장치 관리 네트워크 관리 보안 관리 기타 관리 (사용자 계정 관리, 통계, 오류 발견 및 대응, 부팅) 3) 운영체제와 응용소프트웨어 운영체제 응용소프트웨어 목적 컴퓨터 하드우어나 응용소프트웨어 등 자원 관리 컴퓨터 사용자..

• format_list_bulleted Computer Science/Operating System
• · 2023. 7. 7.
• textsms

Calling Convention (함수 호출 규약)

0. 들어가며 함수 호출 규약 : 함수의 호출 및 반환에 대한 약속 함수 호출 시 프로그램의 실행 흐름이 다른 함수로 이동 이 때, 기존 함수로 돌아오기위해 호출 방식에 대한 약속을 규정 1. 함수 호출 규약 함수를 호출할 때는 반환된 이후를 위한 호출자의 StackFrame 및 반환 주소 저장 피호출자가 요구하는 인자 전달 피호출자의 실행 종료 시 반환 값 전달 함수 호출 규약을 적용하는 것은 일반적으로 컴파일러 2. 함수 호출 규약의 종류 CPU 아키텍처와 컴파일러 종류에 따라 함수 호출 규약도 달라짐 x86(32비트) 아키텍처 레지스터를 통해 피호출자의 인자를 전달하기에는 레지스터의 수가 적어 스택을 이용하는 함수 호출 규약 사용 cdecl stdcall fastcall x86-64 레지스터가 많으..

• format_list_bulleted Security/Reversing
• · 2023. 7. 6.
• textsms

다이나믹 프로그래밍 (2) - P/NP,플로이드-워셜 알고리즘

1. P와 NP 입력 데이터 크기가 증가함에 따라 문제 해결의 복잡도가 어느 정도까지 향상되는지 파악 P 문제 : 다항 시간내에 해답을 구할 수 있음을 의미 시간 복잡도가 $O(n), O(n^2), O(log n)$ NP 문제 : 비결정적 다항 시간문제 주어진 문제의 솔루션을 검증하는 것은 쉬우나 실제 솔루션을 만드는 일은 매우 어려움 NP의 많은 문제들은 NP-완전으로 알려져 있음 특별한 특성을 공유 다항 시간처럼 효율적으로 해결하는 솔루션이 발견 → 다른 문제에도 적용 가능 2. 부분집합의 합 문제 다시보기 특정 부분집합에 대한 유효성 검증은 각 부분집합의 원소를 모두 더하여 목표치와 같은지를 검사하는 방식 검증에 대한 복잡도는 부분집합 크기에 대해 선형 관계 만족 부분집합의 합 문제를 O(n*m) ..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 7. 6.
• textsms

스택프레임

1. 스택프레임 ESP (스택 포인터)가 아닌 EBP (베이스 포인터) 레지스터를 사용하여 스택 내의 로컬 변수, 파라미터, 복귀 주소에 접근하는 기법 ESP의 레지스터의 값은 프로그램 안에서 수시로 변경 ESP값을 기준으로 하면 스택에 저장된 변수, 파라미터에 접근을 하기 어려움이 있음 ESP 값을 EBP에 저장하고 이를 함수 내에서 유지해 아무리 ESP 값이 바뀌어도 EBP를 기준으로 해당 함수의 변수, 파라미터, 복귀 주소에 접근 가능 2. 스택 프레임의 구조 PUSH EBP ; 함수 시작 (EBP 값을 저장) MOV EBP, ESP ; 현재 ESP 값을 EBP에 저장 (함수 본체) ; EBP의 값은 변하지않음 -> 로컬 변수와 파라미터 엑세스 가능 MOV ESP, EBP ; ESP 값 복구 POP..

• format_list_bulleted Security/Reversing
• · 2023. 7. 5.
• textsms

다이나믹 프로그래밍 (1) - 부분집합의 합 / 문자열 시퀀스

0. 들어가며 분할 정복 패러다임 개념을 확장 매우 복합적이며 창의력과 인내심, 추상적 개념을 시각화하는 능력을 요구하는 경우가 많음 다이나믹 프로그래밍이 자주 사용되는 몇 가지 예 조합 (특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기) 문자열과 시퀀스 (편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스) 그래프 (최단 경로 문제) 머신러닝 (음성/얼굴인식) 1. 동적 계획법(Dynamic programming)이란? 피보나치 수열을 통한 동적 계획법 설명 피보나치의 재귀조건 : $F(n) = F(n-1) + F(n-2)$ 피보나치의 기저조건 : $F(0) , F(1)$ 하향식 방법 : 재귀 트리의 맨 꼭대기서 시작하여 기저 조건에 닿을 때까지 이동 피보나치의 경우 여러 개의 부..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 7. 5.
• textsms