자기계발을 멈추면 죽는다

프로그래밍/자료구조&알고리즘 (7)

등고선 알고리즘

프로그래밍/자료구조&알고리즘 스피비 2011. 5. 22. 22:26

등고선 알고리즘이란? 길찾기 알고리즘의 한 종류로 도착점에 0이라는 숫자를 넣고 주변을 검사하여 벽이 아닌 인접한 블록에 -1로 쓴다. 다시 -1 주변을 검사하여 벽이 아닌 인접한 블록에 2를 쓰고,이런 식으로 출발점까지 가장 적은 수가 나오는 경로를 찾아가는 알고리즘이다. 이러한 방법이 마치 등고선을 그리는 방법과 비슷하여 등고선법이라고 한다. 구현방법 1. 각 셀을 -1로 초기화 한다. -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2. 도착점을 0으로 설정한다. -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 3. 도착점부터 각 셀에 순서대로 번호를 매긴다. -1 -1 4 -1 -1 3 -1 4 3 2 -1 -1 ..

링크드 리스트 파일 입출력할때 skill

프로그래밍/자료구조&알고리즘 스피비 2011. 4. 9. 23:08

링크드 리스트의 특징상 총 개수를 알 수 있는 방법이 없다. 그래서 FILE 저장할때는 그 크기를 알려주는게 좋다! 저장할때 처음부분에 리스트 크기를 넣어주고, 읽을때 그 크기를 읽어서 읽은만큼 for문을 돌려주는 센스! 무슨 말인지 모르겠다면 게임프로그래머를 위한 자료구조와 알골리즘 링크드리스트 파일 입출력 부분 참조!!

배열의 빠른 제거 skill

프로그래밍/자료구조&알고리즘 스피비 2011. 4. 9. 23:05

보통 배열의 중간요소를 제거할땐, 제거할 항목 이후의 항목들을 모두 한 칸씩 앞으로 당기는 식이다! 하지만, 이런식으로 진행하기엔 속도가 느릴 수 있다. ex) 7을 제거한다면 3 5 6 7 1 2 9 4 ↙ ↙ ↙ ↙ 3 5 6 1 2 9 4 4 그래서 배열의 빠른 제거 skill이 있는데, 이는 제거할 항목을 그냥 마지막 index의 값으로 덮어쓰는 방법이다. 좀 무식한(?!)방법이긴 하지만 속도에서 완전 유리하기때문에 게임에서 자주 이용된다!. 이 방법을 사용할땐 순서가 중요하지않은 경우에 이용된다!!! ex) 7을 제거한다면 3 5 6 7 1 2 9 4 3 5 6 4 1 2 9 4

시간의 복잡도 총정리(알고리즘)

프로그래밍/자료구조&알고리즘 스피비 2011. 3. 25. 15:46

시간 복잡도(알고리즘) 0. 들어가기 앞서서 자료구조와 알고리즘을 배울때 핵심은 공간과 시간 이용이다. 공간과 시간은 거의 항상 반비례하는 경향이있다. 시간복잡도: 어떤 알고리즘이 얼마나 걸리느냐(CPU사용량) 공간복잡도: 어떤 알고리즘이 메모리를 얼마나 쓰느냐(RAM사용량) 1.시간의 복잡도에 나타나는 수들 (맨날 까먹으니 웬만하면 외우자) 1(constant): 입력자료의 수에 관계 없이 일정한 실행 시간을 갖는 알고리즘 log N: 만약 입력 자료의 수에 따라 실행 시간이 이 log N 의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다. N(Linear): 입력 자료의 수에 따라 선형적으로 실..

자리수 제한 없는 수를 컴퓨터로 입력하기?

프로그래밍/자료구조&알고리즘 스피비 2011. 3. 22. 16:33

오늘 자료구조 공부하면서 상당히 흥미로운 것을 발견했다. 우리가 일반적으로 사용하는 int char 같은 기본 자료형은 표현할 수 있는 수가 4바이트, 1바이트... 이런식으로 지정되있다. 그렇다면 1조같은 수가 입력되면 어떻게 처리되야되야할까?!?! 당연히 int같은 자료형을 쓰면 에러가 난다. 그렇다면 어떻게할까??!?! 답은 여러가지가 존재할 수 있겠지만 이렇게 처리하는것이 좋다 =>>> 1. 컴퓨터상은 어짜피 2진수가 길게 늘여진 모습이니까 2진수를 4자리씩 나누면 16진수가 된다. 2. 이렇게 나누어진 16진수를 10진수로 변환을 해준다!!! ( 16진수 -> 10진수 ) 3. 나누어진 수를 10진수 배열에 하나씩 넣는다. 그렇다면 연산은 어떻게 할까? =>>> 1. 컴퓨터상은 어짜피 2진수가 ..

Copyright © 자기계발을 멈추면 죽는다 All Rights Reserved
Designed by JB FACTORY

티스토리툴바