Study_farobi

• 공간 복잡도(space complexity) : 프로그램을 실행시켜 완료하는데 필요한 메모리의 양(RAM관련)
• 고정 부분
• 프로그램의 입출력 특성과 관계 X - 횟수, 크기 등에 상관 X
• 보통 명령어 공간, 단순 변수, 일정 크기의 요소 변수, 상수들을 위한 공간을 포함
• 가변 부분
• 풀려고 하는 문제의 인스턴스에 의해 크기가 결정되는 변수가 필요로 하는 공간과, 참조된 변수가 필요로 하는 공간, 순환 스택 공간으로 구성
• 공간복잡도 S = C(상수) + Sp(인스턴스 특성)
• Sp는 함수가 얼마나 콜되는가에 따라 달라지는 것 같음
• 변수가 여러개 있다고 해서 Sp가 올라가는 것은 아님
• 순환의 깊이에 따라 Sp가 올라갈 수도 내려갈 수도 있음

• 시간 복잡도(time complexity) : 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간(CPU관련)
• 프로그램에 소요되는 시간은 컴파일 시간 + 실행 시간 - SUM(명령어들의 수행시간 * 명령어들이 몇번이나 실행됐는지 센 결과)
• 컴파일 시간은 인스턴스 특성과는 무관하며 컴파일된 프로그램을 재컴파일 하지 않고 여러번 수행된다는 가정 하에 무시 가능 - 프로그램 실행 시간만 고려해도 OK
• 각 단계수(실행 횟수)를 고려하여 시간 복잡도를 계산
• 주석 : 단계수 0
• 선언문 : 변수/상수 정의문, class, struct, union, template, 접근자, 함수 타입 결정문 등은 단계수 0
• 비실행문이거나, 관련 함수가 기동되는 비용에 포함되므로
• 산술식 및 지정문
• 산술식 : +, -, *, / 등은 단계수 1, 다만 함수 호출을 포함하는 산술식은 예외
• 지정문 : = 등은 단계수 1, 다만 인스턴스 특성의 함수를 대입하는 경우 인스턴스 특성과 같은 단계수를 가짐
• 반복문 : 제어 부분만 단계수 고려, 반복문이 실행되는 횟수
• 스위치 명령문 : 수행되는 식의 단계수와 동일, 각 조건의 비용은 자신의 비용 + 앞서 나온 모든 조건의 비용
• if-else문 : 각 수행문에 따라 단계수 할당
• 함수 호출
• 매개변수가 인스턴스 특성에 의존하는 값이 아니라면 단계수 1, 의존하는 값이라면 값 인자의 크기가 단계수, 순환적이라면 지역변수도 고려
• 메모리 관리 명령문 : new, delete, sizeof 등 단계수 1
• new와 delete의 경우 생성자와 소멸자를 묵시적으로 호출할 수 있는데 이때는 함수 호출과 같은 방법으로 계산됨
• 함수 명령문 : 단계수 0
• 분기 명령문 : continue, break, goto, return 등 단계수 1, return 반환값; 일 경우 반환값이 인스턴스 특성의 함수라면 단계수는 반환값과 같음

밑의 예제를 통해 시간 복잡도를 조금 쉽게 이해하며 계산해보기

각 라인당 몇번 실행되는지 구한 후 다 더하면 OK

내가 변화시키고 싶은 특성들을 정해두고 그 특성에 맞춰 시간 복잡도를 계산하는 것이 좋음

• 균형 분기점(break even point) : 시간 복잡도가 큰 A와 작은 B가 있을 때 A가 B보다 빠를 수 있는 조건이 되는 n이 존재함. 그 때의 n이 균형 분기점
• 점근 표기법
• Ο(빅오) : 알고리즘 실행 시간의 상한을 나타냄 - 최악의 경우
• Ω(오메가) : 알고리즘 실행 시간의 하한을 나타냄 - 최고의 경우
• Θ(세타) : 알고리즘 실행 시간의 평균을 나타냄 - 평균의 경우

알고스팟은 다 좋은데 다른사람 코드를 보지 못하는게 아쉽다..

검색으로 찾아서 알아볼까

내 알고리즘이 너무 별로라서 다른 사람꺼 보면서 공부하고 싶다ㅠㅠ

아스키코드

int형에 char형을 넣으면 아스키코드중 10진수가 들어간다.

다른분들은 3ms/2ms 등등 더 시간이 짧았다.

난 6ms였는데 여기서 더 줄일 방법을 찾아봐야겠다..

if문의 조건이 까다로워서 그랬던건지/반복문이 너무 많아서 그런것인지 모르겠다.

함수 수행이 많아서 그럴지도?

strtol()이라는 함수를 처음 알았다.

문자열을 원하는 진수형으로 바꿀 수 있다.

내가 사용한 것은 16진수로 바꾸는 것

사용하기 위해서는 <stdlib.h> 헤더가 필요하다.

알고스팟에서 자주 string자료형을 사용해서 정리좀..

Header : string

namespace : std

#include <string>

s.size(), s.length() : 문자열의 길이를 반환

