본문 바로가기
반응형

전체 글147

알고리즘 - 투 포인터(two pointer) 이미 정렬이 완료된 배열 or 리스트에서 두 개의 인덱스(포인터)를 이용해 포인터에 담긴 값과 원하는 결과를 비교해 원하는 해를 구하는 알고리즘. 이중 반복문으로도 해결가능한 문제이나 O(N^2) 의 시간이 소요. 정렬이 안된 배열에서도 O(NlogN), 정렬된 배열에선 O(N)의 시간으로 단축됨. ex) 배열 내 합이 S가 되는 순서쌍 찾기. 배열의 앞 뒤에서 포인터로 좁혀오며 순서쌍을 찾찾. 투 포인터(앞 : l 뒤 : r)가 지시하는 두 요소의 합을 S 와 비교 l 2020. 3. 4.
알고리즘 - Greedy(탐욕) 문제 해결 기준으로 조건탐색 시기 기준으로 최적의 요소를 선택해서 해결해가는 알고리즘. 즉, 매우 근시안적 선택을 이용해 문제를 해결하는 방식. 최적화 문제에 자주 사용됨. 주의할 점은 " 최적을 선택하는 조건 " 이다. 조건이 잘못되면 해를 구할 수 없는 경우가 생길 수 있기 때문. 거스름돈 문제와 최소비용 신장 트리에서 많이 사용됨. Greedy 알고리즘은 최선의 해를 구하는 것이 아닌 최적 or 적당히 납득할만한 해를 구하는 것이 목표. 2020. 3. 4.
알고리즘 - 완전 탐색 어떠한 문제에 대해 모든 경우의 수를 찾아 답을 찾아내는 알고리즘. 반복문이나 재귀 함수로 작성. 반복문을 사용한 구현이 더욱 직관적이며 알아보기 쉽다. 재귀함수를 이용할 때에는 꼭 탈출 조건을 명확하게 발생시킬 수 있어야하고 호출 깊이가 너무 깊어지지 않도록 해야한다. 호출 깊이를 제한해야하는 이유는 메모리 때문. 함수는 호출되면 스택에 데이터가 저장되며, 재귀함수로 인해 스택 오버플로우의 발생가능성이 높아지기 때문. 코딩테스트에서 메모리 초과 or 런타임 에러로 오답처리되면 메모리 문제를 체크해보자. 2020. 3. 4.
알고리즘 - 개요 이하 모든 글은 goorm edu의 비타 알고 2를 공부하며 정리하는 내용임. 알고리즘 : 문제를 해결하는 방식, 기법, 순서 시간 복잡도 : 알고리즘을 해결하는 동안 걸리는 시간을 나타내는 방법. 빅 오 표기법을 사용한다. O( n ) 구현 : 알고리즘을 실제 실행 가능한 코드로 나타내는 것. 순서도 : 알고리즘의 순서를 도형으로 나타낸 것. 의사코드 : 실제 코드로 작성하기 이전에 일반적인 언어를 이용해 간이로 작성한 코드. 2020. 3. 4.
c/c++ 클래스에서의 static, const static : 클래스, 구조체가 아닌 곳에서 사용할때는 변수를 정적 변수로 바꾼다. 변수는 기본적으로 자동주기에 의해 코드블럭 밖으로 나가거나, 함수가 종료되면 삭제된다. 그러나 static 접두사가 붙으면 정적 주기로 바뀌어 범위를 벗어나도 삭제 되지 않는다. 선언과 동시에 초기화가 권장되며 프로그램 종료시까지 유지된다. 범위는 지역변수와 같으며, 용도는 전역변수와 같다. const : 변수를 상수화 시키는 접두사. 일반 변수를 임의대로 변경할 수 없게 하여 고유의 값으로 사용하도록 한다. 클래스 멤버 변수 및 함수의 static 멤버 변수,함수에서 사용되는 static은 공유의 기능을 가진다. 객체 : 기본 static 변수와 같은 기능. 멤버 변수 : 해당 클래스로 생성된 객체에서 공유되는 변수... 2020. 1. 28.
Array 많은 프로그래밍 언어에서 기본적으로 지원하는 자료구조로 선형 자료구조의 대표격으로 리스트와 거의 비슷하다. 리스트와 차이점은 물리적 메모리의 주소값이다. 리스트는 포인터로 구성된 만큼 물리적 메모리가 선형적으로 딱 붙어있지 않는다. //리스트 그림. 메모리 주소 배열은 물리적 메모리가 딱 붙어서 저장된다. //배열 그림. 메모리 주소 배열에는 정적 배열, 동적 배열이 있다. 정적 배열 : 배열 선언시 크기가 정해지는 배열. c++ 에서는 선언후에 길이를 재조정 할 수 없다. 동적 배열 : 포인터를 기반으로 생성하는 배열로, 필요한 경우 재할당을 통한 길이 조정이 가능하다. 배열을 구성하는 단위를 '요소' 라고 하며 각 요소는 index라고 하는 고유의 번호를 가지게 된다. 실제로 저장되는 값은 아니다. .. 2020. 1. 28.
반응형

티스토리툴바