▸C언어42

• 

  정렬알고리즘_힙 정렬 [6/8] [ 힙 정렬이란? ] 이진 트리에 기반한 힙 트리구조를 만들어가며 배열을 정렬시킴 병합정렬의 메모리 효율성 문제를 해결하면서 O(n*logN)의 시간 복잡도를 보장 결국 시간복잡도가 log지수의 증가를 가지려면 소그룹으로 분리시켜 정렬해나가야 함 소그룹으로 쪼개서 정렬하는 방법에 힙 트리(이진 트리) 구조가 적용된 방식이라 볼 수 있음 ​[ 이진 트리란? ] 하나의 노드에 자식 노드가 2개 이하인 트리 구조 ​[ 힙 트리란? ] 이진 트리 구조에서, 노드 간의 관계에 규칙성이 적용 된 구조 최대 힙 구조 : 부모 노드가 자식 노드보다 값이 큼 (가장 위 root 값이 최대값이 됨) 최소 힙 구조 : 최대 힙 구조와 반대 이진 트리를 최대 힙 또는 최소 힙 구조로 완성시킴 (최대값, 최소값을 빠르게 찾을 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_병합정렬 [5/8] [ 병합 정렬이란? ] 퀵정렬이 이미 정렬이 완료돼있는 경우 최악 시간 복잡도 O(n^2)을 가지는 문제를 보완 인접한 숫자 2개를 정렬하고 인접한 정렬 묶음을 다시 정렬하는 방식을 반복 수행 이미 정렬된 소그룹을 계속해서 합쳐 나가는 방식으로 O(n*logN)의 시간 복잡도를 보장 평균적으로는 퀵정렬과 비슷한 속도이지만 어느 상황에서나 속도를 보장할 수 있다는 장점 코드로 구성해보겠습니다. 반복문이 여러번 중복으로 들어가서 머릿속에서 그리는데 좀 어려웠습니다. 천재가 되고 싶다... ​ 병합정렬은 분할정복(퀵정렬처럼 분할해서 정렬) + 삽입정렬을 섞어쓰는 느낌입니다. 그룹을 잘게 쪼개서 시간 복잡도를 log지수로 만들고, 각 그룹을 정렬하는 방식입니다. 삽입정렬에서 설명드렸듯이 정렬이 많이 되어 있는 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_퀵 정렬 [4/8] [ 퀵 정렬이란? ] 특정 값을 기준으로 정렬해야할 데이터그룹을 소규모 그룹으로 쪼개가며 정렬하는 방식 일반적으로 정렬은 n의 크기에 따라 O(n^2)로 시간 복잡도가 증가하지만, n의 크기를 일정하게 유지해 나가며 데이터를 정렬하기 때문에 O(n*logN)의 평균 시간 복잡도를 지니게 됨 이미 정렬이 잘 되어 있는 경우는 삽입 정렬에 비해 비효율적인 방식이 될 수 있음 가장 첫 값을 피봇값으로 지정해서 시작 오른쪽으로는 피봇값보다 큰 숫자를 찾고 왼쪽으로는 작은 숫자를 찾음 둘 다 찾았는데 큰값의 위치와 작은 값의 위치가 교차되지 않았다면 두 숫자를 바꿔줌 두 위치가 교차되었다면, pivot값과 left 값을 바꿔줌 크로스가 발생했다는 것은, 현 left의 위치까지 피봇값보다 큰 값은 없다는 것을 의미.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_삽입정렬 [3/8] [ 삽입 정렬이란? ] 정렬 기준에 맞도록 배열의 중간에 끼워넣는 방식 앞쪽부터 계속 데이터 정렬을 수행하기 때문에 뒤로 갈 수록 수행 횟수가 줄어듦 일반 배열의 경우 값을 중간에 삽입하면 다른 데이터들을 뒤로 밀어줘야하기 때문에 비효율적 시간 복잡도 또한 O(n^2)로 비효율적인 구조에 속함 (최악정렬, 역순으로 정렬돼있을 경우) 선택정렬과 버블 정렬에 대비 수행횟수가 줄어들어 효율적인 편 삽입 정렬은 역순으로 정렬되어 있을 경우 매우 비효율적이며, 반대로 거의 정렬이 완성돼 있는 경우에는 매우 효율적인 구조가 됩니다. ​ 랜덤하게 정렬돼 있는 경우 또는 지속적으로 정렬을 해줘야하는 상황이라면 데이터가 많을 수록 배열의 이동이 많아지기 때문에 비효율적이 됩니다. 따라서 데이터 정렬이 항상 필요한 경우는.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_버블정렬 [2/8] [ 버블 정렬이란? ] 기준값과 다음값을 비교해서 작은 값을 앞으로 가져옴 이 과정을 계속 반복해서 마지막까지 가면 정렬 완료 코드는 간단하지만 O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2 선택정렬보다 값을 교체(Swap)하는 수행 횟수가 많으므로 더 비효율적이고 느림 arr[0] > arr[1] 이면 두 값을 바꿔줌 arr[1] > arr[2] 이면 두 값을 바꿔줌 ...반복... arr[8] > arr[9] 이면 두 값을 바꿔줌 (한 사이클 완료) arr[0] > arr[1] 이면 두 값을 바꿔줌 ...반복... arr[7] > arr[8] 이면 두 값을 바꿔줌 (한 사이클 완료) ...반복... ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_선택정렬 [1/8] [ 선택정렬이란? ] 전체 데이터를 모두 검색하는 과정을 반복해서 특정 기준으로 정렬하는 방법 쉽게 사용할 수 있으나, O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2 ​[ 오름차순 vs 내림차순 ] 왜 항상 헷갈리는 걸까요.. 내림차순 : 큰 것 → 작은 것 (높은 고도(500)에서 내려간다 (1)) 오름차순 : 작은 것 → 큰 것 (낮은 고도(1)에서 올라간다(500)) arr[0] ~ arr[9] 중 가장 작은 값을 찾아 "arr[0]"과 바꿔줌 arr[1] ~ arr[9] 중 가장 작은 값을 찾아 "arr[1]"과 바꿔줌 arr[2] ~ arr[9] 중 가장 작은 값을 찾아 "arr[2]"와 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  재귀함수_팩토리얼 예제 [1/1] 저는 개인적으로 시작할 때 들었던 악명 높은 포인터도 어렵다고 느껴본적이 없는데.. 오히려 재귀함수가 제일 어려웠던 것 같습니다. 물론 원리를 알고 나니 그리 어렵지만은 않지만요. 재귀함수는 잘못하면 무한루프가 돌기 쉬우니 조심하셔야 합니다. ​ [ 재귀함수란? ] 말 그대로 함수 안에 자기 자신의 함수가 다시 있는 것을 뜻 함 (Recursion) 특정 조건을 만족시킬때까지 함수실행-함수실행-함수실행 형태로 같은 함수 반복 수행 ​아래는 재귀함수에서 제일 흔한 예제인 팩토리얼 구현입니다. 5! = 5 * 4 * 3 * 2 * 1 == 120 3! = 3 * 2 * 1 == 6 아래 예제만 보면 굳이 재귀함수를 사용할 필요 없이 일반 반복문을 사용하면 충분해 보입니다만.. 같은 기능을 다른 범위나 다른 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  큐 구조_미로찾기 (최종 ver) [3/3] 만들다보니 갑자기 욕심이 생겨서 조금 더 기능을 추가하게 됐습니다. 중요한거만 얼른 하고 넘어가야 하는데 계속 딴길로 새서 문제네요.. 최단 거리를 찾기 위해 고민하다가 결국 모든 길을 다 돌아다녀봐야한다는 점에 착안해서 만들어봤습니다. 동서남북방향을 동시에 다 가보고 제일 먼저 도착하는 길을 찾는 방식입니다. ​ 이전 버전을 만들고 나서 좀 미흡해보였던 부분들을 수정하고, 추가로 필요한 기능들을 넣어서 다시 만들어 보았습니다. 분기점이 나올 때마다 새로운 길이 생김 몇 개의 길이 발생할지 모르니 일반 배열을 사용하기가 어려움. 연결리스트 사용 왔던 길을 되돌아가는 구조가 아니라서 스택구조와는 크게 관계가 없는 자료구조가 됨 아래와 같이, 출발점을 기준으로 갈 수 있는 길이 나오면 다시 그 길을 기준으로.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_미로찾기 (애니메이션 ver) [2/3] 애니메이션 형태로 만들기는 간단하네요. 내친 김에 직접 움직여서 탈출하는 게임으로도 만들어볼까 했지만.. 콘솔로 게임 만들기는 좀 찾아보다보니 로직이나 알고리즘 전개의 문제라기보단 윈도우 제어 함수를 다루는 것에 더 중점이 있는 것 같아서 굳이 거기까지 공부할 필요는 없단 생각이 듭니다. 하면 좋기야 하겠지만 빨리 공부하고 JAVA로 넘어가는 편이 더 나을 것 같네요. 애니메이션 형태로 출력하기 위해 두 가지를 수정했습니다. [ gotoxy() 함수 추가 - 출력 위치 지정 ] 기본 함수가 아니라 직접 만들어줘야함 (인터넷에 아주 많음) 유명한 함수 이름이 gotoxy()인데, 사실 이름은 마음대로 지정해서 쓰면 됨 windows.h 헤더파일에 있는 커서 위치 정보 변환 함수를 써서 만들어줌 시간이 나면.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_미로 찾기 [1/3] 이번 과제는 미로 찾기입니다. 두 달 가까이 열심히 공부했더니 이제 이정도는 꽤 순조롭게 짤 수 있게 됐네요. 왕기초 과제이지만 왕초보인 저는 아직은 이정도만해도 뿌듯.. 뭔가 애니메이션같이 진행되는 모습을 보고 싶은데 방법이 없나 내일 한 번 찾아봐야겠어요. 과정마다 하나씩 프린트할 수는 있지만 영 맘에 들진 않네요..ㅎㅎ 해당 과제는 유투브 '권오흠'님의 자료구조 강의를 참조하였습니다. [ main() ] 사실 이번 건 코딩보다 미로 그리는게 더 어려웠던 것 같음.. 미로크기는 언제든 변경할 수 있게 매크로를 사용 배열 내용이 낭비없는 구성이라 포인터 변수 배열 대신 일반 배열을 사용함 이동할 수 있는 최대값인 MAX는 ROW * ROW * 2 로 설정 #include #include #define .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_후위표기식_수식 계산하기(수정/기능추가) [3/3] 강의는 저랑 완전 다른 방식으로 풀어내네요. 여러가지 방면에서 다르지만 가장 큰 차이점은 괄호도 연산자와 마찬가지로 취급하여 처리한다는 점입니다. 그 외에는 함수를 어떤 방식으로 구성해서 사용했는가 정도의 차이 같습니다. 강의에는 나오지 않았지만 굳이 후위표현식으로 변환하지 않고 연산자가 나오면 바로바로 계산해도 될 것 같습니다. ​ 강의에서 진행한 방식과 제 방식을 섞어서 다시 최종 버전을 만들어봤습니다. 그리고 다시 하는김에 조금 더 완벽하게 만들어보기 위해 이것저것 기능을 더 추가해봤습니다. 강의에 풀이가 없는 기능들이라.. 얼마나 잘 짰는지는 알 수가 없네요. 일단 기능은 다 잘 됩니다. ㅎㅎ ​ 대략 아래와 같은 방식입니다. [수정사항] 괄호와 연산자를 하나의 스택(배열)을 사용해서 연산 순서 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_후위표기식_수식 계산하기(괄호 포함 수식) [2/3] 괄호를 어떻게 해결할지 한참 고민했네요. "괄호가 시작되면 별도의 수식으로 생각한다." 라는 점을 두고 한참 고민하다 답을 찾긴 했습니다. 맞는진 모르겠지만..ㅎㅎ ​ 기본 개념도는 아래와 같습니다. 괄호가 시작될 때마다 새로운 배열로 만들어주고, 괄호가 닫히면 괄호안의 값을 계산해서 앞 수식의 뒤에 붙여주는 방식으로 괄호가 없는 최종 수식을 만들어내면 되네요. 괄호만 잘 골라내주면 어제 만든 계산 수식을 이용해 간단히 짤 수 있었습니다. [ main() ] 수식이 길어져서 소스파일을 나눔 #include "Header.h" int main() { /* 중위표기식 원본 문자열*/ char form[] = "10+21*(2*(15-10)/2)-3"; int result = calculation_all(fo.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_후위표기식_수식 계산하기(괄호 없는 수식) [1/3] [구현 목표] 수식 내 우선순위에 따른 계산 결과 도출 ex) "2 + ((35+65) / 25) * 7" 과 같은 형태의 수식 계산 (엑셀과 비슷) 강의 보기 전에 미리 해보고 있는데 생각보다 엄청 복잡하네요.. 공부 하면서 가장 많이 느끼는 점은 간단해보이는 프로그램들이 실제로는 간단하지 않다는거.. 존경해요 MS.. 괄호까지 한번에 해결하려고 했는데 제 머리로는 답이 안나오네요. 일단 괄호가 없는 식을 계산하는 함수를 만들고, 괄호가 나오면 함수를 통해 괄호가 없는 것처럼 따로따로 계산하는 방식을 사용하기로 했습니다. ​ [ main() ] 입력받을 수식을 저장하는 공간, 후위표기식으로 변환 저장할 공간, 결과값 공간 생성 #include #include #include void postfix(ch.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  스택구조_괄호 수식 검증 [1/1] 해당 과제는 유투브 '권오흠'님의 자료구조 강의를 참조하였습니다. 닫힌 괄호는 가장 마지막에 나온 열린 괄호와 같은 유형이어야 한다라는 점만 유의하면 간단하게 작성할 수 있습니다. 어차피 스택과 같은 후입선출 개념을 사용할 수밖에 없습니다. 열린 괄호가 나오면 해당 유형 번호를 배열에 순서대로 저장 닫힌 괄호가 나오면 가장 마지막에 나온 열린 괄호와 유형이 같은지 확인 후, 해당 배열값을 제거 해당 순서의 열린괄호와 다른 유형의 닫힌 괄호가 나오면 에러값 반환 짝이 맞지 않아 배열의 값이 남거나 또는 모자랄 경우 에러값 반환 실제 엑셀과 같은 괄호 계산 식의 구현은 다음글들을 참조하시면 됩니다. 2019/12/09 - [C언어/알고리즘 및 자료구조] - 스택구조_후위표기식_수식 계산하기(괄호 없는 수식).. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  연결리스트_일반 배열 vs 연결리스트 [3/3] 일반 배열과 연결리스트는 비슷한 개념이지만, 사용 여부는 '순서'에 따라 달라질 것 같습니다. 일반 배열 : 들어온 순서대로 데이터가 쌓일 때 유리 연결리스트 : 들어온 순서가 관계 없이 특정 기준으로 데이터가 항상 정렬되어야 할 때 유리 [일반배열] 데이터 순서를 변경할 때 해당 순서 뒤의 데이터를 모두 복사-붙여넣기 해줘야함 중간에 데이터가 들어오거나 삭제될 때마다 뒷 순서의 배열을 모두 옮겨주는 작업이 발생 데이터 변경이 많을 수록 비효율적인 구조가 됨 배열의 크기는 미리 정해놔야하기 때문에, 빈 메모리 공간이 발생하여 비효율 초래 배열이 꽉 차 새로 메모리를 할당할 경우, 모든 데이터를 복사하는 작업 발생 ※ Point 따라서 데이터의 순서변경이 잦거나, 쌓이는 데이터의 수량을 적절히 파악하기 힘.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.