알고리즘

1일 1알고리즘

 

넥스터즈 2주차

2주차 정규활동 이전에 팀원들과 오프라인으로 모여 기획 회의를 진행했다.

생각보다 많은 팀원들이 모이게되었고, 멀리서 오신분도 계셨는데.. 대단했다.

진행도 어느정도 많이되었고, 팀 분위기도 좋았다.

정규활동 시간에도 회의를 계속 진행했고, 팀 배정이 되고 첫 발표를 진행했다.

간단하게 팀원 소개 및 진행상황을 발표하는거라 편하게 했다.

 

후기

다음주는 설이라서 2주 후에 3주차 세션이 진행되는데 이 기간안에 설계는 마무리 해야할 것 같고, 어느정도 진행을 해야겠다는 생각이 든다.

같이 백엔드 맡으신 분이 엄청 열정적이셔서 많이 배워야겠다는 생각이 들었다.

하지만 나도 같은 팀원인 만큼 최대한 기여할 수 있는 부분을 하려고 한다.

다음주도 화이팅~

'잡담' 카테고리의 다른 글

1월 4주차 결산  (2) 2023.01.30
1월 3주차 결산  (0) 2023.01.22
1월 1주차 결산  (0) 2023.01.09
12월 5주차 결산  (0) 2023.01.02
12월 4주차 결산  (0) 2022.12.26

알고리즘

1일 1알고리즘

 

넥스터즈 1주차

이번주 활동이 시작되었다.

PM 분들의 아이디어 발표 후에 팀 빌딩을 진행하였다.

내가 원하는 팀에 들어갈 수 있어서 너무 좋았다.

 

후기

큰 부분에서는 싸피와 비슷하겠지만 디자이너분들이 있다는 점, 회사 일과 병행한다는 점과 같이 다른부분도 있다.

처음 팀이 확정되고, 너무 만족스러웠다.

내가 원했던 주제기도 하고, 회식을 하면서 텐션을 담당하는 팀원이 많아서 분위기도 금방 좋아졌다.

앞으로의 일정이 기대가 되고, 민폐가 되지 않도록 준비 잘해야겠다.

'잡담' 카테고리의 다른 글

1월 3주차 결산  (0) 2023.01.22
1월 2주차 결산  (0) 2023.01.16
12월 5주차 결산  (0) 2023.01.02
12월 4주차 결산  (0) 2022.12.26
12월 3주차 결산  (0) 2022.12.19

알고리즘

1일 1알고리즘

 

후기

와 23년이다..

22년을 돌아보면 싸피를 끝내고, 취업을 했다.

회사에서 직접 프로젝트를 경험해보고 충격을 받았었다.

싸피 내에서 내가했던 프로젝트는 정말 기초중의 기초라는 것을 알게되었다.

유저 로그인을 위해 jwt 토큰을 발급 받는 과정, oauth를 이용한 로그인 이런것들을 security에서 구현할 수 있다는 것부터가 신기할 따름이었다.

올해는 새로운 경험을 위해 넥스터즈에 합류했다.

싸피 활동처럼 조급함을 가지지 않고 즐기면서 활동할 것이고, 이 활동이 내가 더 성장할 수 있는 기회가 되었으면 좋겠다.

'잡담' 카테고리의 다른 글

1월 2주차 결산  (0) 2023.01.16
1월 1주차 결산  (0) 2023.01.09
12월 4주차 결산  (0) 2022.12.26
12월 3주차 결산  (0) 2022.12.19
12월 2주차 결산  (0) 2022.12.11

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

 

14450번: Hoof, Paper, Scissors (Gold)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

가위바위보 마지막 문제입니다.

이 문제에서도 입력으로 상대방의 race가 주어지며, 베시는 같은 것만 여러번 연속으로 낼 수 있습니다.

Silver 문제와 다른 점은 K번까지 바꿀 수 있으며, K의 최대는 20입니다.

 

누적합으로는 해결할 수 없으며, dp와 재귀를 활용합니다.

dp[idx][cnt][race]: idx번째 게임에서 베시는 race를 cnt번 변경한 상태고, 현재 race를 낸 상태일 때 얻을 수 있는 최대 점수

3중 배열을 사용해야 하며, 첫 번째 게임에서 race를 낼 수 있는 경우 3가지를 모두 확인해야 합니다.

(race를 인덱스로 활용하고, 편의를 위해 입력에서 race를 숫자로 변경하였습니다.)

 

