Computer Science

[네트워크] 네트워크의 기초 정리

보호되어 있는 글입니다.

[알고리즘] DP (동적 계획법)

| 동적계획법이란? - 복잡한 문제를 여러 개의 간단한 문제로 분리하여 해결하는 방법 - 원리 및 구현 방법 1) 큰 문제를 부분적으로 분리하여 분석한다 --> 부분적인 문제의 결과값은 항상 동일해야한다. 2) 1)을 통해 알게된 규칙을 통해 점화식을 생성한다. 3) 기존 배열과 dp배열을 어떻게 만들지 구상하고 4) 아래 두 가지 방법 중 적절한 구현 방법에 따라 수도 코드를 작성한다. 타뷸레이션 = 바텀-업 - for문을 사용하여 구현 메모이제이션 = 탑-다운 * 이미지 출처 : 나무위키 - 재귀를 사용하여 구현 | 피보나치를 통해 보는 동적 계획법 - 점화식을 통해 재귀로 푼 피보나치 문제 풀이는 아래와 같았다. // 피보나치 수열 // 재귀 (일반풀이 방법) - O(n^2), 계산했던 부분도 다시..

모듈러 산술

| 모듈러 산술 - 모듈러 (=mod = %)는 덧셈, 뺄셈, 곱셈에 있어서 아래와 같은 산술을 할 수 있는 특징이 있다. - 알고리즘 문제를 풀다보면 애매하게 정수 Max값을 넘을랑 말랑 하는 데이터가 있기도 한데, 그럴 때 이 모듈러 산술을 고려해서 문제를 풀면 굳이 Long 타입 변수를 쓰지 않아도 Int만으로 충분히 풀이가 가능하다. (a + b) % C = (a % C + b % C) % C (a - b) % C = (a % C - b % C) % C (a * b) % C = (a % C * b % C) % C | 참고할 만한 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 ..

[알고리즘] 분할정복

| 분할정복이란? - 폰노이만 구조를 만든 그 폰노이만에 의해 소개된 알고리즘 - 간략하게 말하면, 큰 문제를 작은 단위로 쪼갠 후 다시 조합하여 문제를 해결하는 방법을 말한다. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다 *출처 : 나무위키 | 분할정복 과정 1. 문제를 하나 이상의 작은 단위로 분할 2. 작은 단위에서 부분적인 해결 3. 부분들의 해결을 조합해 전체 문제의 해답을 찾는다. function F(x): if F(x)가 간단 then: return F(x)를 계산한 값 else: x 를 x1, x2로 분할 F(x1)과 F(x2)..

[알고리즘] 그리디

| 그리디란? - 그리디 알고리즘은, 매 선택에서 지금 이 순간 가장 최선이라 생각되는 답을 선택해 결과를 도출하는 것을 말한다. - 여기서 Greedy을 직역하면 '탐욕'을 뜻한다. - 왜 '탐욕'이라는 말을 쓸까? 그건 지금 이 순간의 부분적인 최적해가 항상 종합적인 최적해는 아닐 수 있음에도, 욕심쟁이와 같이 지금 보는 이 부분적인 선택이 전체의 최선이라 단정짓기 때문이다. rf. 여러 개의 도시가 연결된 도로가 있고, 그 도로 간에 이동 거리가 각각 다른 상황에서 가장 이동거리가 짧은 거리를 찾아야한다고 할 때, 그리디를 쓰면 가장 짧은 도로들을 선택하는 게 될 수 있다. - 정확함 보다는 적당히 맞는 답을 찾을 때 좋은 알고리즘이다. 따라서, 그리디 알고리즘을 근사 알고리즘으로도 부른다. - 언..

[알고리즘] 탐색 - DFS, BFS, 이진 탐색

| 탐색이란? 주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘 | 탐색의 종류 언제? 특징 시간복잡도 DFS(깊이 우선 탐색) 그래프의 모든 노드를 탐색하고자 할 때 - 재귀 또는 스택을 통해 구현 - 트리의 pre-order, in-order, post-order 순회 모두 DFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) BFS(너비 우선 탐색) 그래프의 가까운 지점부터 탐색하고자 할 때 - 큐를 통해서 구현 - 트리의 level-order 가 BFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) 이진 탐색 * DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다. 1. DFS (깊이 우선 탐색) DFS란, 루트에서 시작..

[시스템 소프트웨어] 쉘스크립트

보호되어 있는 글입니다.

HashSet<int[]>와 Hashset<ArrayList<Integer>>

| HashSet와 Hashset 문제를 풀다보면, 좌표를 집합에 넣어야 하는 경우가 있었다. 예를 들어, (0, 1), (2, 1) 그래서 아무 생각 없이 아래와 HashSet를 쓰게 되면 contains를 할 때 검색이 제대로 되지 않는 걸 볼 수 있다. 왜 그럴까? 이유는 배열의 경우 Hashcode를 비교하고, 리스트의 경우 Wrapper된 Integer값을 비교하기 때문. HashSet int 배열의 hashcode를 비교 HashSet Integer List의 Wrapper객체(Integer)를 비교 따라서, 좌표와 같은 수열의 집합을 만든다고 하면 HashSet 안에 ArrayList로 넣는 것이 좋다. [ 참고 ] https://stackoverflow.com/questions/654546..

[시스템 소프트웨어] 리눅스의 기본 명령어

보호되어 있는 글입니다.

[시스템 소프트웨어] AWS로 리눅스 서버 세팅하기

보호되어 있는 글입니다.