DSLOG

알고리즘 & 자료구조/Algorithm

[Algorithm] BFS & DFS (feat.Java)

그래프 자료 탐색 방법인 깊이우선탐색(DFS)과 너비우선탐색(BFS)에 대해 공부하고 기록해보자 그래프 정점(Node)과 정점을 연결하는 간선(Edge)으로 구성된 자료구조를 말한다. 특정한 하나의 정점에서는 간선으로 연결된 다른 정점들을 방문할 수 있다. BFS와 DFS는 하나의 정점에서 시작해 그래프의 모든 정점들을 탐색하려할 때의 방법들로 어떤 순서대로 모든 정점들을 방문할지에 차이가 있다. 그래프를 인접 리스트 와 인접 행렬 방법으로 표현할 수 있다. 인접 행렬 방법 int[][] adjArray = new int[n+1][n+1]; for(int i = 0; i < m; i++) { int v1 = sc.nextInt(); int v2 = sc.nextInt(); adjArray[v1][v2] ..

알고리즘 & 자료구조/Algorithm

[Algorithm] 이분 탐색

이분탐색(Binary Search) 에 대해 공부해보자 탐색? 많은 데이터 속에서 원하는 데이터를 찾는 것 완전 탐색 가능한 모든 경우의 수를 탐색하는 것으로 반복문 또는 재귀함수 등을 사용해 구현하게 된다. 자원 소모가 크지만 반드시 원하는 데이터를 찾을 수 있다. 자원 소모가 크다고 하나 반드시 필요한 상황 또한 있다. 컴퓨터를 사고 싶은데 돈이 아까워서 친구 핸드폰으로 구매하는 상황이라고 해보자 핸드폰 결제 문자 메시지 인증이 4자리의 숫자라는 것을 아는 나는 친구에게 인증번호를 물어보지 않아도 1000 부터 9999까지 모두 대입해보다 보면 결국 인증번호를 맞출 수 있게 된다. 물론 시간제한도 있고 현실은 그 전에 한 3번 틀리면 내 세션에서의 인증이 아예 막혀버리겠지만 그런 시스템을 배제한다면 ..