모든 경우에서 race를 변경하지 않고 연속으로 내는 경우를 구할 수 있고,

cnt < K인 경우에만 race를 변경하는 경우를 구하도록 합니다.

 

 

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX_N = 100001;
    private final static int MAX_K = 21;
    private static final int RACE_CNT = 3;
    private static int list[] = new int[MAX_N];
    private static int dp[][][] = new int[MAX_N][MAX_K][RACE_CNT];
    private static int N, K;
 
    private static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
    }
 
    private static int getScore(int x, int y) {
        if (x == 0 && y == 1) {
            return 1;
        } else if (x == 1 && y == 2) {
            return 1;
        } else if (x == 2 && y == 0) {
            return 1;
        } else {
            return 0;
        }
    }
 
    private static int dfs(int idx, int cnt, int race) {
        if (idx > N) {
            return 0;
        }
        if (dp[idx][cnt][race] != -1) {
            return dp[idx][cnt][race];
        }
 
        dp[idx][cnt][race] = dfs(idx + 1, cnt, race) + getScore(race, list[idx]);
        if (cnt < K) {
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 1) % RACE_CNT) + getScore(race, list[idx]));
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 2) % RACE_CNT) + getScore(race, list[idx]));
        }
 
        return dp[idx][cnt][race];
    }
 
    private static void func() {
        init();
        System.out.println(Math.max(dfs(1, 0, 0), Math.max(dfs(1, 0, 1), dfs(1, 0, 2))));
    }
 
    private static int getRace(char x) {
        if (x == 'H') {
            return 0;
        } else if (x == 'S') {
            return 1;
        } else {
            return 2;
        }
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = getRace(st.nextToken().charAt(0));
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

'algorithm > dp' 카테고리의 다른 글

boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2281 데스노트  (0) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12

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

 

14453번: Hoof, Paper, Scissors (Silver)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

입력으로 상대방의 race를 확인할 수 있으며, 그거에 맞도록 적절한 race를 결정해야 합니다.

그리고 베시는 같은 것만 여러번 연속으로 낼 수 있으며, 최대 한 번만 바꿀 수 있습니다.

 

이 문제는 누적합을 활용할 수 있습니다.

입력으로 주어지는 race의 P, H, S의 누적 합을 각각 구하고,

베시가 race를 변경할 어떤 구간을 기준으로 왼쪽, 오른쪽의 P, H, S의 누적합의 최대를 더한 값으로 구할 수 있습니다.

 

 

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
64
65
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static class Point{
        int pCnt;
        int hCnt;
        int sCnt;
 
        public Point(int p, int h, int s) {
            pCnt = p;
            hCnt = h;
            sCnt = s;
        }
    }
 
    private static final int MAX = 100001;
    private static Point[] dp = new Point[MAX];
    private static int N;
 
    private static void func() {
        int ret = Math.max(dp[N].pCnt, Math.max(dp[N].hCnt, dp[N].sCnt));
        for(int i = 1; i < N; i++) {
            int l = Math.max(dp[i].pCnt, Math.max(dp[i].hCnt, dp[i].sCnt));
            int r = Math.max(dp[N].pCnt - dp[i].pCnt, Math.max(dp[N].hCnt - dp[i].hCnt, dp[N].sCnt - dp[i].sCnt));
 
            ret = Math.max(ret, l + r);
        }
 
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        char x;
        N = Integer.parseInt(st.nextToken());
        dp[0] = new Point(0, 0, 0);
        for (int i = 1; i <= N; i++) {
            dp[i] = new Point(0, 0, 0);
            st = new StringTokenizer(br.readLine());
            x = st.nextToken().charAt(0);
 
            if (x == 'P') {
                dp[i].pCnt++;
            } else if (x == 'H') {
                dp[i].hCnt++;
            } else {
                dp[i].sCnt++;
            }
 
            dp[i].pCnt += dp[i - 1].pCnt;
            dp[i].hCnt += dp[i - 1].hCnt;
            dp[i].sCnt += dp[i - 1].sCnt;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

'algorithm > dp' 카테고리의 다른 글

boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 2281 데스노트  (0) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12
boj 21923 곡예 비행  (0) 2022.06.10

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

 

14456번: Hoof, Paper, Scissors (Bronze)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

입력으로 주어지는 숫자는 가위인지, 바위인지, 보인지 알 수 없습니다.

이 문제는 숫자 1, 2, 3을 가위, 바위, 보로 적절히 분배하여 첫 번째 소가 이길 수 있는 최대 게임 수를 출력합니다.

 

race를 지정할 수 있는 경우의 수는 3! = 6가지

게임 수는 최대 100게임

따라서 브루트포스로 해결할 수 있습니다.

nextPermutation으로 race의 모든 경우를 확인할 수 있고, 그 때마다 첫 번째 소가 얻을 수 있는 점수를 구합니다.

그리고 그것들의 최댓값을 구하여 출력합니다.

 

 

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX = 100;
    private final static int RACE_CNT = 3;
    private static int race[] = {1, 2, 3};
    private static int list[][] = new int[MAX][2];
    private static int N;
 
    private static void swap(int i, int j) {
        int tmp = race[i];
        race[i] = race[j];
        race[j] = tmp;
    }
 
    private static boolean nextPermutation() {
        int i = RACE_CNT - 1;
        while (i > 0 && race[i - 1] > race[i]) {
            i--;
        }
 
        if (i == 0) {
            return false;
        }
 
        int j = RACE_CNT - 1;
        while (race[i - 1] > race[j]) {
            j--;
        }
        swap(i - 1, j);
 
        int k = RACE_CNT - 1;
        while (i < k) {
            swap(i++, k--);
        }
 
        return true;
    }
 
    private static int getScore(int x, int y) {
        if (x == 1 && y == 2) {
            return 1;
        } else if (x == 2 && y == 3) {
            return 1;
        } else if (x == 3 && y == 1) {
            return 1;
        } else {
            return 0;
        }
    }
 
    private static void func() {
        int ans = 0;
        do {
            int ret = 0;
            for (int i = 0; i < N; i++) {
                ret += getScore(race[list[i][0] - 1], race[list[i][1] - 1]);
            }
 
            ans = Math.max(ans, ret);
        } while (nextPermutation());
 
        System.out.println(ans);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

'algorithm > Bruteforce' 카테고리의 다른 글

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2021.01.29
boj 1018 체스판 다시 칠하기  (0) 2021.01.29

이 글에서는 RedisRepository가 아닌, RedisTemplate를 사용한 코드를 포스팅합니다.

 

1
2
3
4
5
6
7
8
// maven
<dependency>    
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
 
// gradle
implementation 'org.springframework.boot:spring-boot-starter-data-redis'
 cs

먼저 redis의 의존성을 추가합니다.

 

1
2
3
4
spring:
  redis:
    host: localhost
    port: 6379
 cs

그 다음은 yml에 redis의 host와 port를 적어줍니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.connection.lettuce.LettuceConnectionFactory;
 
@Configuration
public class RedisConfig {
    @Value("${spring.redis.host}")
    private String host;
    @Value("${spring.redis.port}")
    private int port;
 
    @Bean
    public RedisConnectionFactory redisConnectionFactory() {
        return new LettuceConnectionFactory(host, port);
    }
}
 
 cs

redis 사용을 위한 configuration입니다.

host와 port는 yml에 작성한 값들을 가져옵니다.

하지만 SpringBoot 2.0부터는 auto-configuration으로 위에 작성한 RedisConnectionFactory나 RedisTemplate와 같은 것들이 자동으로 생성된다고 합니다.

따라서 SpringBoot 2.0 이상 버전을 사용하신다면 RedisConfig는 생략하셔도 됩니다.

 

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
import lombok.RequiredArgsConstructor;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
import org.springframework.transaction.annotation.Transactional;
 
import java.time.Duration;
 
@Service
@RequiredArgsConstructor
@Transactional
public class RedisService {
    private final RedisTemplate<String, String> redisTemplate;
 
    public String getRedisTemplateValue(String key) {
        return redisTemplate.opsForValue().get(key);
    }
 
    public void deleteRedisTemplateValue(String key) {
        redisTemplate.delete(key);
    }
 
    public void setRedisTemplate(String key, String value, long time) {
        if (getRedisTemplateValue(key) != null) {
            deleteRedisTemplateValue(key);
        }
 
        Duration expiredDuration = Duration.ofMillis(time);
        redisTemplate.opsForValue().set(key, value, expiredDuration);
    }
}
 
 cs

Redis의 기능을 담은 Service입니다.

위에서 언급한것처럼 auto-configuration으로 인해 RedisTemplate이 자동으로 생성되었기 때문에 바로 사용할 수 있습니다.

지금은 제가 문자열을 사용하기 때문에 value를 String으로 입력했지만 Object를 하셔도 됩니다.

 

set을 이용하여 <key, value> 쌍의 데이터를 저장합니다.

저장하기 전에 getRedisTemplateValue에서 key로 데이터를 검색하고, 존재한다면 deleteRedisTemplate에서 삭제부터 진행합니다.

만료 시간을 매개변수로 같이 보내서 지정할 수 있습니다.

이 때는 해당 시간이 종료되면 자동으로 삭제됩니다.

만료 시간을 매개변수로 보내지 않을 경우에는 해당 데이터가 삭제되지 않습니다.

 

세팅이 끝났으니 테스트를 해봐야겠네요.

위 명령어를 통해 redis에 접속할 수 있습니다.

여기서 -h는 호스트를 나타내며, -p는 포트번호입니다.

default는 127.0.0.1:6379 (localhost:6379)이니 localhost에서 작업하시는 분이라면 생략하셔도 됩니다.

 

그리고 위 명령어로 redis가 비어있는 것을 확인합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import com.example.test.global.redis.RedisService;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
 
@SpringBootTest
public class RedisTest {
    private final long expiredTime = 60 * 1000;
 
    @Autowired
    private RedisService redisService;
 
    @Test
    void setRedis() {
        String key = "key:emoney96";
        String value = "redis test value";
 
        redisService.setRedisTemplate(key, value, expiredTime);
    }
}
 
 cs

테스트 코드를 간단하게 작성해봤습니다.

key, value, expiredTime까지 값을 넣어주시고, key가 "key:emoney96"이고 만료 시간이 1분인 데이터를 redis에 저장합니다.

여기서 expiredTime은 ms(밀리 초) 단위입니다.

이 테스트를 실행하여 redis에 데이터를 넣어주겠습니다.

 

일단 테스트는 성공했고

데이터도 들어간 것을 확인할 수 있습니다.

만료 시간을 1분으로 등록했기 때문에 1분이 지나면 자동으로 사라집니다.

그리고 get key 명령어를 통해 해당 데이터의 value를 확인할 수 있습니다.

그리고 ttl 명령어로 해당 데이터의 유효 시간을 확인할 수 있습니다.

단위는 초 단위이며, 위처럼 양의 정수는 남은 시간을 뜻합니다.

만료 시간을 설정하지 않았을 경우 ttl 값은 -1입니다.

해당 데이터가 삭제됐거나 존재하지 않을 경우 ttl 값은 -2입니다.

'Spring' 카테고리의 다른 글

필드 주입 vs 생성자 주입  (0) 2022.10.31
SpringBoot OAuth 적용 [Naver - 2]  (0) 2022.10.18
SpringBoot OAuth 적용 [Naver - 1]  (0) 2022.10.17
SpringBoot OAuth 적용 [Kakao - 2]  (0) 2022.10.17
SpringBoot OAuth 적용 [Kakao - 1]  (0) 2022.10.14

알고리즘

1일 1알고리즘

 

후기

올해가 1주남았네..?

올해 있었던 일들 정리하고 내년을 준비할 때가 된 것 같다.

근데.. 컴퓨터를 초기화하는 과정에서 백업이 모두 날라가서 멘탈이 없어질것 같다 ㅎㅎㅎ

학교 수업, 과제부터 싸피활동 취업활동 등 모든 자료들이 날아갔다... ㅎㅎㅎㅎ

몇년의 자료들이 다날아가니 멘탈 바사삭...

일단은 지금부터라도 하나하나 다시 모아봐야겠다..

'잡담' 카테고리의 다른 글

1월 1주차 결산  (0) 2023.01.09
12월 5주차 결산  (0) 2023.01.02
12월 3주차 결산  (0) 2022.12.19
12월 2주차 결산  (0) 2022.12.11
12월 1주차 결산  (0) 2022.12.05

알고리즘

1일 1알고리즘

 

후기

하나둘씩 내친구들이 서울로 올라오기 시작했다. 동네 친구도 한명 생겼고, 경기도로 이직하는 친구도 있다.

타지역에 와서 제일 안좋았던 점이 친구가 없다는 것이었는데 ㅠ.. 너무 다행이라고 생각한다.

얼마전에 지원했던 넥스터즈에 합격을 했다.

면접을 너무 못봐서 당연히 떨어질 줄 알았는데 나의 꾸준함을 높게 보신 것 같아 다행이라고 생각한다.

내년 초부터 활동 시작이니 준비를 잘해야겠다는 생각이 든다.

'잡담' 카테고리의 다른 글

12월 5주차 결산  (0) 2023.01.02
12월 4주차 결산  (0) 2022.12.26
12월 2주차 결산  (0) 2022.12.11
12월 1주차 결산  (0) 2022.12.05
11월 4주차 결산  (0) 2022.11.28

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

 

16985번: Maaaaaaaaaze

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을

www.acmicpc.net

오랜만에 포스팅입니다. (너무 게을러서..)

 

bfs에 브루트포스까지 섞여있는 풀이가 복잡한 문제입니다.

5x5 크기의 2차원 배열이 5개 있으니 3차원 배열이 됩니다.

(0, 0, 0)에서 출발하여 (4, 4, 4)에 도착하는 최소 이동 횟수를 요구합니다.

여기까지만 보면, 단순 bfs로도 해결이 가능합니다.

 

하지만 5x5 크기의 판들의 순서도 변경이 가능하고, 판을 회전할 수도 있습니다.

브루트포스를 이 제약조건 두 개에 각각 적용해야 합니다.

 

저는 이 판들의 인덱스로 번호를 매겼고, dfs로 순회하면서 이동 횟수의 최솟값을 구하고, 회전 로직을 구현했습니다.

1
2
3
4
do {
    copyArray();
    dfs(0);
} while (next_permutation(order, order + MAX));
 cs

먼저, 순열을 이용하여 판들의 순서를 바꿔줍니다.

cpp은 next_permutation을 제공하여 편하게 구현할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int idx) {
    if (idx == MAX) return;
 
    for (int i = 0; i < 4; i++) {
        int ret = bfs();
 
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        dfs(idx + 1);
        rotate(idx);
    }
}
 cs

처음 제출했을 때의 dfs 함수입니다.

모든 경우에서 bfs로 이동 횟수를 구하고, 회전하는 방식입니다.

 

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
int bfs() {
    queue<pair<int, pair<int, int> > > q;
    q.push({ 0,{0,0} });
    memset(visit, false, sizeof(visit));
    visit[0][0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second.first;
            int z = q.front().second.second;
            q.pop();
 
            if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
                return t;
            }
 
            for (int d = 0; d < 6; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
                int nz = z + direct[d][2];
 
                if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
                if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
 
                q.push({ nx,{ny,nz} });
                visit[nx][ny][nz] = true;
            }
        }
    }
 
    return -1;
}
 cs

bfs로 이동 횟수를 구합니다.

중간에 도착 지점을 만났다면 t를 리턴, 아니면 -1을 리턴합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
}
 cs

