짬뽕얼큰하게의 맨땅에 헤딩 :: 짬뽕얼큰하게의 맨땅에 헤딩

백준(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

티스토리툴바