짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 카테고리의 글 목록 (31 Page)

'알고리즘'에 해당되는 글 307건

백준(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
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바