현재 단계에서 이동횟수를 모두 구했다면 배열을 회전합니다.

회전은 90도, -90도 중에 아무렇게나 해주시면 됩니다. 한 방향으로 회전하는 것이 중요합니다.

이렇게 하시면 AC는 받을 수 있습니다.

하지만 다른 분들의 실행 시간을 보니 제 코드가 비효율적으로 동작한다는 것을 깨달았고, 가지치기를 진행하였습니다.

위의 코드들은 가지치기 이전 단계의 코드이며, 변화가 있는 로직은 rotate와 dfs입니다.

 

생각을 해보니, 문제에 답이 있었다는 것을 깨달았습니다.

  1. 참가자가 들어갈 수 없는 칸이 존재한다.
    • 그 칸이 시작/도착 지점이라면 bfs 탐색할 필요가 없다.
    • 배열은 회전하므로 시작/도착 지점이 갈 수 없는 칸일 가능성이 있다.
  2. 배열 크기는 5 x 5 x 5로 고정되어 있다.
    • 탈출이 가능한 배열에서 나올 수 있는 최소 이동 횟수는 12다.
  3. 회전을 해도 이전과 같은 모양이 나올 수 있다.
    • 이미 구한 것으로 간주하고, 다음 단계를 진행할 필요가 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
 
    if (cnt == MAX * MAX) return false;
    else return true;
}
 cs

