버그 해결을 위한 모든 질문을 던져
+4 votes
474 views

전 잘몰라서 그냥 가만히있었는데 이제는 알고싶습니다

 

리플까지 다 막으시면 게임코디 명물이 ;ㅅ;

asked (238 point)
수정됨 , 474 views
여긴 드립을 치기도 애매한데......ㅠ
**에서 가장뜨거운곳 데스벨리
읔ㅋ 그 글에 더 이상 댓글을 달 수 없다니.ㅋㅋ

마지막으로라도 댓글을 달아 둘 걸 아쉽네요.ㅎ
연말 연초에 인사하러 가면서 행운을 비는 장소인데 ㅠㅠ
이 글에 좋아요를 찍기위해 throw bug 들어왔습니다 ㅋㅋ

이거 근데 원본 글은 이제 못보나요 ㅜㅜ

https://www.c-sharpcorner.com/article/linked-list-implementation-in-c-sharp/

연결리스트를 구현하여 사용할 수 있다면, 얼마든지 만들어서 사용할 수 있습니다."
위 URL들어가면 C#으로 구현된 연결리스트 코드가 있습니다.

http://lab.gamecodi.com/board/zboard.php?id=GAMECODILAB_QnA_etc&page=1&sn1=&divpage=2&sn=off&ss=on&sc=on&select_arrange=last_comment&desc=desc&no=2652

 

예를 들면 c++ 에서는  list  map  hashmap 같은것들은 node 기반이지 않습니까?

그래서 node를 이용해 한번에 지울수가 있었는데  물론 map 같은 경우는 지운후에는 균형 트리 정렬을 다시 하겠지만요

c# 자료구조를 좀 보고 있는데   처음에는 node 기반 자료구조가 아예 없나 싶더라고요

기것찾아낸것이 LinkedList  (기본 자료구조에 소개엔 나오지도 않음) 밖에 없더군요

희안한게  노드기반형 자료구조는 자료를 찾은후 그 노드를 기억했다가 다시 검색하지 않고 지울수가 있었는데

c#에서는 그런 map hashmap 같은게 없어보이더라고요

그냥 키값을 다시줘서 지우던데 원래 이렇게 밖에 안되던가요?

 

 

메모리 관련된 글을 검색해보다 우연찾게 보게된 글인데 이쪽 업계에서는 성진순례 글인가 보군요. 끝없이 달리는 댓글을 보면서, 그래서 이와 관련된 글을 한번 써보는 것도 재밌을 것 같아서 써보려고 합니다.

 

이 내용에 대해서 정확하게 이해를 해보려면, 자료구조와 알고리즘의 성능 개선에 대해서 공부를 좀 많이 해야 합니다. 대부분 연결리스트를 기반으로 한 탐색 알고리즘에 대해서는 잘 모르기 때문에 발생된 문제라고 보여지네요.

 

1. C#에서는 노드 기반형 빠른 자료구조가 없던가요?

어떤 프로그래밍 언어든, 연결리스트 기반으로 탐색 성능이 높은 알고리즘을 구현하여 사용하면 됩니다. 다만 그걸 구현할 수 있는 프로그래머의 능력이 되는지 안되는지가 문제의 핵심이라고 보면 됩니다.

 

2. C#에서의 포인터

C#이라는 언어에서는 포인터를 사용하지 않는 것을 권장합니다. 필요하면 얼마든지 개발 환경 tool에서 해제하여 포인터를 사용할 수가 있습니다.

 

http://soulduo.tistory.com/38

 

이때 체크해야할 항목이 "안전하지 않은 코드 허용"이라고 쓰여져 있으니, C# 프로그래머들은 포인터가 마치 위험한 도구인양 생각을 하는 모양입니다. 그래서 위험한 장난감이라고 쓰여져 있나 봅니다. 포인터를 사용하면 해당 코드에 대한 신뢰성을 확인할 수 없다고 하는데, 이렇게 얘기하는 사람들은 포인터를 사용하지 못하기 때문이라고밖에 생각할 수가 없습니다.

그리고 대체적으로 댓글들을 보면, 이미 논문으로 발표된 알고리즘이나 혹은 자료구조들에 대해서 뭐가 검증이 필요하다고 하는 것인지를 알 수가 없네요. 대부분 잘 모르는 사람들이 자기의 약점을 드러내고 싶지 않을 때 주로 이런 얘기를 합니다. 그냥 검증을 하면 되는 것이죠. 뭐가 어려울게 있겠습니까?

 

 

