위처럼 작은 상자들이 저마다 무게와 가치를 가지고 있을 때,

15Kg 등 가방의 무게수납제한 하에서 어떤 박스들을 선택해서 가방에 넣어야 가장 많은 돈이 될까?

라는 형식의 문제를 냅색 문제라고 한다.

 

이때 같은 상자를 중복해서 여러 번 넣을 수 있으면 unbounded knapsack problem(UKP)라고 하고,

단 한번씩만 넣을 수 있으면 0-1 knapsack problem이라고 한다. 

(위 두가지 버전 사이에 K번 넣을 수 있는 버전으로 bounded knapsack problem도 있긴 함)

 

아래는 관련 문제 리스트

https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 

 

문제 - 1 페이지

 

www.acmicpc.net

 

 

0-1 냅색

일반적으로는 0-1 냅색 버전이 가장 흔하다.

 

이문제는 NP완전에 해당하는 문제로 브루프포스로 모든 경우의 수를 해보는 것 이외에 더 효율적인 방법은 없는 것으로 알려져 있다.

모든 경우의 수를 해보려면 상자의 개수가 n개일 때 $O(2^n)$의 복잡도를 가진다(0-1 냅색의 경우)

 

n의 개수가 대략 20 이하일 때는 브루트 포스로 풀수 있다. 이 문제를 통해 체크해보자.

내 브루트포스 답안은 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
 
int32_t main()
{
    int N; scanf("%d", &N);  // 사람수 <=20
    int L[21] = {}; REP(i, N)scanf("%d", L + i);  // 체력 <= 100
    int J[21] = {}; REP(i, N)scanf("%d", J + i);  // 기쁨 <= 100
    int ans = 0;
    for (int i = 0; i < (1 << N); i++) {
        int jsum = 0;
        int lsum = 0;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) jsum += J[j], lsum += L[j];
        }
        if (lsum < 100) ans = max(ans, jsum);
    }
    printf("%d\n", ans);
    return 0;
}
 
 cs

 

n의 개수가 20을 넘어갈 때는 DP로 푸는 게 기본이고, 이 문제가 기본에 해당한다고 볼 수 있다.

아래 영상에서 다루었다.

https://youtu.be/frlRE7 bRIDo

내 경우, 위 풀이에도 나와있지만, 대체로 iterative DP보다 recursive DP(DFS + memoization)가 훨씬 생각하기 수월한 경우가 많았다.

 

UKP

상자를 반복해서 사용 가능할 경우 UKP문제가 된다. 이 문제가 기본에 해당한다고 볼 수 있다.

 

이 문제는 recursive DP로는 시간 초과가 났고, iterative DP 버전도 배열 크기 줄이기 신공을 써야 통과했다.

 

경우에 따라 UKP문제를 0-1 냅색으로 변환해서 시간 복잡도를 낮출 수 있다. 이 문제를 참조하자.

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

너비 우선 탐색(Breadth-first search, BFS)  (0) 2020.03.19
백트래킹(back tracking)  (0) 2020.03.09
이진탐색/이분탐색 (Binary Search) 알고리즘  (0) 2019.12.09
소수(prime)  (0) 2019.03.30
약수 출력하기  (0) 2019.03.24

행렬은 알고리즘 문제를 풀 때도 그렇고, 3D 코딩을 할때도 필요하고 여러모로 쓸 경우가 많은것 같아 여기 정리합니다.