우선 rotate입니다.

자료형은 bool로 변경되었고, 회전한 배열이 이전 배열과 같은지 확인하는 로직만 추가되었습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int idx) {
    if (idx == MAX) {
        if (!map[MAX - 1][MAX - 1][MAX - 1]) {
            return;
        }
 
        int ret = bfs();
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (map[0][0][0]) {
            dfs(idx + 1);
            if (ans == MIN_ANS) return;
        }
 
        if (!rotate(idx)) return;
    }
}
 cs

dfs 함수에 많은 변화가 있었습니다.

bfs 함수 호출은 모든 회전이 한 번씩 끝났을 때 진행하는 것으로 변경하였고, 출발/도착 지점에 대한것과 최솟값, rotate에 대한 가지치기가 모두 포함되어 있습니다.

이제 제출을 해보니 시간이 많이 줄어든 것을 확인할 수 있습니다.

 

 

최종 코드는 아래입니다.

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 5
#define MIN_ANS 12
using namespace std;
 
int list[MAX][MAX][MAX], map[MAX][MAX][MAX];
int order[MAX], ans;
int direct[6][3] = { {0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0} };
bool visit[MAX][MAX][MAX];
 
int bfs() {
    queue<pair<int, pair<int, int> > > q;
    q.push({ 0,{0,0} });
    memset(visit, false, sizeof(visit));
    visit[0][0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        if (ans <= t) return t;
 
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second.first;
            int z = q.front().second.second;
            q.pop();
 
            if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
                return t;
            }
 
            for (int d = 0; d < 6; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
                int nz = z + direct[d][2];
 
                if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
                if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
 
                q.push({ nx,{ny,nz} });
                visit[nx][ny][nz] = true;
            }
        }
    }
 
    return -1;
}
 
