tony9402

Search algorithm을 보기 전에 시간 복잡도에 대한 계산을 어떻게 하는지 알아야 한다. 시간 복잡도를 계산할 때, Worst case, Best case 인 경우를 구하면 된다.Worse case는 말 그대로 최악의 상황일 때 시간 복잡도를 계산하면 되고Best case는 상황이 가장 좋을 때 시간 복잡도를 계산하면 된다. Search algorithm 검색(찾기) 알고리즘(한국말로 하니깐 뭔가 어색하다) Searching 하는 알고리즘에는 기본적으로 Binary Search, Sequential Search가 있다. 1. Sequential Search(순차 검색) 아래는 Sequential Search에 대한 Pseudo-code 이다. 12345678void Seqsearch(int n,..

※ 학교 공부 복습 겸 올리는 것들이라 틀린 부분도 있을 수도 있습니다.(틀린 부분 있으면 댓글로 남겨주시면 감사하겠습니다.) 또한 간략하게 정리하는거라 내용이 부족할 수 있어 이 글을 보시는게 도움이 될 수도 안될 수도 있습니다. 알고리즘은 위에 영어로 되어있듯이 컴퓨터를 이용해서 문제를 풀기 위한 테크닉(Technique)이다. 테크닉은 Pseudo-code로 문제 풀이 과정을 프로그래밍 언어가 아니지만 프로그래밍 하는 듯이 표현하는걸로 생각하면 된다. 알고리즘을 다른 말로 설명하면 문제 풀이를 위한 절차라고 말할 수 있다. 실제로 알고리즘은 설계단계에서 사용한다. 우리학교 컴퓨터학부에선 machine이라고 말하면 machine은 CPU라고 생각하면 된다고 한다.알고리즘에서 복잡도가 곧 성능과 관련이..

백준 11657 타임머신 SPFA 공부중.... 벨만 포드랑 비슷하면서 살짝 다른 알고리즘저번에 디피로 풀면 쉽게 풀리는 문제를 그냥 대충 BFS로 풀었는데 어떤 갓분이 그거 SPFA라고 하셔서 이번에 한번 공부해봄 그땐 음수가 없었기 때문에 사이클을 체크 하는 부분이 없어도 되지만 이 문젠 음수가 존재하여 음수 사이클 존재여부를 체크 해야함 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include#include#include#include using namespace std; qu..

백준 1504 특정한 최단 경로 우선순위 큐를 이용한 다익스트라 공부중.....(소스가 좀 드러울 수도 있음)(지금은 소스만 올리고 나중에 정리해서 수정할 예정) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include#include#include#include using namespace std; const long long INF = 98765432; vector map;priority_queue pq;vector ans;int v, e; long long Daijk(int start, int e..

백준 1753 최단경로 처음에 짤땐 모든 간선을 넣을려 하지 않고 중복된 간선이 있을 수 있어서 최소비용 간선으로 갱신을 하는 소스를 짰더니 0.7~0.9초까지 나왔다. 이 갱신하는 부분을 지우고 제출해보니깐 시간이 0.2초까지 줄어들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include#include using namespace std; const int INF = 0x3f3f3f3f; vector map;vector visit;vector ans;priority_queue pq; ..

백준 1916 최소비용 구하기 소스 코드 메모(해설은 아직) - 우선순위 큐를 이용한 다익스트라 공부중 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include#include#include#include#include const int INF = 0x3f3f3f3f; using namespace std; vector map;vector visit;priority_queue pq;vector money; int main(){ ios::sync_with_stdio(false); cin.tie(0)..

성능 분석과 측정 프로그램의 평가 기준 - 우리가 원하는 작업을 하는가? - 원래 작업의 명세에 부합해서 정확히 작동하는가? - 문서화가 되어 있는가? - 논리적 작업 단위를 수행하는 기준으로 함수가 생성되었는가? - 코드가 읽기 쉬운가? 성능 평가(performance evaluation) - 성능 분석(performance analysis) => 사전 예측 - 성능 측정(performance measurement) => 이후 검사 공간 복잡도 공간복잡도 - 프로그램을 실행 시켜 완료하는 데 필요한 메모리 양 - 고정 부분 => 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 - 가변 부분 => 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간 - 프로그램 P의 공간 유고 ..

시스템 생명 주기(System Life Cycle) 요구사항 - 프로젝트들의 목적을 정의한 명세들의 집합 - 입력과 출력에 관한 정보를 기술 분석 - 문제들을 다룰 수 있는 작은 단위들로 나눔 설계 - 추상 데이터 타입(abstract data type) 생성 - 알고리즘 명세와 설계 기법 고려 정제와 코딩 - 데이터 객체에 대한 표현 선택 - 수행되는 연산에 대한 알고리즘 작성 검증 - 정확성 증명 : 수학적 기법들을 이용해서 증명 - 테스트 : 프로그램의 정확한 수행 검증, 프로그램의 성능 검사 오류 제거 - 독립적 단위로 테스트 후 전체 시스템으로 통합 객체 지향 설계 구조적 프로그래밍 설계와의 비교 - 유사점 : 분할 - 정복 기법 : 복잡한 문제를 여러개의 단순한 부분 작업으로 나누어 각각을 개..

백준 7569 토마토(3차원) 이 문제는 토마토(2차원)이랑 높이가 생겼다는 것 빼곤 똑같다. 2차원에서 위, 아래(높이 방향)이 추가 되었으므로 체크해야하는 위치가 2가지가 늘었다. 하지만 푸는 방식은 토마토(2차원)이랑 같다. (토마토(2차원) 풀이 보러가기) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include#include using namespace std; queue q;int map[101][101][101] = { 0 };bool visit[101][101][101] = ..

백준 7576 토마토 이 문제는 익은 토마토가 주변 익지 않은 토마토를 익게 만든다. 박스 안에 토마토의 정보를 받으면서 익은 토마토의 위치를 큐에 넣고 큐 사이즈만큼 돌면서 큐의 크기가 0이 될 때까지 돌리면 된다.이때까지 포스트를 올린 문제는 대부분 두 가지 유형으로 볼 수 있다. 이 문제에서 우리가 중심적으로 봐야하는 익은 토마토나 불이나 불! 문제에서 우리가 봐야하는 불이랑 사람의 위치를 알아야 하고 BFS를 돌리면서 주변으로 퍼지게 하는 느낌으로 짜면 된다.이러한 문제와 다르게 단지번호붙이기, 유기농 배추와 같은 문제는 한 좌표에서 주변으로 퍼져나가 넓이를 계산하고 다른 좌표(방문하지 않았던 좌표)에서 또 퍼져나가면서 넓이를 구하는 문제가 있다.하지만 두 가지 유형엔 공통점이 있다. 바로 한 중..