s.max_size() : 할당할 수 있는 가장 큰 문자열 사이즈 반환

s.resize() : 문자열의 크기를 재설정

(크기) : 크기만큼 사이즈 변경

(크기, 문자) : 크기가 커질 경우 빈 공간에 문자가 새로 추가됨

s.capacity() : 문자열에 실제 담을 수 있는 사이즈(할당된 메모리)를 반환

capacity가 size보다 클 때 속도가 더 빠름

capacity가 size보다 작으면 문자를 추가하기 위해 새로운 메모리를 할당해야 하기 때문

s.reserve(용량) : 문자열의 capacity를 변경할 수 있음

용량의 크기가 현재 capacity보다 크지 않으면 수행되지 않음

s.empty() : 문자열이 비어있는지 확인

size()==0 보다 일반적으로 빠름

s.assign() : 문자열을 할당

(문자열) : 문자열 할당 

(개수, 문자) : 문자를 개수만큼 할당

(문자열, 시작위치, 개수) : 매개변수인 문자열을 시작위치부터 개수만큼 호출한 문자열에 할당

s.append() : 문자열의 끝에 문자열 할당

(문자열) : 끝에 문자열 추가

(개수, 문자) : 문자를 개수만큼 끝에 추가

(문자열, 시작위치, 개수) : 매개변수인 문자열을 시작위치부터 개수만큼 호출한 문자열에 할당

s.swap(문자열) : 문자열과 매개변수인 문자열을 서로 바꿈

s.at(위치) : 문자열에서 특정 위치의 문자에 접근하거나 대입

s.c_str() : 문자열을 null로 끝나는 char*형으로 바꾸어 반환

리턴하는 값은 재할당이 일어나는 연산(append(), insert())을 수행한 뒤에 유효하지 않을 수 있음

s.data() : 문자열을 구성하는 문자 버퍼에 대한 포인터 반환

s.begin(), s.end() : 문자열의 처음과 끝을 가리키는 임의접근 반복자 반환

반복자가 가리키는 값은 각 문자들

//마저 추가

s.insert() : 

s.erase() : 

s.replace() : 

s.copy() : 

s.substr() : 

s.compare() : 

s.find() : 

s.rfind() : 

• 삼항 연산자 - ?:

• 3개의 피연산자 필요

• (조건식) ? (식1) : (식2)

• 조건식이 true면 식1, false면 식2을 결과로 얻음

• 대입 연산자 - =, op=

• 변수에 값 or 수식의 연산결과를 저장하는데 사용

• 왼쪽에는 반드시 변수가 위치해야 함

• 변수 앞에 final을 붙이면 상수가 됨

△ 대입 연산자의 종류

• 논리 연산자 - &&, ||

• && : AND결합, 양쪽 다 true여야 true

• || : OR결합, 양쪽 다 false여야 false

• boolean과 boolean을 결과로 하는 조건식 사용 가능

• &&가 ||보다 우선순위가 높음

• ||의 경우 좌측의 피연산자가 true이면 우측의 피연산자 검사 X

• &&의 경우 좌측의 피연산자가 false이면 우측의 피연산자 검사 X

• 같은 조건식이라도 피연산자의 위치에 따라 연산속도가 달라짐

• &, |는 위와 다르게 좌, 우 항상 둘 다 검사함

• 비트 연산자 - &, |, ^

• 이진 비트연산 수행

• & : AND, 피연산자 중 양 쪽이 1이면 1을 결과로 얻음, 나머지는 0

• 3 & 5 = 1

• | : OR, 피연산자 중 한 쪽이라도 1이면 1을 결과로 얻음, 나머지는 0

• 3 | 5 = 7

• ^ : XOR, 피연산자 중 한 쪽만 1이면 1을 결과로 얻음, 나머지는 0

• 3 ^ 5 = 6

• 실수형을 제외한 기본형 변수에 사용 가능

• 두 개의 리터럴, 변수를 비교할 때 사용, 연산결과는 true or false

• 비교하는 피연산자의 자료형이 다를 경우 범위가 큰 쪽으로 형변환하여 자료형을 일치시킨 후 비교

• 대소비교 연산자 - <, >, <=, >=

• boolean을 제외한 기본형 변수에 사용 가능, 참조형에는 사용 불가

• 등가비교 연산자 - ==, !=

• 저장되어 있는 값이 같은지 다른지 비교함

• 모든 자료형에 사용 가능(기본형, 참조형)

• 기본형 : 저장되어 있는 값이 같은지

• 참조형 : 가리키고 있는 주소가 같은지(같은 객체를 가리키는지)

• 참조형 변수에 사용할 수 있는 연산자는 ==, !=, (타입), +

• +는 문자열 결합 때만 허용, 문자열 비교는 == 대신 equal() 사용

• 기본형과 참조형은 형변환이 불가능하므로 기본형-참조형 함께 사용 불가능

• 실수형인 float와 double은 근사값으로 저장됨

• float f = 0.1f, double d = (double)f 일 때 d ≠ f

• f = 0.1, d = 0.10000000149011612 이므로 다름

• 이항 연산자의 한 종류