bool rotate(int idx) {
    int tmp[MAX][MAX][MAX] = { 0, };
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
            map[idx][i][j] = tmp[idx][i][j];
        }
    }
 
    if (cnt == MAX * MAX) return false;
    else return true;
}
 
void dfs(int idx) {
    if (idx == MAX) {
        if (!map[MAX - 1][MAX - 1][MAX - 1]) {
            return;
        }
 
        int ret = bfs();
        if (ret != -1) {
            ans = min(ans, ret);
        }
 
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (map[0][0][0]) {
            dfs(idx + 1);
            if (ans == MIN_ANS) return;
        }
 
        if (!rotate(idx)) return;
    }
}
 
void copyArray() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                map[order[i]][j][k] = list[i][j][k];
            }
        }
    }
}
 
void func() {
    ans = 1e9;
    do {
        copyArray();
        dfs(0);
    } while (next_permutation(order, order + MAX));
 
    if (ans == 1e9) ans = -1;
    cout << ans << '\n';
}
 
void input() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                cin >> list[i][j][k];
            }
        }
        order[i] = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 14466 소가 길을 건너간 이유 6  (0) 2022.10.13
boj 18112 이진수 게임  (0) 2022.09.16
boj 16946 벽 부수고 이동하기 4  (0) 2022.05.22

