본문 바로가기

programming35

[graph] BFS,DFS graph를 나타내는 2가지 방식인접 행렬(Adjacency matrix)nxn 형태의 행렬로 나타냄. M(i,j)는 정점 i와 j를 연결하는 간선이 존재한다는 의미가 된다. 무방향그래프라면 i와 j가 서로 연결된 상태이며 M(i,j)=M(j,i)인 상태이다.저장공간은 O(n^2)이며, 어떤 노드 v에 인접한 모든 노드를 찾는것은 행렬의 한 row를 전부 탐색하는 것과 같기 때문에 O(n)이고, 어떤 간선 E(u,v)가 존재하는지 확인하는 것은 M(i,j)를 확인하면 되므로 O(1)이다.인접 리스트(Adjacency list)정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다. 예를 들면 간선 E(1,2), E(1,5), E(5, 4)가 존재한다고 할 때 정점의 배열의 원소 중.. 2017. 7. 23.
R과 JDBC 연동 oracle 연동..driver drv 2017. 7. 17.
[boj-4811]알약 나는 항상 보면 접근 자체를 복잡하게 생각하는 경우가 많다. 부족한 두뇌로 복잡한 계산을 생각하다보니 스스로 지쳐서 머리 회전이 멈추는 듯 하다. 재귀는 항상 기억할 것은, 상태공간트리를 그려가며 작은 sub-problem으로부터 base case를 먼저 생각하고 그 후 recursion case를 정해 나가는 것이다. 이 과정만 제대로 할줄 안다면 정말 완벽할텐데.. 어쨌든 문제는 다음과 같다. 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 .. 2017. 7. 15.
(Recursion) 미로 찾기 출처: 인프런-영리한 프로그래밍을 위한 알고리즘 강좌(권오흠 교수님) 위와 같은 그림의 미로가 있다고 할 때 입구에서 출구로 빠져나가기 위한 경로를 구하고자 한다면 어떠한 방법이 최선일까요? 2중 for문을 통해서 찾아갈 수도 있겠지만 이는 너무 어리석은 짓이고.. recursion을 통해 해결할 수 있을 겁니다. 먼저 recursion을 통해 해결하기 위한 base case를 보면 다음과 같습니다.base case:참조된 점 (x,y)가 이미 출구인 경우 참조된 점 (x,y)가 벽인 경우그렇다면 recursion case는 무엇일까요? 이는 참조되고 있는 자기 자신을 제외한 인접한 점들에 대하여 재귀적으로 함수를 호출하면 될것같습니다.recursive case: 인접한 4개의 점들에 대해 재귀적으로 검.. 2017. 7. 9.

티스토리툴바