아
블로그 좀더 일찍 시작했으면 그 동안 공부했던 내용들을 좀더 편하게 찾아봤을 텐데.. 하는 생각
지금 정리하면서 고통받을일이 없었을텐데.. 하는 생각..
물론 지금 하고 있는 django도 제때 올리고 있지 못함 ㅋㅋㅋ
| LeetCode Contest 참여 후기 - 팁들, BOJ 기준 난이도/ 문제 유형 (0) | 2023.02.12 |
|---|---|
| 스마트폰으로 문제 풀기 (0) | 2023.02.04 |
| 알고리즘 공부하기 싫어서 웹 시작합니다. (1) | 2016.10.19 |
| 한동안 공부하느라 너무 힘들어서... (0) | 2016.10.12 |
| 블로그 새로 만들었습니다. (0) | 2016.06.09 |
연산자 오버로딩
연산자 오버로딩이란 내가 만든 사용자 정의 타입(class나 struct)에 관한 연산자를 정의하여 좀더 편하게 사용할 수 있게 만든 C++의 문법적 기능의 말한다.
문법
1 2 3 4 | [리턴형] operator[연산자]( [연산 인자] ) { //연산하는데 들어가는 로직 } | cs |
example 1)
1 2 3 4 5 6 | struct point { int x, y; }; bool operator==(point a, point b) { return a.x == b.x && a.y == b.y; } | cs |
example 2)
1 2 3 4 5 6 7 | struct point { int x, y; bool operator==(point b) { return x == b.x && y == b.y; } }; | cs |
단항 연산자 오버로딩과 이항 연산자 오버로딩
이 두가지 분류는 항의 갯수에 따라 단항 연산자 오버로딩인지, 다항 연산자 오버로딩인지가 정해진다. 오버로딩할 연산자의 항의 개수는 각각의 연산자들의 원래 항의 개수와 정확히 일치한다. 예를들어 /연산은 이항연산자 이므로 이항 연산자 오버로딩 해야하고 !는 단항 연산자 이므로 단항 연산자 오버로딩을 해야한다.
이것 이외에도 아주 특이한 친구들이 몇몇 존재하는데 바로 ++나 --이다. 이 두가지 연산자를 오버로딩하는 방법에 관해서는 구글링 해보도록 하자. 현재 포스팅에서 다루기에는 너무 세세하게 들어간 것 같다.
단항 연산자와 이항 연산자를 오버로딩한 모습은 아래와 같은데 -의 경우 단항연산자로도 쓰이고 이항 연산자로도 쓰이므로 좋은 예가 될 것 같아서 아래와 같이 오버로딩 해봤다. (23번째줄에서 사용) (생성자 만들기 귀찮아...)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <cstdio> using namespace std; struct point{ int x,y; }; point operator-(point p1){ point ret; ret.x = -p1.x; ret.y = -p1.y; return ret; } point operator-(point p1,point p2){ point ret; ret.x = p1.x - p2.x; ret.y = p1.y - p2.y; return ret; } int main() { point p1, p2; p1.x = 10, p1.y = 20; p2.x = 5, p2.y = 5; point p_one = -p1, p_two = p1-p2 ; printf("%d %d\n%d %d",p_one.x, p_one.y,p_two.x, p_two.y); return 0; } | cs |
output
- 10 - 20
5 15
위의 23번째 줄은 다음과 동치이다. operator-를 일반 함수명이라고 생각한다면 더 이해하기 쉬울 것이다.
1 | point p_one = operator-(p1), p_two = operator-(p1,p2); | cs |
구조체나 클래스의 연산자 오버로딩과 전역 함수의 오버로딩
일반적으로 전역 함수의 오버로딩은 단항 연산자의 경우 인자를 하나, 이항 연산자의 경우 인자를 두개 받는다. 이런 형태를 띄는게 전역 함수의 오버로딩인데 그 대표적인 예가 바로 위에서 보여준 예이다. 그렇다면 구조체나 클래스 안에서 구현한 연산자 오버로딩은 어떻게 다를까?
구조체나 클래스 안에서의 연산자 오버로딩의 경우 첫 번째 인자가 구조체나 클래스 인스턴스를 가르킨다고 생각하면 쉽다. 예제로 이해해 보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> #include <cstdio> struct point{ int x,y; point operator-(){ point ret; ret.x = -x; ret.y = -y; return ret; } point operator-(point p2){ point ret; ret.x = x - p2.x; ret.y = y - p2.y; return ret; } }; int main() { point p1, p2; p1.x = 10, p1.y = 20; p2.x = 5, p2.y = 5; point p_one = -p1, p_two = p1-p2 ; printf("%d %d\n%d %d",p_one.x, p_one.y,p_two.x, p_two.y); return 0; } | cs |
output
- 10 - 20
5 15
1 | point p_one = p1.operator-(), p_two = p1.operator-(p2); | cs |
구조체나 클래스에 종속적인 배열 인덱스 연산자 오버로딩과 대입 연산자 오버로딩
이 부분은 현재 시점에서 다루기 적절치 않은 부분이므로 개인적으로 공부하도록 합시다 ^ㅇ^
메모리 관리나 레퍼런스 같은 복잡한 것들이 얽혀 있습니다. 실제로 C++의 라이브러리를 구현한다던가 하는 큰 규모의 프로젝트에서 사용될 법한 내용들은 처음 하시는 분들을 위해서 생략하도록 하겠습니다. 이런게 있구나 하고 넘어가시기 바랍니다.
| Python으로 알고리즘 문제 쉽게 풀기 (1) - input 받기 잡기술 (0) | 2021.04.01 |
|---|---|
| 문제 만들기 TestCaseGenerator와 output 만들기 (0) | 2017.08.06 |
| [JAVA] java로 빠른속도로 입력받기, 출력하기 (0) | 2017.07.30 |
| C에서 C++로 넘어가기 - 시작 (0) | 2016.11.21 |
| 알고리즘 사이트 별 장/단점 총정리 (0) | 2016.10.19 |
C++은 그 기본부터 C에서 온 친구로서 사실상 C에서 사용할 수 있는 것들은 대부분 C++에서도 사용 할 수 있다. 오히려 C에서 불편하던 여러가지를 개선 시킨 것이 C++이라 할 수 있는데 이 때문에 C에서 불편하던 것들이 무엇인지 안다면 C++로 넘어가면서 어떤 방식으로 개선되었는지를 직관적으로 이해하기 쉽다.
이번 포스팅에서는 C에서 C++로 넘어가는 와중에 필요한 지식을 간단히 설명하려 한다.
여러분들이 C에 대해 대부분의 내용을 이해했다고 가정하고 설명하도록 할 것이기 때문에 C에 대한 내용은 언급만 하고 넘어갈 예정이다.
1. namespace
namespace란? 이름 공간. 함수, 변수, 클래스등의 하나로 묶어서 접근을 특정 이름만으로 할 수 있도록 제한하는 키워드
C에서 사용하는 여러 라이브러리의 속을 한번 뜯어봤다면 봤을 만한 함수나 변수명이 있을 것이다. __로 시작하는 이름들이 그것인데 이런 방식으로 사용하는 근본적인 이유는 함수명이나 변수명의 중복을 피하기 위해서다. (일종의 약속이라고 보면 된다.)
이런 것들은 C의 태생적 한계 때문이기도 한데 함수의 경우 그 이름을 전역으로 밖에 선언하지 못하고 따라서 여러 라이브러리를 사용할 경우 이름이 겹치는 위험이 발생할 수 있기 때문이다. 이를 방지하기 위해 C에서는 static 키워드를 제공하는데 (특정 파일 안에서만 접근 가능 ) 이것으로는 부족한 것이 현실이다.
이를 해결하기 위한 좋은 방법으로 C++에서 제공하는 namespace기능을 이용할 수 있다. 이 기능을 사용하면 변수명이나 함수명이 겹치더라도 잘 처리할 수 있다.
이 namespace라는 것을 사용하는 방법은 아래와 같다.
일반적으로 C++로 프로그램을 짤 때 많이 사용하는 STL(Standard Template Library)은 모두 std라는 namespace에 묶여있으며 이 안에는 최대 값을 구해주는 함수가 있다. 이 함수는 STL library중에서도 algorithm 헤더파일에 들어 있는데 이를 사용하는 모습은 아래와 같다.
|
1
2
3
4
5
6
|
#include <stdio.h>
#include <algorithm>
int main(void){
int max = std::max(10,20);
printf("%d",max);
}
|
cs |
2. struct, class
struct, class란? 여러 자료형을 한곳에 묶어 관리하기 위한 하나의 '구조'로 필요에 따라 접근을 제한 하고, 해당하는 자료를 처리하기 위한 루틴을 거치도록 만들 수 있다.
일반적으로 struct는 data에 관한 자료를 다루기 위해 사용하며, class는 그 외의 다양한 자료를 다루기 위해 사용한다. (ADT 같은 것들)
C에서도 struct라는 키워드가 있다. 이는 C언어에서 제공하는 아주 강력한 기능으로 그 쓰임세는 정말 다양하여 모두 나열할 수는 없을 것이다. 하지만 그 대부분의 쓰임세는 struct의 특징인 여러 자료형을 한 곳에 묶어 (의미적으로, 공간적으로) 관리하기 편하게 만들었다는 점에서 기인한다. 하지만 C의 이런 방식은 한계가 존재하는데 바로 누구나 해당 자료형의 데이터에 접근하고 수정할 권한이 있다는 것이다.
ADT의 예를 들어보자. ADT에는 추상화라는 개념이 있다. '추상화'란 사용자가 그 내부의 복잡한 구현을 알 필요없이 그 기능들을 가져다 쓰게 함으로 써 실질적으로 필요로 하는 것을 구현하고 설계하는데 집중 하게하는 것이다. C에서 이를 쉽게 구현하는 법은 구조체에 담아 관리하고 이 구조체를 다루는 함수를 제공하는 방식인데 이 방식에는 약간의 문제가 있다.
그 문제는 접근을 제한할 수 없기 때문에 발생하는데 대표적으로 struct의 field에 사용자가 접근하여 값을 바꾸는 것이다.
ADT의 가장 대표적인 예인 double linked list를 예로 들어보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <stdio.h>
struct linked_node {
int data;
struct linked_node * prev, * next;
};
struct linked_list {
int size;
struct linked_node * front, * back;
};
bool linked_empty(struct linked_list * list){
return list->size == 0;
}
int main(void){
struct linked_list list;
linked_init(&list);
list.size = 1000;
if(linked_empty(&list)){
printf("empty");
}else printf("not empty");
}
|
cs |
위 코드의 linked_empty()라는 함수는 해당 리스트가 비어있다면 true를 비어있지 않다면 false를 리턴하는 C 코드이다. 만약 이 때 어떤 사용자가 main 처럼 마음대로 접근을 해버렸다고 해 버리자.
그렇다면 이 ADT는 원래의 역할을 제대로 다하지 못할 것이다.
이 처럼 특정 데이터에 접근하는 것을 제한할 필요성이 있는데 이를 C++에서는 접근제어자로 해결할 수 있다. 접근 제어자는 크게 3가지 종류가 있는데 아래와 같다.
위 키워드들은 아래와 같이 사용할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <stdio.h>
struct linked_list {
private :
int size;
struct linked_node {
int data;
struct linked_node * prev, * next;
} * front, * back;
public :
linked_list() {
size = 0;
front = back = (linked_node *)0;
}
bool empty(){
return size == 0;
}
};
int main(void){
linked_list list;
list.size = 1000; //에러
if(list.empty()){
printf("empty");
}else printf("not empty");
}
|
cs |
13~16은 생성자라는 친구로 C에서는 없는 개념이다. linked_init에 해당하는 친구다.
24번째 줄에서 에러가 나는 것을 확인 할 수 있는데 private로 접근이 제한되었기 때문이다. 이렇게 잘못된 코드를 런타임 에러나 잘못된 동작이 아니라 컴파일 에러로 찾아 낼 수 있다는 것은 더 안전한 프로그램을 개발 할 수 있게 만들어준다.
상속이나 생성자, 소멸자에 관한 내용은 다음번에 다시 다루기로 하겠다. (지금은 필요 없음 ㅎ)
c++에서 struct와 class는 큰 차이가 없는데 이는 c++이 객체지향적이기도하고 절차지향적이기도 한 과도기적 언어이기 때문이다. 다른 언어의 경우 이 두 키워드를 차이를 둬서 다루게 된다.
c++에서 두 키워드의 유일한 차이
더 자세한 내용은 다음에 다루도록 하겠다.
3. template
template란? template이란 단어 그 자체의 이름 그대로 형틀이다. 특정한 형틀을 가지고 자료형,함수등 새로운 것들을 찍어내는 것이라고 보면 된다. input으로 자료형을 넣으면 새로운 자료형, 함수, 클래스 등을 찍어 낼 수 있다.
template은 기존의 C언어에서 대응되는 개념이 거의 없는데 비슷한 것을 꼽아보라면 void *형이라고 보면 될 듯 싶다. 이는 void *보다 더 많은 정보를 담고 있는 친구이다.
여러분은 C언어의 stdlib.h에 존재하는 qsort라는 함수를 사용한 경험이 있을 것이다. 이 함수는 quick sort를 구현해 놓은 친구로 어떤 배열형이든 받아 정렬해주는 함수이다. 이 함수의 원형은 다음과 같다.
|
1
2
|
void qsort (void *base, size_t num, size_t size,
int (*compare)(const void *, const void *))
|
cs |
혹시 모르는 사람들을 위해서 설명하자면 어떤 배열(base)과 그 배열이 담고있는 원소의 갯수(num), 그리고 원소 하나의 바이트수(size)와 각각의 배열을 어떻게 비교할지 결정하는 비교함수(compare)를 인자로 넘기면 그 배열을 quick sort로 정렬해주는 함수다.
C언어에서는 이런 임의의 배열을 표현할 방법이 없기 때문에 void *형이라는 꼼수를 사용해서 이를 구현해야 했다. 반면 C++에서는 이런 임의의 무언가를 표현할 좀더 직관적이고 안전한 방식을 제공하는데 그것이 바로 template이다.
사실 이런 template는 class부터 기본 타입, 때로는 상수도 들어갈 수 있으며 여러가지 장난질을 칠 수 있다. 이런 template으로 함수나 클래스등을 찍어 낼 수 있으며 이러한 자세한 내용에 관해서는 나중에 다루도록 하겠다.
template의 사용법은 대체로 "template이름<자료형>" 형태로 사용하게 된다. 위의 경우에는 template이름은 my_sort고 자료형들은 int나 double이 들어간 것이다. 때로는 이 <> 를 사용하지 않고도 사용할 수 있는데 이는 컴파일러가 자동으로 타입을 추론할 수 있는 경우에 한한다.
template의 자세한 구현방법에 대해서는 다음에 더 자세한 내용을 다룰 것이다.
4. STL container
STL이란? Standard Template Library의 약자로 C++에서 제공되는 표준화된 라이브러리다. 이 라이브러리는 쓰레드, 알고리즘, 특정한 ADT등 들을 다루기 위한 여러가지 모듈들을 이미 구현해놓았다.
Container란? ADT들을 실질적으로 구현해놓은 것들이다.
아마 다루고 넘어갈 것들로는 아래와 같다.
| Python으로 알고리즘 문제 쉽게 풀기 (1) - input 받기 잡기술 (0) | 2021.04.01 |
|---|---|
| 문제 만들기 TestCaseGenerator와 output 만들기 (0) | 2017.08.06 |
| [JAVA] java로 빠른속도로 입력받기, 출력하기 (0) | 2017.07.30 |
| [C++] 연산자 오버로딩 (0) | 2016.11.29 |
| 알고리즘 사이트 별 장/단점 총정리 (0) | 2016.10.19 |
H. Polynomial BOJ 11500
문제 설명 :
어떤 함수 f(k)를 아래와 같이 정의한다.
이 때 우리는 f에 관한 새로운 식 S(n)을 정의할 건데 그건 또 아래와 같다.
이럴 때 S(n)을 n에 관하여 정리해보자면 아래와 같이 정리된다.
이 때 다음을 구해서 출력하시오.
주어지는 것은 다음이다.
문제 풀이 :
사실 이런 종류의 수식을 처음 접하는 사람은 이게 대체 뭔 개소린가 싶은 느낌이 들 것이다. 정수론과 굉장히 밀접한 식인데 처음 읽었을 때 도무지 분석을 할 수가 없었다.
S(n)을 f(k)로 풀어보자면 다음과 같다.
일단,
이식을 보면 이걸 n에 관하여 정리해야 하는데, 정수론에 대해 기초 지식이 있는 사람들은 (사실 고딩때도 배운다) 거듭제곱의 합이 n에 관한 식으로 나온다는 사실을 알 수 있다.
예를들면,
요런 것들?
따라서 거듭제곱이 같은 것끼리 모아보자.
위 식을 정리하면 아래와 같이 깔끔하게 나오게 된다.
이제 필요한게 0<=t<=25 사이에 있는 모든 거듭제곱의 합의 계수들만 찾으면 답이다.
근데이게 쉽지가 않다. 이 걸 찾기 위해서는 가장 마지막에 주어진 식이 필요하다.
1부터 n까지 k제곱의 합을 앞으로 T(n,k)라 했을 때 다음과같다.
^증명보시려면 클릭하세요.
위 식을 정리하고나면 0~k-1의 거듭제곱합을 통해서 k거듭제곱합을 구할 수 있다.
따라서 0,1,2,3,4...25까지 미리 거듭제곱의 합을 구해놓고 처리하면 끝
소스코드 보기 <- 클릭
| [leetcode 834] Sum of Distances in Tree O(N) 풀이 (2) | 2023.02.04 |
|---|---|
| 2021 Code jam Round 1A 문제 풀이 (0) | 2021.04.11 |
| Asia Regional - Daejeon 2015 모든 문제 풀이 (0) | 2016.11.07 |
| BOJ 1514 자물쇠 (0) | 2016.10.17 |
문제집 : https://www.acmicpc.net/category/detail/1413
풀이는 하나하나 업데이트 될 예정입니다.
간략한 문제 분류와 솔루션만 제시 해놓고 풀이가 따로 필요하다고 생각되는 문제들은 추후 링크 하도록 하겠습니다. (요청하시면 그 부분에 관한 풀이도 올려드리겠습니다. )
flow문제 중에서도 MCMF문제다. "동전의 교환 = 코스트" 로 두고 흰색을 모두 흰색으로 옮길때의 최소 코스트로 그래프 설계를 하면 된다.(검은색을 검은색으로 옮기는 코스트로 생각해도 무방) 흰색 정점이 있는 곳을 src와 연결하고 흰색 동전이 있는 곳을 sink로 돌렸을 때 나오는 MCMF결과를 출력하면 된다.
C. Grid BOJ 11495
flow 문제 중에서도 이분 그래프로 만든 후 최대매칭하는 문제다. 익히 알려진 사실로 최대 매칭은 flow와 동치다.
각각의 그리드를 순서대로 1, 2, 3,4... 번호를 매긴 후 인접한 것 끼리 연결한다. 이때 짝수는 src에 홀수는 sink에 연결하며 각각의 캐퍼시티는 그 그리드의 값으로 하고 매칭을 찾으면 된다.
이 때 결과를 찾는 방법은 두가지 있는데 src와 sink에 남아 있는 캐퍼시티를 추적하는 방법과 전체에서 매칭의 수를 빼는 방법이 있다.(1매칭은 1코스트를 감소시켜주므로)
D. Kernel BOJ 11496
기하 문제다.(segment tree로도 풀린다고 한다.) kernel이 존재할 수 있는 구간을 결정하고 그 위치가 주어진 polygon사이에 존재하는 지 결정하는 문제다. 열심히 그려보다보면 어떤 방식으로 kernel이 존재할 수 있는 구간을 결정하는 지 알 수 있다.(솔직히 이런걸 대회중에 발견하기는 어려워 보인다..)
E. Log Jumping BOJ 11497
그리디 문제다. 통나무들을 길이 순으로 정렬하고 원의 왼쪽 오른쪽 차례대로 배치해 나가면 최적이 된다.
F. Odd Cycle BOJ 11498
그래프 문제 중에서도 SCC를 사용하여 시간을 줄이는 문제다. 사실 진짜 별거 없고 coloring하는데 그 coloring을 SCC내에서 하면 되는 문제다. 근데 한가지 조심해야할게 그냥 돌리면 WA가 날 수 있는데 사이클이 여러개 존재할 수 있다. 따라서 coloring을 back edge만 체크하게 해야한다. 이때 잘 처리 해줘야 TLE가 안난다.
기하 문제 중에서도 Convex_hull을 사용하는 문제다. 사실 그냥 컨백스 홀 만드는 방식으로 그냥 쭉 훑으면서 만들면서 최대 값을 갱신만 시켜주면된다.
그냥 수식을 정리하는 문제다. 수학적 센스가 필요한 것 같다. (이미 알고 있다면 개꿀이었을 듯...) 수식을 정리해서 그대로 대입하면 된다. (하루종일 정리하면 된다.) 거듭 제곱의 합에 관하여 정리해야 한다.
I. Stock BOJ 11501
파라매트릭 서치 문제다. 특정 상한을 결정하고 만들 수 있는지 검사한다. 이 때 검사는 선형으로 할 수 있어서 O(n) 그리고 파라매트릭에 logn이 들어 총 O(nlogn)이 든다.
J. 3-Primes Problem BOJ 11502
추측이라는데 그런가 보다 하면 된다. 그냥 하라는데로 하면 되는데 1000밖에 안된다. 따라서 소수 a,b를 결정하면 자동으로c가 결정된다. 여러가지 방법이 있는데, 전수 검사를 해서 (a,b,결정하고 c가 소수인지 확인) 푸는 방법, 넵섹하는 법, 등등 있다.
K. Tree Edit BOJ 11503
트리 dp문제다. 아직 안풀었다.
L. Wheel of Numbers BOJ 11504
시뮬레이션 문제다. 직접 다해보면 된다.
| [leetcode 834] Sum of Distances in Tree O(N) 풀이 (2) | 2023.02.04 |
|---|---|
| 2021 Code jam Round 1A 문제 풀이 (0) | 2021.04.11 |
| Asia Regional - Daejeon 2015 H. Polynomial 솔루션 (0) | 2016.11.08 |
| BOJ 1514 자물쇠 (0) | 2016.10.17 |
갑자기 새로운 친구가 프로젝트에 합류해서 해당 AWS서버를 공유해줘야 하는 상황이다.
새로운 계정을 파서 그 계정으로 접속하게 하고 싶었는데 알다시피 AWS linux에 접속하려면 공개키로 접속하는 형식이다. aws는 암호가 없이 private키를 소유하고 있는 사람이 접속할 수 있는 방식이라 내 계정을 그대로 넘겨야(즉 내 private key를 공유...) 해야 했다. 실제로 저번 프로젝트의 경우에는 그런 식으로 운영을 했었다 .
근데 문득 리눅스 자체가 여러 유저가 한 컴퓨터에 접속하는게 가능한 OS인데 (multi user!) 굳이 이렇게 할 필요가 있나 싶었다.
그래서 새로운 계정을 만들어 나눠줘볼까 라는 생각을 했다. 즉 새로운 유저 계정을 만들고 그 계정에 키페어를 만든 후 그 키를 가져오는 방법!
[ubuntu ~]$ sudo adduser newaccount새로운 유저를 만든다.
[ubuntu ~]$ sudo su - newaccount새로운 계정으로 변경한다.
[newaccount ~]$ ssh-keygen -t rsassh-keygen은 keypair를 만드는 명령어다. 다음 명령어를 사용한다면 뭔가 이것저것 물어보는데 그냥 enter, enter, enter, enter 쳐보도록하자. 수행이 완료되면 .ssh라는 폴더가 생긴다.
[newaccount ~]$ ls -al쳐서 확인해보도록 하자. 이 폴더 안에는 두가지 파일이 존재하는데 id_rsa 와 id_rsa.pub이다. 여기서 id_rsa는 우리가 로그인을 하기위해 필요로 하는 private 키고 id_rsa.pub는 public key이다. AWS에는 이 퍼블릭 키의 이름이 반드시 authorized_keys라는 이름이어야한다. (이름을 안바꿔주면 정상 작동을 하지 않더라... 확인 필요 ㅠ)
[newaccount ~]$ mv .ssh/id_rsa.pub .ssh/authorized_keys이제 준비는 다 끝났다. 우리가 접속할 때 필요한 파일은 바로 id_rsa다. 외부에서 newaccount계정으로 접속하려면 이 파일이 필요하다.
방법1. 이 파일을 내 컴퓨터로 이동시켜야하는데 그냥 복붙 하시면 된다. 이 경우에는 권한을 바꿔줘야한다.
[mycomputer ~] vim myrsa
[mycomputer ~] chmod 600 myrsa
[mycomputer ~] ssh -i "myrsa" newaccount@[instance DNS]
방법2. 마찬가지로 컴퓨터로 이동시켜야 하는데 좀 더 간지가 나게 옮길 수가 있다.
[ubuntu ~] sudo mv /home/newaccount/.ssh/id_rsa /home/ubuntu
[ubuntu ~] sudo chown ubuntu:ubuntu ./id_rsa
[ubuntu ~] exit
[mycomputer ~] sudo scp -i "ubuntukey.pem" ubuntu@[instance DNS]:/home/ubuntu/id_rsa ./
[mycomputer ~] sudo ssh -i "id_rsa" newaccount@[instance DNS]
이제 이 키를 팀원에게 나눠주면된다. 개꿀 ^ㅇ^
| UNIX 명령어로 특정 파일을 제외하고 압축하기 (0) | 2021.04.03 |
|---|---|
| Linux상에서 Dual monitor workspace를 동시에 이동하기 (1) | 2021.02.18 |
요즘 개발하고 싶은 서비스가 있어서 angular.js, django, html, css, + AWS를 동시에 배우고 있다보니 정신이 하나도 없다. 사실 이렇게 벌려놓으면 수습못하는데 일단 벌렸다. 웹공부하는 친구 한명 꼬셔서 프로젝트를 진행중이다.
그 중에서 이번 프로젝트에서 서버단으로 django를 시작하기로 했다. (사실 나 혼자 정했다. 어차피 개발해야할 것, 파이썬에 익숙해지면서 하나하나 배워볼겸해서 ㅎㅎ)
아무튼 자세한 기본기보다는 순수 구현목적으로 배우고 있는 거기 때문에 자세한 원리라던가. 하는 건 포스팅 하지 않을 예정이다. 주로 공부 하면서 기본적으로 필요로하는 것, 구현에 있어서 만난 장애를 해결하는 과정등에 관해서 포스팅을 할 것 같다.
이렇게 한꺼번에 시도하는 건 별로 좋지 않다고 생각하지만 ( 내 성향하고도 잘 맞지 않다. ) 웹이란게 원래 너무 복합적이다 보니, 프로젝트를 연 이상 어쩔 수 없는 것 같다.
주변에 파이썬 장인(?)도 있기도 하고 모르면 물어보러가야지.
아 참, django에 관한 아주 기본적인 것부터 차례차례 하고 싶으신 분들은 아래 링크로 가서 시작해보도록 하자. 생각보다 프로젝 트만들고 기본적인 토대를 다시는데 필요한 건 다 있다.
참, 난 블로그를 만드는 것은 아니기 때문에 완전히 저것과 똑같이 하진 않을 듯 싶다. (아직까진 django에 대해서 무지하다 ㅠㅠ)
| 새로운 장고 글로 돌아오겠습니다. (0) | 2017.07.30 |
|---|
이사 중...
===============================================
아
하다가 멘탈 깨져서 정리함.
서픽스 어레이의 n^2logn 풀이는 아주 간단하다. 소스 코드만 정리해보자면 ...
1 2 3 4 5 6 7 8 9 10 | vector<int> getSuffixArray(const string& s){ vector<int> suffix; //suffix배열을 초기화 for (int i = 0; i < s.size(); ++i) suffix.push_back(i); //문자열을 비교( 람다함수 사용 ) sort(suffix.begin(), suffix.end(), [&s](int a, int b){ return strcmp(s.c_str() + a, s.c_str() + b) < 0; }); return suffix; // 리턴 } | cs |
아아아아아주 쉽다. 오히려 람다함수가 더 어려운듯...
방식자체는 설명하자면 n개의 문자열을 죄다 때려박은 후
(메모리를 적게 사용하기 위해서 인덱스만 때려박음 : 4번째 줄)
그 해당 문자열을 정렬한다. 근데 정렬하는데 드는 비용이 nlogn이고 하나의 문자열을 비교하는 비용이 n이므로 n^2logn이다.
굉장히 못써먹을 시간복잡도라고 생각할 수 있지만 사실 문자열을 비교하는데 일반적인 경우, 항상 n이 걸리지는 않기 때문에 그럭저럭 쓸만하다.
... 인풋이 aaaaaaaaaaaaaaaaaaaa... 만 아니라면...
이것보다 좋은 알고리즘으로는 맨버-마이어스의 알고리즘이 있다.
이 알고리즘의 시간복잡도는 n * log n * log n n을 로그로 떨군건데
난 멍청해서 이걸 이해하는데 엄청 오래걸렸다.
내가 구글링을 잘 못하는 걸 수도 있는데 제대로 정리된 블로그가 없어... 그래서 정리함.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | std::vector<int> getSuffixArray(const string& s) { int n = s.size(); //idx + t 까지 비교한다! int t = 1; //group[i]는 t까지 비교했을 때 i의 그룹 번호 vector<int> group(n + 1); //t==0일때를 대신한 거라고 봐도 무방... for (int i = 0; i < n; ++i) group[i] = s[i]; group[n] = -1; //서픽스를 담을 배열 vector<int> suffix(n); //서픽스를 초기화 for (int i = 0; i < n; ++i) suffix[i] = i; while (t < n) { //비교함수 아주 중요함 auto cmp = [&group, t](int a, int b){ if (group[a] != group[b]) return group[a] < group[b]; return group[a + t] < group[b + t]; }; //정렬 std::sort(suffix.begin(), suffix.end(), cmp); t *= 2; //t가 n보다 크거나 같으면 종료 if (t >= n) break; //그룹 재지정 vector<int> newGroup(n + 1); newGroup[n] = -1; newGroup[suffix[0]] = 0; for (int i = 1; i < n; ++i){ if (cmp(suffix[i - 1], suffix[i])){ newGroup[suffix[i]] = newGroup[suffix[i - 1]] + 1; }else newGroup[suffix[i]] = newGroup[suffix[i - 1]]; } group = newGroup; } return suffix; } | cs |
람다함수 [&group,t] <= group은 레퍼런스로 참조하고 t는 값을 복사해서 사용한다.
나름대로 정리하자면
s ? 구하려는 서픽스 배열의 target 스트링
group[i] ? i번째 접미사가 가지는 그룹 번호(index순)
suffix[i] ? t까지 봤을때 i번째 접미사(사전 순)
t상태일때 어디까지 정렬되냐면 글자수가 2t일때까지 정렬된다.(즉 1일때는 글자수가 2개까지 정렬)
근데 이 그룹이라는 놈이 엄청나게 많은 것을 함축 하고 있는데
group[a]는 사실 string의 [a...a+t)까지 비교한 결과의 상대 값이 저장되어 있다고 보면 된다.
이걸 이해하는데 이틀걸림.
22~ 26줄의 compare함수를 보자.
case : group[a] != group[b]
group[a]와 group[b]가 다를 때 group[a] < group[b]를 리턴한다.
현재 t상태일때 벌써부터 group값이 다르다는 것은 이미 비교가 끝나있다는 것이다.
그러니 a+t번째는 비교해볼 가치도 없음.
case : group[a]와 group[b]가 같다.
string의 [a...a+t) [b...b+t)의 비교결과가 같다는 것이다.
그럼이제 이걸 신경 쓸 필요가 없지.
[a+t...a+2t)와 [b+t...b+2t) 만 비교하면 된다.
근데 이걸 일일이 다 비교하면 시간복잡도가 어마어마하게 증가한다.
비교 할때마다 t만큼 추가 시간이 걸리니 말이다.
그리고 다행스럽게도 이 결과는 이미 저장되어 있다.
어디에?
group[a+t]와 group[b+t]에!
그렇기 때문에 group[a+t]와 group[b+t]를 비교한 값을 리턴해주면 된다.
이 비교함수로 정렬이 완료되었으면 이제 이 결과를 다시 그룹에 반영해줘야 하는데
이부분이 37~46줄이다.
그룹의 값은 상대값이기 때문에 suffix의 첫번째 값은 0으로 설정하도록 하자.
이제부터 suffix[n-1]까지 갱신해주는데 비교했는데
이 비교의 기준은 이전 group과 t이다.(아직 갱신되기 전)
(실수로 t를 값이아니라 레퍼런스로 참조해봤는데 재밌는 일이 일어났다 ㅎㅎ)
case : suffix[i-1]과 suffix[i]를 비교
비교값이 더크데! <- 당연히 더 커야지 비교한 결과가...
즉 이미 비교가 완료된 항목임.
그러니까 상대값도 1증가시켜줌.
case : 현재까지 문자열을 사전순으로 비교할 수 없다.
suffix배열은 t까지 진행했을때 정렬되어 있어야한다.
즉 이부분은 아직 정렬이 제대로 이뤄지지 않았다는 것이고
따라서 아직까지는 suffix[i]와 suffix[i-1]은 누가더 사전순으로 우선인지 알 수 없다.
즉 suffix[i]와 suffix[i-1]은 길이가 2t일때까지 같았다는 것
그룹번호를 같게 유지해서 다음 시퀀스에 비교할 수 있게 해두자.
(서픽스 어레이의 특성상 모든 문자열의 길이가 다르기때문에 같은건 존재할수없다.)
다른사람이 이해가 됐을지 모르겠다.
내가 나중에 봤을때 이해할 수 있을 정도로만 정리해둔거라...
틀린부분 있다면 지적부탁드려용.
참고 : 알고리즘 문제해결 전략 2권 suffix array파트 참조
p.s. suffix array관한 풀이는 최대 n까지 줄일 수 있고 이것보다 쉬운 nlogn풀이도 존재합니다.
p.s.2 그니까 저건 나중에 공부해서 포스팅할게요. 이거하는데도 지침 + sa와 한쌍인 lcp알고리즘도 다음에... 저가 너무 멍청해서
======================================================
이전 블로그에 있던 글 옮겨왔습니다. ㅎ
| nCr mod p 구하기 (2) | 2018.04.26 |
|---|---|
| 거듭 제곱의 합 (2) | 2016.10.22 |
링크드리스트에 관한 포스팅에 들어가기전에 대부분의 자료구조에서 사용되는 자기참조구조체에 관해서 알아보도록 하자.
자기참조구초제(Self-referential structure)는 링크드리스트 뿐만 아니라 여러 자료구조에서(이를테면 그래프의 표현이나, 트리등의 자료구조를 작성할 때) 사용한다.
아주 중요한 개념이라고 할 수 있는데 실질적으로 작성해보면 어렵지 않다.
자기참조구조체를 사용하는 자료구조에서는 대부분 하나의 데이터 단위를 자기참조구조체로 관리하게 되는데 기본적으로 자기가 관리하는 데이터 정보와 자신의 타입의 레퍼런스를 가지고 있다. 모양을 보면 다음과 같다.
1 2 3 4 5 | struct [struct_name] { [datatype] datatype_name; [struct_name *] pointer_name; }; | cs |
여기서 이런 공부를 처음 시작하는 사람들이 자주 혼동하는 개념이 있다.
이게 다 이름을 저 모양으로 지어놔서 그렇다. ㅡㅡ..
자기참조구조체면 마치 나 스스로를 참조할 것 같아 보이지만 참조의 대상이 나라는 구조체가 아니라 나와 같은 타입이다. 즉, 나와 같은 타입의 다른 구조체를 가르킨다고 보면 된다.( 물론 구현에 따라 자기 스스로를 가르킬... 수도 있다.)
여기서 자기참조구조체는 참조하는 대상이 한개일 수도 있지만 여러개일 수 있다. 이것도 어떤 자료구조를 구현할지에 따라서 달라진다. 예를들면 double linked list 를 구현하게 될경우 레퍼런스를 두개 사용해야하고, 자식의 갯수가 n개인 n-진트리를 작성하게 될 경우 레퍼런스가 n개가 될 것이다.
double linked list의 자기참조 구조체를 잠깐 살펴보면 아래와 같다.
1 2 3 4 5 | struct linked_node { int value; struct linked_node * prev; struct linked_node * next; }; | cs |
서론이 너무 길었던 것 같다. 다음번 포스트는 정말로 링크드리스트에 관하여 다루겠다.
| 자료구조 포스팅에 앞서서... (0) | 2016.10.12 |
|---|---|
| 자료구조 연재 시작 (0) | 2016.10.12 |
웹 쪽을 시작하기 앞서서 일단 웹! 하면 서버!기때문에
AWS를 준비하도록 한다.
사실 AWS는 꽤 자주 사용해 봤는데 제대로 사용하는 법은 잘 모른다.
매번할때마다 까먹고 다시 구글링해서 보고...
그래서 준비하는 AWS준비하기
일단 AWS에 들어가서 가입한다. 대충 로그인 하려고 하면 아래와 같은 창이 뜨는데
계정 만드는 부분은 스크린샷을 안찍어둬서...
걍 하면된다. 새사용자로 클릭,클릭,클릭, 하고 넘어가다가 신용카드나 체크카드를 요구한다.
돈을 뜯어가겠다는 건데 등록을 안하면 EC2(인스턴스를 관리하는 곳)을 열어주지 않는다.
따라서 무조건 등록해줘야한다.
카드를 처음 결제하는 사람일 경우에는 이 부분에서 막힐수가 있는데(이게 뭔소리지... 하는)
credit card number는 체크카드 앞면의 xxxx xxxx xxxx xxxx 하고 나와있는 것들을 의미하고
날짜는 그 밑에 xx/xx라고 나와있는 게있는데 그걸 순서대로 넣어주면 된다.
이름은 아마 선택사항이었던 것 같다.
그리고 그렇게 1달러가 들게 됩니다.
아무튼 이렇게 AWS를 가입하고 나면 이제 EC2에 입장할 수 있는데
아래와 같은 화면을 볼 수 있다.
빨간색 동그라미 위치에서 위치를 변경할 수 있고 (서울, 도쿄 등등 있다.)
파란색 동그라미로 이제 우리가 원하는 인스턴스를 만들 수 있다.
인스턴스란 복잡하게 생각할 필요는 없고 그냥 간단하게 컴퓨터를 만든다고 생각하면 된다.
인스턴스를 누르면 아래와 같은 창이 뜬다.
OS나 기타등등을 선택하고 추가 옵션을 뭐넣을건지, 스토리지는 얼마나 쓸 건지 등 결정할 수 있다.
잘모르겠으면 그냥 우분투 선택하고 런치 시키면된다. 연습 단계에서는 하등 상관 없을 것 같다.
이 대 뭐시기 key를 발급 받을 꺼냐고 물어보는데 간단히 말하자면 그야말로 열쇠다.
여러분이 만든 key를 통해서 인스턴스에 접속 할 수 있고 따라서 key관리를 잘 해야한다.
이미 존재하는 키가 없다면 새로운 키를 발급받으라고 나오는데
역시 이름짓고 하라는데로 하면 키를 생성하고 인스턴트를 실행할 수 있을 것이다.
그 후에 이제 우측 중간에 있는 메뉴 중에서 instances를 선택해 보자.
하나가 생성되어 있을 것이고 기본셋팅중이 들어올 것이다.
이때의 instance state가 노란불이 들어와 있을 것이다.
이 불이 녹색으로 변경되면 ssh 나 putty 를 통해서 간단히 접속할 수 있다.
| 공짜로 서비스 배포하기 Lambda로 서비스 배포하기 (1) (0) | 2023.02.05 |
|---|---|
| aws IAM (0) | 2017.08.17 |
| aws 시작하기 (0) | 2017.08.17 |
| aws에서 결제 알람 받기 (0) | 2017.01.23 |