3. C#에서 포인터를 사용하지 않는 이유

 

C와 C++의 가장 강력한 무기는 포인터입니다. 이 포인터를 이해해야만 제대로 자료구조와 알고리즘을 구현하고 이해할 수가 있습니다. 하지만 가장 난해한 개념이고, 배우려고 하는 사람들을 좌절시키는 것도 바로 이 포인터입니다.

이 포인터라는 개념은 전세계 프로그래머라면 다 어렵다고 생각하는 개념이라고 생각하면 됩니다.

1972년도에 개발된 C언어이지만, 아직까지도 제대로 이해를 하지 못하고 있는 개념이 포인터라고 보면 됩니다 .

국내/국외에 출간된 책들 중에서 포인터에 대해서 제대로 설명되어 있는 책은 없다고 하면 믿기지 않겠지만, 대부분이 다 틀린 내용입니다.

 

포인터에 대한 개념 및 정의 부터가 데니스 리치가 쓴 책과는 다르게 설명하고 있는데, 맞을 수가 없습니다.

 

1990년대 초반에 나타난 자바라는 언어에서는 그래서 포인터를 제외한 코드 형태가 사용이 됩니다. 내부적으로 동작되는 것은 포인터의 개념이 그래로 남아 있습니다. 다만 "*" 역참조 연산자라는 개념이 사라지고, 이를 대신해서 사람들이 익숙한 [] 형태로 메모리 접근하는 방법만 남겨놨다고 보면 됩니다. call by address라는 개념은 배열을 넘길때만 사용되고, 이 이외의 식별자에서는 사용하지 못하게 막아놨습니다. 당연히 call by reference라는 개념도 사용하지 않습니다.

그래서 call by address 혹은 call by reference라는 방법을 사용을 해야하기 때문에 자바라는 언어 부터는 static이라는 키워드를 적극적으로 사용을 합니다. 거의 모든 코드에 static을 사용하지 않으면 안되게 되었습니다.

 

(그래서 이때부터 코드가 지저분하게 됩니다. 개인적으로 이런 static을 사용하는 것을 좋아하지는 않아서, 그냥 깔끔하게 *나 & 사용하면 코드의 구조가 참 깔끔하게 나타나는데, static을 사용하면 코드 리뷰할 때마다 짜증이 나는 경우가 많습니다. 이건 개인적인 견해임을 밝힙니다.)

 

자바라는 언어는 이런 특징이 있습니다. 또한 자바는 C++언어와 다를 바가 없는 거의 동일한 언어라고 보면 됩니다.

C++ + STL 이 자바+Collection이라는 형태로 바뀔뿐 그 형태나 사용하는 방법은 거의 유사합니다. 역참조 연산자나 혹은 참조 연산자를 사용하지 못하는 경우를 다른 식으로 바꿔놨을 뿐, 동작하는 것은 C++과 동일합니다.

 

C++의 STL, 혹은 자바의 Collection에는 주로 자료구조와 알고리즘 수업에서 학습하는 여러 자료구조의 형태나 혹은 알고리즘들이 대부분 구현되어 있어서 프로그래머들이 그냥 가져다 쓸 수 있도록 해놨다 생각하면 됩니다.

당연히 해당 자료구조나 알고리즘을 구현하지 않아도, 혹은 제대로 이해하지 못해도 사용하는 법만 알고 있으면 가져다쓸 수 있으니, 코드 생산성은 높을 수밖에 없습니다.

list, hash, map 프로그램을 개발하면서 사용 빈도수가 높은 알고리즘들은 대부분 C++의 STL이나 자바의 Collection안에 구현이 되어 있습니다.

 

대부분 이러한 STL의 자료구조나 알고리즘은 그 기반이 배열 기반으로 동작되게 작동됩니다. STL에서 제시된 반복자라는 개념과 container라는 개념이 바로 그 배열 기반, 즉 연속적인 메모리 할당 구조에 기반하여 만들어졌다고 생각하면 됩니다. 반복자와 컨테이너는 동작원리는 처음에 일정정도 메모리 크기를 할당하고 부족하면 일정 크기만큼 재할당하는 형태로 코드가 실행된다고 개념적으로 이해를 하면 됩니다. C언어에서 malloc하고 나서 realloc()해서 할당하는 것과 동일하다 생각하면 될 것입니다.

