Computer Science/language9 [algorithm] 시간 복잡도와 빅오 표기법(big-O notation) 알고리즘을 공부하다 보면 필수적으로 듣는 용어가 시간복잡도와 빅오 표기법이다.빅오 표기법이란?먼저 쉽게 말하면 알고리즘 최악의 실행 시간을 표기해 아무리 최악의 상황에도 이 정도 실행 시간은 보장한다는 뜻이다. 컴퓨터과학(Computer Science)에서 알고리즘이란 특정 문제를 해결하기 위한 방법으로 알고리즘의 시간 복잡도를 나타내는 수학적 표기법 중 하나이다. 이는 주어진 알고리즘이 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타낸다. 일반적으로 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 나타내고, 이를 O(..) 형태로 표기하며, 괄호 안에 알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 나타내는 함수를 뜻한다. 본래 알고리즘의 효율성을 측정하는 가장 간단한 방법은 “직.. 2025. 7. 7. [algorithm | 백준/C] 2805: 나무 자르기 문제 문제 정의 문제를 찬찬히 읽어보면.. 나무가 필요한 상근이는 절단기의 높이를 적절히 정해서 나무를 자르고 잘린 부분을 가져간다.이런 느낌이라고 이해하면 될 거 같다. 직접 그렸다. 이때 상근이가 필요한 만큼(M)만 가져갈 수 있는 절단기의 최대 높이(H)를 구하는 문제이다.예를 들어 각각 25, 15, 10, 17미터인 4개의 나무가 있고 상근이는 7미터의 나무가 필요하다. 이때 가장 낭비가 없는 절단기의 높이는 15가 된다.25 - 15 = 515 - 15 = 010 - 15 = x17 - 15 = 2여기서 절단기의 높이가 더 작다면 상근이에게 필요한 나무가 부족하고 절단기의 높이가 더 높다면 낭비되는 나무가 생겨 환경을 생각하는 상근이가 싫어할 것이다. 문제 접근 절단기 높이 H 를 적절히 정.. 2025. 7. 6. [assembly | dreamhack] - Quiz: x86 Assembly 2 writeup Q1. end로 점프하면 프로그램이 종료된다고 가정하자. 프로그램이 종료됐을 때, 0x400000부터 0x400019까지의 데이터를 대응되는 아스키 문자로 변환하면 어느 문자열이 나오는가? end로 점프하며 프로그램이 종료된 시점에 데이터가 어떻게 바뀌었을 지를 알아내야 하는 문제이다. 레지스터 설명rcx: 반복 횟수를 제어하는 카운터 역할이다. 초기값은 0이다.rsi: 데이터의 시작 주소를 담고 있다. (예시에선 0x400000)dl: rdx의 하위 8비트이다. 1바이트 데이터를 임시 저장하기 위해 사용된다.코드 설명 5~6행[code]의 6행을 확인하면 jg end라는 코드를 볼 수 있다.jg 명령어는 jump if greater라는 뜻으로 직전에 비교한 두 피연산자 중 전자가 더 크면 주어진 주소로.. 2025. 5. 25. [assembly] Assembly 함수, 시스템 콜 정리 함수어셈블리어에서 프로그램이 처리해야 할 명령어들을 한 덩어리로 모아 놓은 코드블록C나 파이썬 같은 고급 언어에서 함수 정의하는 것처럼, 어셈블리어에서도 라벨(Label)로 특정 구역을 표시하고 명령어를 활용해 함수 사용함수는 서브루틴, 프로시저 , 함수라는 용어로 혼용함수를 호출한 함수는 call 명령어로 함수를 불러 사용, 호출된 함수는 ret 명령어를 이용해 다시 이전 함수에서 실행중이던 코드로 돌아감.스택자료구조의 한 종류, LIFO방식으로 동작하는 구조x86 아키텍처의 스택은 높은 메모리 주소에서 낮은 메모리 주소로 자라나는 특징.→ 데이터를 추가할 때마다 메모리 주소가 감소하며, 데이터를 제거하면 다시 증가하는 특성rsp: 스택 포인터 레지스터→ 항상 스택의 가장 위(Top)을 가리키며, pu.. 2025. 5. 25. [language] 객체지향 언어와 클래스의 개념 객체object란? 작용의 대상이 되는 쪽, 즉 현실 세계에서 구체적이거나 추상적인 사물을 의미한다. 예를 들어 구체적인 것으론 인간, 자동차, 등이 있고 추상적인 것으로는 축구, 직장 등이 있다. 이 모든 것을 아울러 객체라고 부른다. 소프트웨어 객체도 현실 속 객체와 비슷한 의미를 지닌다. 소프트웨어 객체는 상태를 필드(field)로, 동작을 메서드(method)로 정의한다. 소프트웨어 객체는 현실 세계의 객체를 필드와 메서드로 모델링한 것이다. 절차지향(procedural programming)과 객체지향(Object-Oriented Programming) 절차지향 프로그래밍procedural programming과 객체지향 프로그래밍object-oriented programming의 개념 및 특징.. 2025. 5. 24. [assembly] Assembly 분기문, 반복문 분기문프로그램의 실행 흐름을 바꾸는 명령어분기 명령어 사용시 명령어 포인터(Instruction Pointer)가 변경 됨.분기문의 종류(ja, jae, jp, jpe, jb, jbe)는 매우 많지만 이름으로 직관적 유추 가능모든 분기문은 다음과 같은 문법으로 동작jmp/je/jz, …. label jmp특정 주소로 rip를 바꾸는 명령어. 아무 조건 필요x 무조건 지정된 주소로 점프하는 명령어jmp foo ; foo로 이동foo: je (Jump if Equal) / jz (Jump if Zero)직전에 비교한 두 피연산자가 같으면 점프 (Jump if equal)ZF가 1이면 점프하는 명령어.두 피연산자의 값이 같을 때 특정 동작을 수행하고 싶을 때 해당 명령어를 사용해 지정된 주소로 점프ex. C언.. 2025. 5. 24. 이전 1 2 다음
