728x90

분류 전체보기 172

Binary Tree & Traversal [c++]

선형 자료구조 : queue, stack, array 등 비선형 자료구조 : binary tree 등 이진트리는 트리 자료구조를 활용해 데이터 탐색 속도 증진을 위해 사용하는 구조이다. 완전 이진트리인 경우 힙정렬(Heap sort)를 이용해 배열을 사용해도 괜찮았지만, 완전 이진트리가 아닌 경우에는 데이터의 낭비를 줄이기 위 해 포인터를 사용하는 것이 좋음. 이진트리에 사용되는 자료구조에 따라 각 탐색, 삽입, 삭제의 시간 복잡도는 아래와 같다. 이진트리에서 데이터를 참색하는 방법은 크게 3가지가 있다. Ⅰ. 전위순회(Preorder Traversal) (1) 자기 자신을 처리 (2) 왼쪽 자식을 처리 (3) 오른쪽 자식을 처리 Ⅱ. 중위순회(Inorder Traversal) (1) 왼쪽 자식을 처리 ..

Algorithm 2021.01.11

kruskal algorithm [c++]

ㅇ 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결 하는 알고리즘 -> 최소 비용 신장트리를 만들기 위함 ex) 여러 개의 도시들을 연결 하고자 할 때 비용을 최소한으로 하기 위해 사용 - 거리(cost)가 짧은 순서대로 그래프에 포함 시키면 됨 - 모든 노드를 최소비용으로 연결만 시키면 되기에 모든 간선 정보를 오름차순으로 정렬 한 뒤에 비용이 적은 간선부터 그래프에 포함 - 최소 비용 신장트리에서는 사이클이 발생하면 안 됨 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 그래프에 포함시키지 않음 ★ 사이클이 발생하는지 여부는 Union-Find 알고리즘을 사용 #include #include #include using nam..

Algorithm 2021.01.08

Union-Find [c++]

Union-Find는 그래프 알고리즘으로써, '합집합 찾기'라는 의미를 가진다. 여러개의 연결되지 않은 노드 집합들이 있다고 가정하자. (1) - (2) - (3) - (4) (5) - (6) - (7) - (8) 1,2,3,4와 5,6,7,8을 각각 연결되어있는 노드들이다. 여러한 그래프에서 '연결성'을 프로그래밍 언어로 표현하는 것이 Union-Find 알고리즘이다. Union-Find 알고리즘의 원리는 노드의 집합중 가장 작은 값을 가지는 노드가 부모 노드라고 가정하고, ex) 1,2,3,4의 부모노드는 모두 1이다. 부모노드가 같으면 연결되어 있다고 생각하는 것이다. find는 해당 노드의 부모 노드를 찾는 알고리즘이고 ex) find(3)을 하면 1을 반환 union은 노드의 집합을 연결하는 알..

Algorithm 2020.05.07

DFS [c++]

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다. ㅇ 스택을 이용하여 구현하지만 재귀함수를 이용하면 재귀함수는 스택의 원리를 이용하고 있기 때문에 스택이 없어도 구현 가능하다. 1. 스택에서 최상단 노드를 확인한다. 2. 최상단 노드에 방문하지 않은 연결된 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 인접노드가 없다면 스택에서 최상단 노드를 제거한다. 아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다. // dfs #include #include #include using namespace std; int n,m,startNode; vector visit; vector node; void dfs(int start) { if(visit[start]) return;..

Algorithm 2020.04.18

BFS [c++]

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다. ㅇ 큐를 이용하여 구한다. ㅇ 사용 예) 미로찾기 등 1. 큐에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다. // bfs #include #include #include #include using namespace std; int n,m,startNode; // n : 정점의 개수, m : 이어져있는 노드의 수, startNode : bfs를 시작할 노드 vector visit; // 방문한 노드를 표시하기 위함 vector node; // vector 배열을 받기 위함 void bfs(int st..

Algorithm 2020.04.18

웹해킹 7주차 - 1

이번주에는 저번주보다는 비교적 난이도가 쉬울 것이다. 이번주는 25, 23, 11번을 풀어보겠다. 먼저 25번을 풀어보겠다. 주소창에 hello.txt , index.php, password.php 를 입력해 보았지만 아무런 변화가 없었다. 이로써 한 가지 추측을 해 볼 수 있는데, ?file=hello 가 사실은 hello.txt인데 확장자를 생략시키는 코드가 짜여있어서 hello로 나타나 있다는 것이다. 그래서 password.php를 쳐도 password 변형되서 입력되기 때문에 password.php로 넘어가지 않는 것이다. 그렇다면 password.php를 입력받게 하려면 어떻게 해야할까? 예를들어 ?file=index.php 에 + .txt라는 확장자가 자동으로 붙는 코드일 경우 ?file=i..

Web hacking 2017.12.02

웹해킹 6주차 - 2

47번 문제를 풀어보자.. 메일 해더 인젝션이라고 뜬다 F12를 눌러보자 index.phps로 들어가보자. 소스를 보면 password를 admin@webhacking.kr 이라는 이메일에 보내는 거같다. 사실 필자도 mail header injection을 잘 몰라 선배에게 도움을 요청했다 ㅠㅠ "cc : 이메일형식" 을 이용하면 해당 이메일에도 password를 전송한다고 한다. 이를 위해 크롬에서 Falcon proxy를 추가하고, 위의 툴을 사용해서 중간에 패킷을 가로챌 것이다. 위의 버튼을 클릭해서 add를 누른다음 해당 형식에 맞게 아무거나 써주면 된다. 위의 툴을 실행시키고 Proxy -> intercept -> off를 on으로 바꾼후에 이메일 형식을 아무렇게나 입력하고 아래칸에 cc : ..

Web hacking 2017.11.20

웹해킹 5주차 - 3

마.지.막 42번! ㄱㄱ (갈 수록 짧아지는건 기분탓) 위에 것 부터 들어가자. 다시나오자 ㅎ.. F12를 눌러보자. 이제 이쯤이면 인코딩 디코딩에 관해서는 익숙해질 때가 되었다고 생각한다. 누가봐도 base64와 연관되어 있을 것 같지 않은가?! 인코딩 ㄱㄱ zzahn! 위 값을 DOM탐색기를 이용해 test.txt와 같은 형식으로 바꿔서 입력하자. a href=?down=위 인코딩값= 해주면 된다! 오오오옹ㅇㅇ 뭔가 다운했다! 아까 개발자 도구에서 초록글씨로 Password is only numbers 라고 했으니 알집 비밀번호를 푸는 풀을 이용해 풀어보자. 비밀번호는 852! 빨리 풀어보자 (필자는 얼른 자고싶다) 위 사이트로 들어가보자! 패스워드가 나타났다!!! 이상으로 이번주 문제 풀이를 마치겠다.

Web hacking 2017.11.06