메모리를 얼만큼 사용하는지에 대해서 고민할 것이 아니라면, 그냥 자바나 혹은 C#을 사용하면 됩니다.

 

C#이라고 하는 언어는 자바 프로그래머들이 진입을 쉽게 할 수 있도록 거의 유사한 형태로 만들어진 프로그래밍 언어라고 보면 됩니다. 간단하게 생각하면 Visual C++/MFC의 자바 버전이라고 보면 됩니다. 당연히 자바 프로그래머들이 포인터에 대한 이해가 낮기 때문에 포인터 사용을 허용하지 않은 것이고, Visual C++ 혹은 win API에 대해 기반이 있는 프로그래머라면 C#에서 포인터를 사용하면 되는 것입니다.

 

4. list, map, hsah, set과 같은 자료구조들은 2가지 형태로 만들 수 있습니다.

모든 코드는 선형적인 메모리 구조인 배열 기반에서 코드를 작성할 수도 있고, 비선형적 자료구조를 선형적인 메모리 공간에 표현하는 연결리스트 기반으로 코드를 작성할 수가 있습니다.

 

연결 리스트를 이해를 하려면, C언어의 포인터에 대한 개념과, 연결리스트에서 사용되는 자기 자신을  참조하는 구조체 형태에 대해서 이해해야 합니다. 이 구조체 형태를 이해해야만, 그리고 구조체 멤버를 접근할 때 사용하는 ".", "->" 멤버 접근 연산자에 대해서 알지 못하면 연결리스트 기반으로 코드를 짜는 것은 포기를 해야합니다. 대부분이 바로 이 지점을 극복하지 못하고 포기하는 것이 현실이며, 대부분 자기가 연습했던 코드나 봤던 코드의 형태로 포인터 및 멤버 접근 연산자를 사용하다가 실무에서 어려움을 겪는 경우가 태반일 것입니다.

 

 

대부분의 댓들을 보니, 배열 기반의 자료구조 형태에서 벗어나지 못한 것으로 판단됩니다.

연결 리스트를 제대로 사용하여 자료구조를 사용하는 분들은 별로 보이지가 않았습니다.

 

현실 세계에 존재하는 데이터를 표현하는 자료구조는 그래프입니다. 대부분 자료구조에서 학습하는 여러 자료구조는 이 그래프를 이해하기 위해서 배우는 내용이라고 보면 됩니다. 간단하게 예를 들어서 설명하면,

 

그래프를 구현하는 방법은 포인터를 모르는 사람이라면, 배열 기반의 2차원 배열 형태로 구현을 해야할 것입니다.

포인터를 알고 연결리스트를 사용할 수 있다면, 구조체를 사용하여 연결 리스트(싱글 혹은 더블)로 구현하여 포인터배열 형태 혹은 배열포인터, 이중포인터로 사용한 형태로 구현할 수가 있습니다.

 

이 두가지 방식은 메모리의 복잡도에서 차이가 발생합니다. 연결리스트를 사용하는 것은 바로 이런 메모리를 좀더 효율적으로, 데이터의 삽입/삭제 순간에 동적으로 할당/해제해서 사용할 수 있다는 것을 의미합니다. 당연히 불필요한 메모리를 최대한 줄일 수 있게 되는 것입니다. 배열 기반으로 구현한다면 모자라거나 혹은 남거나 두가지 경우밖에 발생하지 않습니다.

즉 자바의 collection이나 C++의 stl을 그대로 사용한다는 것은 이러한 메모리적인 부분, 불필요한 부분은 어쩔수 없이 안고 가겠다고 하는 것이나 다름이 없습니다.

 

이런 부분은 회사의 정책 혹은 프로젝트의 비용, 혹은 개발자의 개발 능력에 달려 있는 부분이기 때문에 따로 논할 필요가 없습니다. 윗 댓글들을 보면 서로 감정 싸움이 발생하는 이유가 바로 여기에 있는 것입니다.

 

자바 혹은 C#위주로 코딩을 해왔다면 당연히 포인터에 대한 개념은 약하고, 자료구조를 직접 구현하는 부분이 안될 것이니 그냥 있는 라이브러리 가져다 쓰면 됩니다.

 

