분류 전체보기
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]..
[C] 문자열과 포인터
[C] 문자열과 포인터
2022.04.01지난번에 배웠듯 C에서 문자열을 표현할 때는 char타입의 배열을 사용해 마지막에 null (\0)문자를 붙이는 것으로 표현할 수 있다. 그런데 포인터 변수로도 배열을 표현할 수 있다면, 문자열도 포인터 변수로 표현할 수 있지 않을까? 표현할 수 있다. 하지만 첫 번째 방법과 두 번째 방법은 차이점이 있다. char * s1 = "your team"; 처럼 포인터 변수를 사용해 문자열을 표현하면, 문자열을 새로 할당하는 것도 가능하고, 문자열이 아니라 char의 주소를 할당하는 것도 가능하지만, 문자열의 일부분을 인덱스를 통해 변경하려고 하면 오류가 발생한다. 이는 자동 할당된 문자열에 대한 규칙으로 받아들여야 한다. char타입의 배열로 문자열을 선언하게 되면 아까와는 반대되는 상황이 발생한다. 배열 ..
[C] 포인터 연산
[C] 포인터 연산
2022.04.01포인터도 값이니 사칙연산이나 증감 연산자를 적용할 수 있지 않을까? #include #include int main() { int num = 1234; int *p = # printf("%p\n", p); printf("%p", p+1); } 포인터p의 값이 1000이라고 했을 때 p+1은 1001이 될까? 포인터 변수에 대해서도 덧셈과 뺄셈은 수행할 수 있지만, 정수 변수의 덧셈과는 다른 양상을 보인다. 변수의 타입에 따라 연산의 단위가 달라진다. 주소를 값으로 바꿔주는 * 연산자에 대해서 덧셈과 뺄셈을 수행해도 직관적인 결과를 얻을 수 있다. 배열과 같은 양상으로 연산을 수행한다. 당연하겠지만, *(ptr) +1을 출력하면 12가 출력되고, 배열 범위를 벗어나면 오류 대신 쓰레기값이 출력된다...
[C] 배열과 포인터
[C] 배열과 포인터
2022.04.01자바에서의 배열과 C에서의 배열은 성격이 좀 다르다. 일단, 배열을 선언한 변수 이름은 배열의 시작 주소를 의미하는 포인터이다. ( arr = &arr[0] ) 자바에서는 arr을 객체로 저장해 arr자체로는 뭐 할 수 있는게 많이 없지만, C에서는 그 자체로도 의미하는 바가 있다. 그러면, 변수명이 배열의 시작 주소를 의미한다고 했으니.. 특정 주소를 할당할 수도 있지 않을까? 라고 생각할 수도 있지만, 할당은 불가능하다. 포인터변수와 배열의 변수명은 굉장히 유사하지만, 배열의 변수명에다가 값을 새롭게 할당할 수는 없다. (읽기는 가능) int main() { int arr[3] = {0, 1, 2}; arr[0]++; printf("%d \n", *arr); // 1 printf("%d \n", ar..
버블 / 선택 / 삽입
버블 / 선택 / 삽입
2022.03.31버블 정렬 가장 기본적인 정렬 방법이다. 배열이나 리스트의 인덱스 0부터 시작해 오름차순으로 정렬을 수행한다. import java.util.*; public class BubbleSort { public ArrayList sort(ArrayList dataList) { for (int index = 0; index dataList.get(index2 + 1)) { Collect..
선 설계 후 코딩
선 설계 후 코딩
2022.03.31문제를 읽고 바로 키보드에 손이 가면 안된다. 특히 시간이 촉박한 상황에서, 급한 마음에 바로 키보드에 손을 올리게 되는 경우가 많은데 좋은 습관이 아니라고 생각한다. 1. 일단 문제를 천천히 읽으며 연습장에 간단한 케이스부터 고려해 어떻게 해결할 지 생각한다. 2. 해결 방법이 보이면, 문제를 여러 파트로 분리해 파트별로 풀이 로직을 메모한다. 3. 파트별로 사용할 변수와 알고리즘을 생각하고 메모한다. 알고리즘 문제를 풀 때는 항상 침착해야 한다.