먼저 나이브한 행렬곱셈을 구현해보면 다음과 같습니다. (관련 문제: 백준 2740번 행렬곱셈)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll A[101][101], B[101][101], C[101][101];
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%lld", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%lld", &B[y][x]);
 
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            for (int i = 0; i < m; i++) 
                C[y][x] += A[y][i] * B[i][x];
            
            printf("%lld ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs


특별할건 없고, 2차원 배열로 잡고 y, x (또는 행, 열 이라고도 표현 가능) 순으로 인덱스 할당해서 계산한다는 것..


근데 한가지 불편한점이 발견되는것은 곱셈결과를 리턴하도록 함수로 뺄 경우에 행렬을 리턴값으로 두기 까다롭다는 것이다 (2차원 배열이니까.. 한가지 work around는 걍 out-value 파라미터를 사용하는것.. 하지만 그렇더라도 리턴값처럼 복사기반이 아니기 때문에 값의 정합성(오버라이팅 된다거나..)에 대해 항상 고민해야한다.) 

따라서 자연스럽게 2차원배열 그 자체로 쓰는것보다 struct나 class로 빼는걸 생각하게 되는데.. 대입연산자나 생성자, 소멸자, 멤버함수등 생각할게 많아지고 코드의 단순함이 많이 훼손(?)된다.


vector의 vector를 사용하면 위의 리턴문제를 비교적 간단하게 해결할 수 있다. 아래 코드를 보자.

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
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix mul(matrix A, matrix B)
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%d", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%d", &B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = mul(A, B);
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs



연산자 오버로딩을 사용하면 mul 함수대신 * 기호를 사용할수도 있다. 다음을 보자.

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
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix operator * (matrix A, matrix B) 
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%d", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%d", &B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = A * B;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs


반응형
저작자표시

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18
백준 제출시 오류유형 정리  (0) 2019.03.18

https://www.acmicpc.net/problem/4949

이 문제 처럼 여러줄의 문장을 입력으로 받는 경우를 생각해보자.


나이브하게 생각하면 아래처럼 하면 될 것 같지만..

1
2
3
4
5
    char line[100];
    while(1){
        scanf("%s", line);
        if(strcmp(line, ".")==0) break;
    }
cs


막상해보면 공백이나 줄바꿈 단위로 끊어져서 단어 단위로 들어옴을 알 수 있다. (더군다나 공백이나 줄바꿈 정보는 소실된다)

만약 원하는게 단어단위로 끊어서 처리하는거라면 이렇게 처리해도 상관은 없다. 


하지만 이 문제의 경우처럼 줄바꿈 정보가 필요한 경우는 다른 방법이 필요하다.


1
2
3
4
5
6
    char line[100];
    while(1){
        gets(line);
        if(strcmp(line, ".")==0) break;
    }
 
cs

그런경우 이런식으로 scanf 대신 gets를 쓰면 줄단위로 받는게 가능하다.

근데 황당하게도 C++14부터는 gets를 지원하지 않는다. ㄷ ㄷ ㄷ

따라서 이함수를 쓰려면 컴파일러를 C로 두거나 C++11이하로 두어야 한다.

또한가지 번거로움이 있는데 visual studio 2017에서는 gets를 지원하지 않아서 gets_s로 바꿔야 한다 ㅠ(근데 또 이대로 제출하면 안됨)


fgets(line, sizeof(line), stdin);  이거는 visual studio, gcc 둘다되는것 같다.


scanf("%[^\n]", str); 신기하게도 이것도 된다.
scanf("%99[^\n]", str); 좀더 safe하게 하려면 이렇게 100-1 숫자를 앞에 적어주면 된다. 1은 \n용


반응형
저작자표시

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
백준 팁모음  (0) 2019.03.18
백준 제출시 오류유형 정리  (0) 2019.03.18

이진탐색의 과정

 

여기보면 알기쉽게 설명돼 있다.

 

 

1. STL사용버전

binary_search() 사용

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[10]= { 0, 1, 3, 3, 3, 4, 6, 9, 10, 11 };
    sort(arr, arr + 10);
    int size = 10;
    int to_find = 9;
    cout << binary_search(arr, arr + size, to_find) << endl;
    return 0;
}
 cs

binary_search()대신 lower_bound()를 사용하면 더 유연하다.

binary_search()는 존재여부만 리턴해서 있으면 1 없으면 0을 리턴하는데, 

lower_bound는 iterator를 리턴해서 위치나 값까지 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[10] = { 0, 1, 3, 3, 3, 4, 6, 9, 10, 11 };
    sort(arr, arr + 10);
    int size = 10;
    int to_find = 9;
    cout << (*lower_bound(arr, arr + size, to_find) == to_find ? 1 : 0) << endl;
    return 0;
}
 
 cs

 

 

2. 직접구현 - 나이브하게 시도해본 버전

아무 생각없이 의식의 흐름대로 구현하면 아래처럼 되는데

1
2
3
4
5
6
7
8
9
10
11
bool my_bsearch(int in[], int N, int find) {
       int left = 0, right = N - 1;
       while (left <= right) {
              int mid = (left + right) / 2;
              if (in[mid] == find) return true;
              if (in[mid] < find) left = mid;
              else right = mid;
       }
       return false;
}
 
 cs