C/C++ 기반 개발자라고 자료구조를 다양하게 구현해봤다면, C#에서 포인터 사용 해제를 체크하고 포인터 사용해서 연결리스트 기반으로 해당 자료구조를 구현하면 될 일입니다.

 

 

5. hash, map, 이런 자료구조를 쓰고, 이 알고리즘에 대한 복잡도 성능에 대해서 얘기를 하려면 우선적으로는 다음과 같은 사항에 대해서 이해를 하고 얘기를 해야 합니다

- 재귀

- 재귀의 성능을 개선시킬 수 있는 방법

- 재귀의 메모리 overflow를 어떻게 막을 것인가?

- 제한된 메모리에서 어떻게 탐색 속도를 빠르게 할 수 있을 것인가?

 

자료구조와 알고리즘에서 학습하는 내용입니다.댓글들을 보면 이런 기본적인 이해도 안되어 있는 분들이 단순히 stl이나 혹은 collection을 가져다 쓰면서 이런 경우는 이렇다 저런 경우는 저렇다라는 식으로 불필요한 논쟁을 벌이고 있습니다.

 

포인터에 대한 이해를 하지못한다면, 당연히 연결리스트 기반으로 코드를 작성하지 못할 것이고, 그렇다면 탐색 성능과 관련한 알고리즘에 대한 이해는 낮을 수밖에 없습니다. 그러니 이런 댓글들을 통해서 쓸데없는 논쟁을 하고 있는 것입니다.

 

트리 자료구조 혹은 그래프 자료구조의 성능을 결정짓는 것은 tree의 높이 혹은 depth입니다.

우리가 사용하고 있는 배열은 트리의 관점에서 보면 편향 트리라고 볼수가 있습니다. 이것보다 성능을 좀 더 개선시킨 형태가 노드가 2개인 binary tree입니다. 하지만 이런 binary 트리의 경우 실제 구현해서 사용하면 tree의 노드 깊이가 깊어져서 탐색을 할때 재귀를 사용하면 메모리 overflow가 발생합니다. 그래서 재귀적 탐색, 즉 bactraking하면서 불필요한 경우에 대해서는 탐색을 제외하는 branc and bound 혹은 prunning 기법을 사용하는 것입니다. 혹은 확률적인 부분을 고려하여 prunning할 수도 있습니다. 또는 tree node의 깊이를 줄이기 위해서 balanced tree라는 개념이 나오는 것입니다.

회전 혹은 압축과 같은 방식을 사용하거나 혹은 트리의노드 개수가 2개가 아닌 여러개 2-3, 2-3-4 tree 같은 것을 배우는 것이 바로 그러한 이유입니다. 패턴 매칭인 경우에는 접두어 혹은 접미어와 같이 공통적인 단어들이 있다면 그걸 하나의 노드 혹은 엣지로 통합하여 압축하는 방식으로 탐색 노드의 깊이를 줄이는 방법을 사용합니다.

 

6. 대부분의 댓글이나 혹은 게시글 본문 내용을 보면 핵심적인 내용에 대해서는 언급이 없고, 내가 맞다 니가 틀리다라는 식의 불필요한 논쟁만 하고 있습니다.

 

 

7. 댓들 중에서 이런 얘기가 쓰여져 있어서. 밑줄까지 그어져 있어서 더 눈여겨볼수밖에 없었네요.

 

링크드 리스트의 장점을 이용한 방식은 거의 없다는 것이 문제겠죠

배열과 링크드 리스트를 사용하는 장점과 단점은 서로 명확히 다릅니다

 

연결 리스트의 장점을 이용한 방식은 거의 없다고 얘기하는데, 탐색 성능을 높이기 위해서 사용되는 hash또한 메모리적인 부분을 고려한다면 연결 리스트 기반으로 작성되야 합니다. 배열과 연결리스트를 사용하는 장점과 단점은 서로 명확하게 다르다라고 했는데, 연결 리스트에 대한 기반 이해가 제대로 되어 있지 않네요.

연결 리스트도 배열입니다. 자기 참조 구조체 형태로 작성된 구조체 배열 혹은 클래스 배열입니다.