• 이항 연산자는 피연산자의 크기가 4byte이하면 4byte(int)로 변환 후에 연산 수행

• 이항 연산자는 피연산자들의 타입을 서로 일치시켜야 함

• 사칙 연산자 - +, -, *, /

• int보다 작은 자료형은 int로 형변환 후에 연산 수행

• 자료형이 다르면 표현범위가 더 큰 쪽에 맞춰 형변환 후에 연산 수행

• 정수형 간의 나눗셈에서 0으로 나누는 것은 금지

• 실수형은 부동소수점 값인 0.0f, 0.0d로 나누는 것이 가능하나 결과는 NaN(숫자 아님)으로 뜸

• 사칙 연산자의 연산결과를 대입할 경우 int보다 작은 자료형에 대입할 시 에러가 발생 - 형변환 해줘야 함

• 변수의 자료형에 따라 발생하는 오버플로때문에 원래의 결과값과는 다를 수 있음

• 연산결과를 넣는 변수의 자료형과는 별개로 피연산자들의 결과값이 오버플로될 경우 오버플로된 값이 변수에 들어감

• 변수의 자료형이 long일지라도 두 개의 피연산자가 int면 결과값은 int기 때문에 오버플로가 발생하여 이상한 값이 변수에 들어갈 수도 있음

• 하나의 피연산자가 long이라면 결과값도 long이 되므로 오버플로 X

• 오버플로 시 연산순서에 따라서도 값이 달라짐

• 상수 or 리터럴 간의 연산은 실행과정동안 변하는 값이 아니기 때문에 형변환이 없어도 실행 가능

• char c2 = ‘a’ + 1; //문제 없음

• char c2 = c1 + 1; //문제 있음

• 대문자와 소문자의 코드 차이는 32

• ‘a’ - ‘A’ = 32

• 숫자 0과 문자 0의 값은 차이가 있음

• Math.round() : 매개변수로 받은 값을 소수점 첫째 자리에서 반올림하여 정수로 돌려줌

• 나머지 연산자 - %

• 나누고 난 나머지 값을 돌려줌

• boolean을 제외한 기본형 변수에 사용 가능

• 정수형인 연산에는 오른쪽에 0을 사용할 수 없고, 0.0d, 0.0f로 나누는 것은 허용

• 결과값의 부호는 왼쪽에 있는 피연산자의 부호를 따름 - 부호를 무시한 나머지 연산 후, 결과에 부호를 붙임

• 쉬프트 연산자 - <<, >>, >>>

• 피연산자의 각 자리를 오른쪽 or 왼쪽으로 이동(2진수로 표현했을 때)

• 정수형 변수에만 사용 가능

• x << n : x * 2^n과 같음

• x >> n : x / 2^n과 같음

• n의 크기가 자료형의 bit보다 크면 n % bit 만큼만 이동시킴

• << : 자리를 왼쪽으로 이동시키며 빈칸을 0으로 채움

• >> : 자리를 오른쪽으로 이동시키는데 양수와 음수일 때 차이가 있음

• 양수 : 빈칸을 0으로 채움

• 음수 : 부호를 위해 빈칸을 1로 채움

• >>> : 자리를 오른쪽으로 이동시키며 양수, 음수 관계없이 빈칸을 0으로 채움

• 쉬프트 연산자가 사칙 연산자(*, /)보다 속도가 빠름

• Integer.toBinaryString() : 매개변수를 2진수로 표현한 문자열 반환, 맨 앞의 0부분을 생략함

• -8 >>> 1 = 1111111111111111111111111111100

• 증감 연산자 - ++, --

• 증가 연산자(++) : 피연산자의 값을 1 증가

• 감소 연산자(--) : 피연산자의 값을 1 감소

• 전위형 : 왼쪽에 사용, 변수의 값을 증가시킨 뒤 연산

• 후위형 : 오른쪽에 사용, 연산한 후에 변수의 값 증가

• boolean을 제외한 기본형 변수에 사용 가능

• 다른 수식에 포함되거나 함수의 매개변수로 사용된 경우(단독사용) 전위형과 후위형의 결과가 달라짐

• 증감 연산자가 사칙 연산자(+, -)보다 더 적은 명령으로 작업을 수행하므로 빠름

• 사칙 연산자(+, -)는 필요에 따라 피연산자를 형변환하지만 증감 연산자는 형변환없이 피연산자 값을 변경

• 부호 연산자 - +, -

• 피연산자의 부호를 변경

• boolean, char을 제외한 기본형 변수에 사용 가능

• 비트전환 연산자 - ~

• 피연산자를 2진수로 표현 시, 0은 1로, 1은 0으로 바꿈

• 정수형과 char에만 사용 가능

• 피연산자의 부호가 반대로 바뀜

• int보다 작은 자료형은 int로 변환 후에 전환

• ~의 연산결과를 담기 위해서는 int를 사용하거나 형변환해야 함

• 어떤 양의 정수에 대한 음의 정수를 얻기 위해서는 ~정수+1 하면 됨(2의 보수?)

• 논리부정 연산자 - !

• true를 false로, false를 true로 변경

• boolean에만 사용 가능