left=3, right=4와 같은 상황이 됐을때 mid = 3이되고 무한루프에 빠진다 ㅠ
integer 나눗셈의 특수성에 기인한 현상으로 잡기가 생각보다 까다롭다.
 

 

이 상황을 피해보겠다고 조건문을 추가하면 아래처럼 덕지덕지가 되는 상황 ㅠ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool my_bsearch(int in[], int N, int find) {
    int left = 0, right = N - 1;
    do {
        int mid = (left + right) / 2;
        if (in[left] == find) return true;  // A
        if (in[mid] == find) return true;
        if (in[right] == find) return true; // A
        if (in[mid] < find) {
            if (left == mid) break;  // B
            left = mid;
        }
        else {
            if (right == mid) break; // B
            right = mid;
        }
 
        if (in[mid] < find) left = mid;
        else right = mid;
    } while (left < right);  // C
    return false;
}
 cs

(경계선 처리가 힘들고 주석 A, B, C 부분이 맘에 안든다)

일단 위처럼 덕지덕지가 되는 코드는 랜덤TC에 맞춰서 수정했을뿐 재활용 가치도 없고, reproduce도 불가능하다. 한마디로 쓰레기

 

3. 해당 문제점들을 개선한 버전

덕지덕지 조건문 붙이는게 싫으면 다음처럼 log연산이라 1000번이면 충분하고도 남는다는 점을 활용해서 T를 추가하고,

1000번이상이면 break시킨다음 left랑 right인덱스도 살펴보는 방법이 있다

(A, B부분)

1
2
3
4
5
6
7
8
9
10
11
12
bool my_bsearch(int in[], int N, int find) {
       int left = 0, right = N - 1;
       int T = 1000;  // A
       while (left <= right && T--) {  // A
              int mid = (left + right) / 2;
              if (in[mid] == find) return true;
              if (in[mid] < find) left = mid;
              else right = mid;
       }
       if (in[left] == find || in[right] == find) return true;  // B
       return false;
}
 cs

이정도만 해도 실전에서는 구현해볼만한 난이도가 된다.

 

그러나 면접용으로 코딩을 준비중이라면, 위의 T로 루프탈출을 하는것보다 아래버전을 외워두는게 좋다.

1
2
3
4
5
6
7
8
9
10
bool my_bsearch(int in[], int N, int find) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (in[mid] == find) return true;
        if (in[mid] < find) left = mid+1;
        else right = mid-1;
    }
    return false;
}
 cs

초기 버전에서 mid+1, mid-1 부분만 +1, -1 가미해준 식으로 바뀐거라 뭐그리 외우기 어렵지도 전혀않다.

위 함수에서 return 부분만 살짝 바꿔주면 lower_bound랑 비슷한 기능을 하도록 수정할 수 있다.

(c++에서는 그냥 lower_bound쓰면 되지만, java에서는 지원하지 않으니 필요할수도..)

int my_lower_bound(int in[], int N, int find) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (in[mid] == find) return mid;
        if (in[mid] < find) left = mid+1;
        else right = mid-1;
    }
    return left;
}

 

결론

꼭 필요한 경우가 아니면 STL쓰는게 좋고, 직접구현은 에러발생하기가 너무나 쉽다.

T로 루프탈출하는 버전을 쓰거나, 젤 아래버전을 외워두자.

 

반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

백트래킹(back tracking)  (0) 2020.03.09
냅색DP(knapsack DP)  (0) 2020.03.07
소수(prime)  (0) 2019.03.30
약수 출력하기  (0) 2019.03.24
우선순위 큐(priority queue)  (0) 2019.03.24

git log -p 하면 기본적인 최근 diff화면을 보여준다.


git log -p -2 처럼 -2를 추가하면 최근 2개만 보여줌


git log --graph 하면 왼쪽에 트리그래프 나오면서 merge 상황등을 체크할 수 있음


git log --graph --oneline 하면 commit 하나당 한줄로 표시되어 그래프 merge상황 체크가 좀 더 쉬워짐

반응형
저작자표시

'Programming > Git' 카테고리의 다른 글

git PR(pull request) 관련  (1) 2023.10.27
git 초기설정  (0) 2023.06.06
git 자주 쓰는 명령어 모음  (0) 2019.09.27
git branch 관련  (0) 2019.04.17
github  (0) 2018.11.07

scp란 무엇인가.. 서버간 파일복사(cp)를 할 수 있게 해주는 프로그램


