짬뽕얼큰하게의 맨땅에 헤딩 :: '분류 전체보기' 카테고리의 글 목록 (29 Page)

'분류 전체보기'에 해당되는 글 290건

백준(BOJ) 1932

알고리즘 2018. 11. 25. 22:59
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 <algorithm>
using namespace std;
int tr[502][502];
int dp[502][502];
int N;
 
int main(void){
    scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= i; j++) {
            scanf("%d", tr[i] + j);
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= i; j++){
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + tr[i][j];
        }
    }
    int result = 0;
    for(int i = 1; i <= N; i++){
        result = max(result, dp[N][i]);
    }
    printf("%d", result);
 
}
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 2908  (0) 2018.11.26
백준(BOJ) 1157  (0) 2018.11.25
백준(BOJ) 11726  (0) 2018.11.25
백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 11726

알고리즘 2018. 11. 25. 22:45
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
int memo[1001];
int main(void){
    int N;
    memo[1] = 1;
    memo[2] = 2;
    scanf("%d", &N);
    for(int i = 3; i <= N; i++){
        memo[i] = (memo[i - 1] + memo[i - 2]) % 10007;
    }
    printf("%d", memo[N]);
}
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 1157  (0) 2018.11.25
백준(BOJ) 1932  (0) 2018.11.25
백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 2920

알고리즘 2018. 11. 25. 22:38
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int main(void){
    bool as = true;
    bool de = true;
    for(int i = 1; i <= 8; i++){
        int n;
        scanf("%d", &n);
        if(n != i) as = false;
        if(n != 9 - i) de = false;
    }
 
    if(as) printf("ascending");
    else if(de) printf("descending");
    else printf("mixed");
 
}
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 1932  (0) 2018.11.25
백준(BOJ) 11726  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
백준(BOJ) 11053  (0) 2018.11.13
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 2178

알고리즘 2018. 11. 25. 22:31
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
#include <stdio.h>
#include <queue>
 
using namespace std;
struct _pair{
    int y;
    int x;
    int cnt;
};
queue<_pair> q;
 
int R, C;
bool map[101][101];
bool visited[101][101];
int main(void){
    scanf("%d %d", &R, &C);
    getchar();
    for(int r = 0; r < R; r++){
        for(int c = 0; c < C; c++){
            map[r][c] = getchar() - '0';
        }getchar();
    }
    q.push({0, 0, 1});
    visited[0][0] = true;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    while(!q.empty()){
        _pair p = q.front();
        q.pop();
        if(p.y == R - 1 && p.x == C - 1){
            printf("%d", p.cnt);
            break;
        }
        for(int i = 0; i < 4; i++){
            int ny = p.y + dy[i];
            int nx = p.x + dx[i];
            if(ny < 0 || ny >= R || nx < 0 || nx >= C || map[ny][nx] == 0||visited[ny][nx]){
                continue;
            }
            visited[ny][nx] = true;
            q.push({ny, nx, p.cnt + 1});
 
        }
 
    }
 
 
}
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 11726  (0) 2018.11.25
백준(BOJ) 2920  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
백준(BOJ) 11053  (0) 2018.11.13
알고스팟(algospot) WILDCARD  (0) 2018.11.13
블로그 이미지

짬뽕얼큰하게

,

알고스팟(algospot) JLIS

알고리즘 2018. 11. 13. 21:09

실수한 점:

1. 먼저 범위가 정수범위인 것을 확인하지 못했다.

2. 정수 범위기때문에 최솟값 설정시 long long 으로 해야하는것을 알아차리지 못했다.