알고리즘

1일 1알고리즘

브론즈 4 올솔 챌린지 중인데 드디어 40문제대로 내려왔다.

하루에 하나씩 하는중이라 40일 이내로 마무리할 것 같다.

 

후기

회사에서 하던 프로젝트는 거의 마무리가 되었고, 다시 원래 하던일을 할 것 같다.

남는 시간에는 GitHub Actions를 통한 배포를 시도하는 중인데, yml 파일 작성법이라던지 모르는 부분이 생각보다 많았다.

물론 처음 뛰어드는거라 모르는게 당연할 것이고.. 앞으로도 많은 삽질을 통해 배워나가려고 한다.

포스팅은 계속 미뤄지고 있는데.. 정리중이니 조만간 올릴 예정이다.

'잡담' 카테고리의 다른 글

12월 4주차 결산  (0) 2022.12.26
12월 3주차 결산  (0) 2022.12.19
12월 1주차 결산  (0) 2022.12.05
11월 4주차 결산  (0) 2022.11.28
11월 3주차 결산  (0) 2022.11.20

알고리즘

1일 1알고리즘

 

후기

벌써 12월..? 시간 장난없다.

한건 없는데 시간만 빨리가는 느낌이다.

이번에 넥스터즈 22기 지원을 했고, 면접을 봤는데 망해버려서 결과는 뭐 기대하지 않는다 ㅎㅎ

합격한다면 후기글을 포스팅할 것이고, 아니라고 해도 다른 활동을 하면서 다음 기수를 노려볼 예정이다.

'잡담' 카테고리의 다른 글

12월 3주차 결산  (0) 2022.12.19
12월 2주차 결산  (0) 2022.12.11
11월 4주차 결산  (0) 2022.11.28
11월 3주차 결산  (0) 2022.11.20
11월 2주차 결산  (0) 2022.11.14

+ Recent posts

티스토리툴바