연결 리스트도 배열이며, 차원과 차원이 연결되어 있는 배열 구조 형태입니다. 비선형적인 자료구조를 자기 참조 구조체라는 형태를 사용하여 선형적인 메모리 공간으로 가지고 와서 표현하는 방법입니다.

 

근데 노드기반 자료구조는 LinkedList 외엔 사실상 존재하지 않는 다는겁니다.

 

노드 기반 자료구조를 왜 사용하는지에 대한 기본 이해조차도 없는 글이라고 생각하면 됩니다. 현재 상용 소프트웨어에서 사용되고 있는 대부분의 탐색 알고리즘은 연결 리스트 기반으로 작성된 알고리즘입니다.

 

 

8. 이정도가 딱 C# 포지션 위치에 대한 적절한 댓글로 보여지네요.

 

어쨋든 제가 C#을 쓰게 되면서 C# 제작자의 의도가 느껴졌던 부분은 딱 이겁니다 "바보도 쉽게 플그래밍 하게 하자!" 이거 같습니다 학생때 프로그래밍 배우면서 첫번째 난관이 바로 "포인터"의 개념이죠 그리고 위에서 말씀하신 노드라는 녀석도 결국 포인터의 개념과 엮여있구요 C#은 될수있도록 프로그래머가 포인터라는 개념을 잘 몰라도 짤수 있도록 언어가 만들어진거 같습니다 C#에서 쓰이는 자료구조들이 대부분 포인터의 개념을 몰라도 쓸수 있습니다 메모리 제어 하려면 포인터의 개념을 알아야 하는데 그런거 X까 가비지 컬렉터가 알아서 다 해줍니다 성능? 그딴거 너네가 신경쓰지마 너네가 앤간한 최적화는 신경 안써도 될만큼 하드웨어가 발전할거고 또 우리가 제공한것만 쓰면 걱정 안해도 돼 <--- 거의 이런 뉘양스입니다

 

9. 본문 게시글에 대한 질문에 대한 답을 한다면.

C#이라는 언어는 포인터를 사용하지 못하는 사람들이 쉽게 언어를 익혀 사용할수 있도록 배려된 언어입니다.

당연히 포인터를 이해해야만 구현할 수 있는 자료구조들은 제공하지 않는 것이 당연한 것입니다. 약간의 성능 저하를 고려하더라도, 단순히 STL 혹은 자바 colletion을 사용할 수 있는 수준이면 사용 가능하게 만들어놓은 언어입니다.

 

하지만 포인터를 사용하고 자료구조를 직접 구현해서 사용할 수 있다면, 왜 위험한 장난감이라고 얘기하는지는 모르겠지만, 포인터를 사용하여 자료구조에 대한 공부를 다시하면서 구현해서 사용하면 됩니다. 그러면 5번 항목에서 얘기하는 내용들을 이해해야 제대로 자료구조를 구현하여 사용할 수 있을 것입니다.

 

10. 감정이 격화되는 댓글 부분을 보면, 너는 C#만 쓸줄 아는 구나 그래서 이것밖에 못하는구나라고 평가하는 부분들과 자신의 알고 있는 것이 전부인양 그것을 고수하는 부분들이 충돌하고 있다고 볼수 있습니다.

 

이 댓글을 보면서 그런 생각이 들더군요. 이 지긋지긋한 포인터. 이게 조금더 쉽게 사람들이 이해할 수 있었다면.. 이런 논쟁은 필요가 없었을텐데.

 

데니스 리치 형님은 너무 천재야.. 왜 쓸데없이 포인터 만들어내서 일반인들을 이렇게 힘들어하게 만드는지.......

포인터라는 개념이 없었으면, 이런 자료구조들도 좀 덜 나왔을텐데.....

 

앗 답변으로 해주셔도 되는데 ;ㅅ;

3 answers

+1 vote
윽 늦었다 ;
answered (19 point)
+1 vote
없습니다.

만약 있다면 사라졌을겁니다.
answered (100 point)
+1 vote
C++을 씁시다.
answered (12 point)

버그 해결을 위해 도움을 구하고, 도움을 주세요. 우리는 그렇게 발전합니다.

throw bug 는 프로그래밍에 대한 전분야를 다룹니다. 질문,논의거리,팁,정보공유 모든 것이 가능합니다. 프로그래밍과 관련이 없는 내용은 환영받지 못합니다.

96 질문
186 answers
194 댓글
211 users