3. 초기 -1을 넘겨주고 -1일 경우는 그냥 다음 배열로 넘어가도록 하였는데, 예외인 케이스가 존재했다.

 456789, 1234 배열에서 첫번째 배열이 하나라도 진행되었다면(start1 >= 0)  start2는 -1에서 멈춰있어야 하는데, 나는 진입해버렸다. 때문에 오답이 나왔다.



  

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <limits>
using namespace std;
const long long NEGINF = numeric_limits<long long>::min();
int arr1[101], arr2[101];
int cache[101][101];
int T;
int N, M;
int jlis(int start1, int start2){
    int& ret = cache[start1 + 1][start2 + 1];
    if(ret != -1) return ret;
    ret = 2;
    long long a = start1 == -1 ? NEGINF : arr1[start1];
    long long b = start2 == -1 ? NEGINF : arr2[start2];
    long long maxNum = max(a, b);
    for(int next = start1 + 1; next < N; ++next){
        if(maxNum < arr1[next]){
            ret = max(ret, jlis(next, start2) + 1);
        }
    }
    for(int next = start2 + 1; next < M; ++next){
        if(maxNum < arr2[next]){
            ret = max(ret, jlis(start1, next) + 1);
        }
    }
    return ret;
}
int main() {
    scanf("%d", &T);
    while(T--){
        memset(cache, -1, sizeof(cache));
        scanf("%d %d", &N, &M);
        for(int i = 0 ; i < N; ++i){
            scanf("%d", arr1 + i);
        }
        for(int i = 0; i < M; ++i){
            scanf("%d", arr2 + i);
        }
        printf("%d\n", jlis(-1, -1) - 2);
    }
    return 0;
}
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
백준(BOJ) 11053  (0) 2018.11.13
알고스팟(algospot) WILDCARD  (0) 2018.11.13
백준(BOJ) 3005번  (0) 2018.11.09
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 11053

알고리즘 2018. 11. 13. 14:21

LIS 문제를 풀었다.


for문은 기존에 풀어봐서 재귀를 이용해 풀었다.

재귀를 사용하려니 더 헷갈렸다.

실수한 점은 lis함수를 재귀를 이용해 구현하면, 필요한 부분만 보게된다는 것이다.

때문에 1 2 3 4 5 1 을 list(5) 로 호출하게되면 1을 리턴하고 끝이 난다.

따라서 lis함수를 메인문에서 N갯수만큼 돌려주어야 한다. 이부분을 놓쳤다.

사실 재귀를 사용하면 필요한 부분만 탐색하기 때문에 for문보다 빠르다는 것은 알고있었다.

하지만 이런 경우, 재귀는 결국 전체를 다 검색해야하기때문에 for문과 같거나 그 이상의 시간복잡도가 걸리게 된다.


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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int N;
int arr[1000];
int cache[1000];
int lis(int n){
  int& ret = cache[n];
  if(n == 0) return ret = 1;
  if(ret != -1) return ret;
 
  ret = 0;
  int m = 0;
  for(int i = n - 1; i >= 0; i--){
    if(arr[n] > arr[i])
      m = max(lis(i), m);
  }
  return ret = m + 1;
 
}
int main(void){
  scanf("%d", &N);
  for(int i = 0 ; i < N; i++){
    scanf("%d", arr + i);
    cache[i] = -1;
  }
  int result = 1;
  for(int i = N - 1; i >= 0; i--){
      result = max(lis(i), result);
  }
 
  printf("%d\n", result);
 
}
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
알고스팟(algospot) WILDCARD  (0) 2018.11.13
백준(BOJ) 3005번  (0) 2018.11.09
블로그 이미지

짬뽕얼큰하게

,

알고스팟(algospot) WILDCARD

알고리즘 2018. 11. 13. 00:16

알고스팟 WILDCARD 문제를 풀었다.


wildcard 문자열 패턴과 입력받은 문자열을 하나씩 비교했는데,

입력받을문자열을 끝까지 갔을경우 wildcard패턴이 남은 경우 패턴이 아니라고 생각하였다.

근데, 남은 패턴이 * 인 경우에는 위 조건에 위배된다. 


