분류 전체보기
[C] 포인터와 함수
[C] 포인터와 함수
2022.04.13배열을 할당받은 변수명은 포인터 타입이다. 함수를 통해 배열을 전달하면, 배열 자체가 전달될까 아니면 포인터가 전달될까? 함수의 인자로 배열을 입력하면 주소 즉, 포인터가 복사돼 전달된다. 지난번에 스택프레임에 대해 배울 때 메모리 스택에서 활성화 된 값들만 조작할 수 있다고 배웠는데, 포인터를 사용하면 비활성화된 스택 프레임에도 접근할 수 있다. 그런데, 배열을 포인터로만 전달하게 되면 배열의 길이에 대한 정보는 전달하지 못한다. 배열에 있는 요소들의 합을 구하는 함수를 작성하고 싶은데, 이런 경우는 어떻게 해야 할까? 함수로 배열을 넘겨줄 때 배열의 길이를 함께 지정해 줄 수 있다. 일단 배열을 받는 함수는 정수 포인터 타입의 변수로 받아오고, 배열의 길이에 대한 정보인 len을 추가로 받는다. 물론..
최단 경로 - 다익스트라
최단 경로 - 다익스트라
2022.04.13가중치 그래프에서 가중치의 합이 최소가 되도록 하는 특정 경로를 찾는 알고리즘이다. 다익스트라 (Dijkstra) 그래프의 특정 노드에서 출발해 시작 노드를 제외한 나머지 모든 노드들에 대해 최단 경로를 찾는 알고리즘이다. 그림과 같은 그래프에서 A에서 출발해 B까지 가는 최단 경로를 구한다고 생각해보자. (가중치를 거리라고 생각하자) A에서 B로 바로 가면 거리는 8이지만, C를 거쳐 B를 가면 6의 거리로 갈 수 있으니 여기서 최단 경로는 6이다. A에서 출발해 B로 가는 최단 경로를 구해보자. 1. 시작 노드와 연결된 노드들에 대해 가중치를 저장할 배열을 만들고, 가중치를 저장한다. A : [8(B), 1(C), 2(D)] 2. 저장된 가중치 중에서 최솟값이 가리키는 노드를 기준으로 설정하고 해당 ..
Backtracking
Backtracking
2022.04.11분할정복이나 dp처럼 문제를 풀기 위한 전반적인 전략 같은 알고리즘이다. 문제의 해가 될 수 있는 후보군들 중에서 특정 조건에 부합하는 해의 집합을 찾을 때 사용한다. 처음에 해가 될 수 있는 후보를 하나 선택하고, 처음 선택과 연관해서 다음 해가 될 수 있는 후보를 하나 선택하는 방식으로 진행하고, 만약 연관된 해를 구할 수 없다면 처음으로 돌아가서(backtrack) 다시 후보를 선택한다. 트리 자료구조와 연관해서 이해하면 편하다. 각 후보를 DFS방식으로 확인하며, 조건에 맞지 않으면 해의 후보가 될 수 있는 위치로 돌아가 다시 탐색한다. 조건에 맞지 않아서 연관된 요소를 모두 포기하는 기법을 Pruning이라고 하고, 해당 요소가 조건에 부합하는지 확인하는 기법을 Promising이라고 한다. 백..
[백준] 17262 팬덤이 넘쳐흘러 - Java
[백준] 17262 팬덤이 넘쳐흘러 - Java
2022.04.06(가장 늦게 등교하는 사람의 등교 시간) - (가장 빨리 하교하는 사람의 하교 시간) import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Student[] arr = new Student[N]; for(int i=0;i o2.end){ return 1; }else{ return -1; } } }); int temp1 = arr[0].end; Arr..
Greedy
Greedy
2022.04.06탐욕 알고리즘이라고도 불린다. 재귀, 분할정복과 dp처럼 특정 문제를 해결하기 위한 알고리즘이라기보다는, 문제 해결에서 사용할 수 있는 도구 중 하나라고 생각하면 좋을 것 같다. 여러 가지 경우 중 하나를 결정해야 할 때, 선택의 순간마다 최적이라고 판단되는 케이스를 선택하는 방향으로 진행해 최종 값을 산출하는 알고리즘이다. 그리디 알고리즘을 사용해서 풀 수 있는 대표적인 문제로, 부분 배낭 문제가 있다. 무게 제한이 있는 상황에서, 최대 가치를 담을 수 있도록 배낭에 물건을 넣어야 한다. 물건들에 대한 무게와 가치 정보가 주어진다. 여기서, 물건을 쪼개서 넣을 수 있다면 분할 가능 배낭 문제 (Fractional knapsack problem)이고, 쪼갤 수 없으면 knapsack problem이라고 ..
DFS
DFS
2022.04.06Depth First Search. 깊이 우선 탐색이다. BFS와 마찬가지로 그래프 자료구조를 탐색할 때 사용하는 알고리즘이다. BFS와는 달리 DFS는 정점의 자식을 먼저 탐색한다. BFS에서는 두 개의 큐 자료구조를 사용해서 구현했지만, DFS에서는 BFS에서 탐색해야 하는 부분을 저장하는 큐 (needvisit)를 스택으로 바꿔서 활용한다. BFS의 로직과 DFS의 로직을 비교해서 공부해보자. import java.util.*; import java.io.*; public class Main { public ArrayList dfsFunc(HashMap graph, String startNode) { ArrayList visited = new ArrayList(); Stack needVisit = ..
BFS
BFS
2022.04.06이진 탐색과 순차 탐색처럼 특정 자료구조 내부를 탐색하는 알고리즘이 있듯, BFS는 그래프 자료구조를 탐색하는 알고리즘이다. 풀 네임은 Breadth-First Search으로, 너비 우선 탐색을 의미한다. BFS는 위와 같이 탐색을 진행한다. 그래프에서 레벨에 해당하는 부분을 탐색하고, 하나의 레벨에 대해 탐색을 마치면 다음 레벨에 대해 탐색을 시작하며 마지막 모든 원소를 확인할 때 까지 탐색을 진행한다. BFS를 구현하기 위해 먼저 Java에서 그래프를 구현하는 방법에 대해 알아보자. 자바에서는 HashMap과 ArrayList자료구조를 이용해 그래프를 구현한다. HashMap의 Key부분에는 그래프의 노드에 해당하는 정보가 들어가고, Values부분에는 해당 노드에 인접한 노드에 대한 정보가 들어간..
HTTP 통신과 라이브러리
HTTP 통신과 라이브러리
2022.04.05HTTP통신으로 get과 post등 여러 가지 요청을 보낼 수 있다. get은 웹사이트에서 정보를 얻어올 때 사용하고, post는 웹사이트에게 정보를 제공하고 제공한 정보에 따라 응답을 확인하는 과정이다. (회원가입과 유사하다) 파이썬으로 웹 크롤링을 진행할 때 위의 HTTP통신을 수행하기 위해 외장 라이브러리인 Requests를 사용한다. import requests response = requests.get('http://www.naver.com') html = response.text print(html) requests.get메서드로 특정 URL을 입력하면, 입력한 URL의 HTML코드를 Python객체로 받아온다. 가져온 정보를 분석하고 사용하기 편한 형태로 가공하기 위해 BeautifulSou..
이분탐색
이분탐색
2022.04.04배열이나 리스트에서 특정 원소를 찾을 때 탐색 알고리즘을 사용한다. 순차탐색은 말 그대로 맨 처음부터 탐색을 시작해 원하는 원소를 찾을 때 까지 탐색을 수행한다. ( O(n) ) 좀 더 효율적으로 탐색하기 위해 이분 탐색 알고리즘이 고안됐다. 일단, 탐색하려는 배열이나 리스트는 정렬된 상태여야 한다. 1. 전체 데이터의 중간을 비교한다. 2. 찾으려는 원소와 중간 원소를 비교해 중간 원소보다 찾으려는 원소의 값이 더 작다면 중간값을 기준으로 좌측을, 그렇지 않으면 우측으로 탐색 구간을 재정의한다. 3. 1 2 를 반복한다. 만약 찾으려는 원소가 배열 안에 없어도 쉽게 파악할 수 있다. 미루어 짐작할 수 있듯, 이분 탐색도 분할정복 기법과 재귀를 사용하는 알고리즘이다. import java.util.*; ..
퀵
퀵
2022.04.03기준점을 잡고 기준점보다 작은 데이터는 좌측, 큰 데이터는 우측으로 정렬한다. 좌측과 우측에 정렬된 데이터들에 대해서 다시 피봇을 설정하고 위 작업을 반복한다. 피봇으로 설정할 때 마다 원소의 위치가 정해진다. 모든 원소들에 대해서 피봇을 설정했으면, 정해진 위치를 기반으로 합치며 정렬을 수행한다. import java.util.*; public class Main { public static void main(String[] args) { ArrayList testData = new ArrayList(); for (int index = 0; index < 100; index++) { testData.add((int) (Math.random() * 100)); } QuickSort qSort = new ..
병합
병합
2022.04.03분할정복 기법을 정렬에서 적용한 정렬 방법이다. 1. 정렬되지 않은 배열을 하나의 원소로 분리 2. 분리된 원소를 정렬하며 병합 두 단계로 구성된다. public ArrayList mergeSplitFunc(ArrayList dataList) { if (dataList.size() leftPoint && rightList.size() > rightPoint) { if (leftList.get(leftPoint) > rightList.get(rightPoint)) { mergedList.add(rightList.get(rightPoint)); rightPoint += 1; } else { mergedList.add(leftList.get(leftPoint)); leftPoint += 1; } } // le..
동적 계획법 (Dynamic Programming)
동적 계획법 (Dynamic Programming)
2022.04.01한 문제를 여러 부분으로 쪼개서 각각의 문제들을 해결한 다음 해결한 결과들을 합병해 문제를 해결하는 분할 정복과 비슷한 알고리즘이다. 동적 계획법은 최하단의 결과를 이용해 상단 결과를 해결하는 방식이고, 이전에 계산한 값을 저장해 다시 계산하지 않게 하는 메모이제이션 기법을 사용해 문제를 효과적으로 풀 수 있게 한다. 분할 정복에서는 메모이제이션을 사용하지 않아 쪼갠 문제들의 결과를 활용하지 않는다. public class dp { public int dpfunc(int data) { int[] num = new int[data + 1]; num[0] = 0; num[1] = 1; for (int i = 2; i < data + 1; i++) { num[i] = num[i - 1] + num[i - 2]..