기본사용방법

현재 서버에 있는 a.txt 파일을 원격서버(192.168.0.1)에 복사하기

scp a.txt wi.kim@192.168.0.1:/home/wi.kim


윈도우에서 ssh접속 서버에 있는 파일을 가져오기

pscp.exe를 사용하고 사용법은 scp와 동일

반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

supervisor  (0) 2020.03.18
ssh 자동로그인(ssh-keygen)  (0) 2020.03.10
mount관련  (0) 2019.12.05
리눅스 비밀번호 틀린 횟수 초과 대응방법  (0) 2019.10.07
crontab  (0) 2019.09.27

마운트 여부 및 location 확인하기

df -h

 

mount하기

sudo mount 192.168.0.1:/volume1/mynas /nas/mynas

앞에가 원격nas위치, 뒤에가 local 위치

-t nfs 옵션을 주는 경우가 있는데 필요한 것인지?

 

nas의 io상태 확인하기

iostat -mnh

만약 설치되어 있지 않으면 sudo yum install sysstat

 

 

반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

ssh 자동로그인(ssh-keygen)  (0) 2020.03.10
scp관련  (0) 2019.12.05
리눅스 비밀번호 틀린 횟수 초과 대응방법  (0) 2019.10.07
crontab  (0) 2019.09.27
리눅스 계정 관리  (0) 2019.09.19

계정 로그인 시도 시 패스워드 불일치로 잠겼을때


1. 계정의 틀린 패스워드 입력 횟수 확인 및 마지막 시도 시간 확인

pam_tally2 -u 계정명


2. 계정 패스워드 잠김 해제

pam_tally2 -u 계정명 --reset



출처: https://siron89.tistory.com/14 [siron89]

반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

scp관련  (0) 2019.12.05
mount관련  (0) 2019.12.05
crontab  (0) 2019.09.27
리눅스 계정 관리  (0) 2019.09.19
CentOS 7 방화벽  (0) 2017.12.04

여기보면 설명 잘 돼있다.


crontab -e 하면 내용 볼 수 있다. (에디트도 아마 가능?)


*　　　　　　*　　　　　　*　　　　　　*　　　　　　*
분(0-59)　　시간(0-23)　　일(1-31)　　월(1-12)　　　요일(0-7)

실행주기는 위처럼 되고.. 9시에서 15시까지 매시간 5분째 마다 실행하고 싶으면

5 9-15 * * * 이렇게 하면 된다.



반응형
저작자표시

'Programming > Linux' 카테고리의 다른 글

mount관련  (0) 2019.12.05
리눅스 비밀번호 틀린 횟수 초과 대응방법  (0) 2019.10.07
리눅스 계정 관리  (0) 2019.09.19
CentOS 7 방화벽  (0) 2017.12.04
리눅스 port 확인  (0) 2017.12.04

git remote -v 하면 repository url 확인 가능


git remote set-url origin 신규url 하면 repository변경 가능(ip가 바꼈다던가 할 때)



tag관련

git tag 하면 현재 달린 tag들 확인가능


git show v1.4 하면 태그 세부 정보 확인가능


git tag -a v1.4 -m "my version 1.4"  하면 버전 달고 메시지 쓸 수 있음


git tag -a v1.4 9fceb02 -m "my version 1.4" 하면 예전 commit에 대해서도 tag달 수 있음


git push origin --tags 이렇게 명시적으로 tag를 따로 push해줘야만 서버에 반영됨에 주의


git checkout v1.4 하면 해당 tag로 체크아웃 가능(근데 detached HEAD 상태가 된다)


git reflog 하면 detached 된 상태를 로그 히스토리 형태로 볼 수 있다.


git log --graph --decorate $(git rev-list -g --all) 하면 현재 HEAD가 어딘지 graph로도 볼 수 있다.


git checkout - 하면 detached 상태에서 원래 HEAD상태로 돌아간다. (tag 체크아웃은 풀린다)


git checkout -b version14 v1.4 하면 브랜치 만들면서 체크아웃 가능 


반응형
저작자표시

'Programming > Git' 카테고리의 다른 글

git 초기설정  (0) 2023.06.06
git log  (0) 2019.12.09
git branch 관련  (0) 2019.04.17
github  (0) 2018.11.07
--no-ff 옵션  (0) 2017.11.13

+ Recent posts

티스토리툴바