때문에 이 케이스를 추가하니, AC를 받았다.


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <stdlib.h>
#include <cstring>
int T;
char wildcard[101];
int N;
char str[51][101];
int cmp(const void* a, const void* b){
    return strcmp((char*)a, (char*)(b));
}
bool check(char* ptr, char* pattern){
    if(pattern[0] == 0 && ptr[0] == 0){
        return true;
    }
    if(pattern[0] == 0 || ptr[0] == 0){
        if(pattern[0] == '*'){
            int i = 0;
            while(pattern[i] == '*') i++;
            if(pattern[i] == 0) return true;
        }
        return false;
    }
    if(pattern[0] == '?'){
        if(check(ptr + 1, pattern + 1)){
            return true;
        }
    }
    else if(pattern[0] == '*'){
        int i = 0;
        for(; ptr[i]; i++){
            if(check(ptr + i, pattern + 1)){
                return true;
            }
        }
        if(check(ptr +i, pattern + 1)) return true;
    }
    else{
        if(ptr[0] == pattern[0]){
            if(check(ptr + 1, pattern + 1)) return true;
        }
    }
    return false;
}
int main(void) {
    scanf("%d", &T);
    scanf("%*c");
    while(T--){
        scanf("%s", wildcard);
        scanf("%d", &N);
        scanf("%*c");
        for(int i = 0 ; i < N; i++){
            scanf("%s", str[i]);
        }
        qsort(str, (unsigned int)N, sizeof(str[0]), cmp);
        for(int i = 0 ; i < N; i++){
            if(check(str[i], wildcard)){
                printf("%s\n", str[i]);
            }
        }
    }
    return 0;
}
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
백준(BOJ) 11053  (0) 2018.11.13
백준(BOJ) 3005번  (0) 2018.11.09
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 3005번

알고리즘 2018. 11. 9. 12:53

http://www.boj.kr/3005


접근방법: 방향이 왼-> 오른, 위 -> 아래 방향이므로  


왼 -> 오른의 문자열중 가장 빠른 단어를 찾고(go함수),

 xy 대칭 시킨 후(rotate 함수),

다시 왼 -> 오른의 문자열중 가장 빨리 나오는 단어를 찾았다(go함수).



실수: xy대칭 함수를 작성할때 정사각형을 생각하고 작성하였다.

때문에 직사각형일 경우 정사각형부분만 대칭되는 문제가 있었다.

ㅠㅠ 좀더 생각잘하자



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
#include <iostream>
#include <string.h>
#include <cstdio>
char result[21]="zzzzzzzzzzzzzzzzzzzz";
char str[21][21];
int R, C;
void rotate(){
  for(int i = 0; i < 21; i++){
    for(int j = 0;j <= i; j++){
      char tmp = str[i][j];
      str[i][j] = str[j][i];
      str[j][i] = tmp;
    }
  }
}
 
void go(){
  for(int i = 0 ; i < R; i++){
    for(int j = 0; j < C; j++){
      if(str[i][j] == '#') str[i][j] = 0;
    }
    int j = 0;
    while(j + 1 < C){
      if(str[i][j] != 0 && str[i][j + 1] != 0){
        if(strcmp(str[i] + j, result) < 0){
          strcpy(result, str[i] + j);
        }
        while(j < C && str[i][j] != 0){
          j++;
        }
      }
      else{
        j++;
      }   
  }
}
 
int main(void){
  scanf("%d %d", &R, &C);
  scanf("%*c");
  for(int i = 0; i < R; i++){
    scanf("%s", str[i]);
  }
  go();
  rotate();
  go();
  printf("%s", result);
 
}
cs

'알고리즘' 카테고리의 다른 글

백준(BOJ) 2920  (0) 2018.11.25
백준(BOJ) 2178  (0) 2018.11.25
알고스팟(algospot) JLIS  (0) 2018.11.13
백준(BOJ) 11053  (0) 2018.11.13
알고스팟(algospot) WILDCARD  (0) 2018.11.13
블로그 이미지

짬뽕얼큰하게

,

스트래티지 패턴(Strategy pattern)

디자인 패턴 2018. 7. 4. 23:46

스트래티지 패턴


심오한 패턴이다. 같은 기능을 전략적으로 사용하고싶을때 사용 할 수 있다.


구체적으로 내가 이해한 내용을 적어본다.


1. 전략적 sorting


나는 sorting 라이브러리를 만드로 사용하는 상황으로 이해했다.


라이브러리 개발자 입장에서는 sort를 할 수 있는 방법이 여러가지이다. 같은 기능을 하지만, 각각의 장단점이 존재하기에 이를 고려한 설계를 한다. 


라이브러리 사용자 입장에서는 여러가지 sorting알고리즘의 장단점에 대해 알고있고, 이를 활용하고 싶어한다.





이러한 상황에서 라이브러리 개발자는 다양한 sorting알고리즘에 유연한 설계를 해야하며 사용자가 여러가지 sorting알고리즘을 활용할수 있도록 해야한다. 또한 유지보수를 위해 sorting알고리즘 추가에 대해서도 생각해야한다.





따라서 라이브러리 개발자는 다음과 같이 설계할 수 있다.


인터페이스를 통해 같은기능을하는 세 클래스를 구현한다.


세클래스를 구현 한 후 전략적 패턴을 사용하기 위해 SortManager클래스를 구현한다.





이런 형태가 된다.


따라서 사용자는 SortManager의 setSort를 통해 Bubble, Quick, Merge를 선택할 수 있고, sort함수를 활용하여 Sort할 수 있다.


strategy 패턴에서는 SortManager가 핵심인듯 하다.


어떤 행위에 대해서 전략적으로 바꿔야 할 상황이 온다면 그 행위에 대한 interface를 정의하고 바뀔 상황에 맞는 interface를 구현해준다. 또한 구현한 interface를 상황에 맞게 쓸 수 있도록 set해주는 클래스를 제공해줘야 strategy 패턴이 완성된다.


strategy 패턴이 적용 될것을 미리 파악하고 설계한다면, 더 유연한 설계가 될 것 같다.



출처: https://www.youtube.com/watch?v=UEjsbd3IZvA&list=PLsoscMhnRc7pPsRHmgN4M8tqUdWZzkpxY






블로그 이미지

짬뽕얼큰하게

,

코리아텍 저지 1010 접두소수

카테고리 없음 2017. 8. 31. 15:40

접두소수 문제를 풀었다.

http://judge.koreatech.ac.kr/problem.php?id=1010


에라토스테네스의 채 알고리즘을 공부한 참에 이걸 이용하려다가... 메모리 초과가 났다.


n이 8까지여서 배열을 array[100000000] 9자리 선언했더니 ..... 

128메가 제한인데 800메가정도 잡힌것? 같다.(정확히는 모르겠다.)  

무튼 계속 시도하다 안됨을 깨닫고.. bfs로 풀었다.


bfs구현은 어려움 없이 구현 되었다. 수를 붙일때마다 소수검사를 해준다.


package koreatech1010;

import java.util.*;

class Pair{

int num;

int cnt;

public Pair(int num, int cnt){

this.num = num;

this.cnt = cnt;

}

}

public class Main {

public static boolean[] isNotSoSoo;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

Queue q = new LinkedList();

q.add(new Pair(2, 1));

q.add(new Pair(3, 1));

q.add(new Pair(5, 1));

q.add(new Pair(7, 1));

while(!q.isEmpty()){

Pair pair = (Pair)q.poll();

if(pair.cnt == n){

System.out.println(pair.num);

}

int[] di = {1, 3, 7, 9};

for(int i = 0; i < 4; i++){

int temp = pair.num * 10 + di[i];

if(isSoSoo(temp)){

q.add(new Pair(temp, pair.cnt + 1));

}

}

}

}

public static boolean isSoSoo(int n){

for(int i = 2; i * i < n; i++){

if(n%i == 0){

return false;

}

}

return true;

}


}


블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
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

티스토리툴바