소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
Sol 1 : ArrayList, Sol 2 : Stack

풀이
따로 알고리즘 구현이 필요 없는 문제이다. ArrayList, List, Stack 과 같은 자료구조 개념을 알고 있다면 쉽게 풀 수 있는 문제이다.

  1. 열 순서대로 인형 탐색

  2. 인형 있으면 -> 해당 칸 빈칸으로

  3. Stack or List 마지막 칸과 비교 같으면 삭제 후 정답 카운트 증가
    다르면 맨 뒤에 추가

  4. moves배열의 길이만큼 수행했다면 정답 카운트 출력

상당히 간단하다. Stack, List 둘다 가능할 것이라 생각하여 solution을 2개 만들었다.

로직은 같고 차이점은 Stack은 뽑는 행위가 디폴트 값으로 마지막 위치에 인형을 뽑는다. 그리고List는 (인덱스 값-1)을 매개변수로 get()을 이용하여 바구니 마지막 위치에 있는 인형을 출력한다.

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
// before test, have to delete 'static' keywords
    public static int solution(int[][] board, int[] moves) {
        int answer = 0;
 
        ArrayList<Integer> box = new ArrayList<Integer>();
 
        for (int idx = 0; idx < moves.length; idx++) {
 
            int row = moves[idx] - 1;
 
            for (int col = 0; col < board.length; col++) {
 
                int boxLastIdx = box.size() - 1;
 
                if (board[col][row] != 0) {
 
                    if (box.isEmpty()) {
                        box.add(board[col][row]);
                    } else {
 
                        if (box.get(boxLastIdx) == board[col][row]) {
 
                            box.remove(boxLastIdx);
                            answer += 2;
                        } else {
                            box.add(board[col][row]);
                        }
 
                    }
                    board[col][row] = 0;
 
                    break;
 
                }
 
            }
 
        }
 
        return answer;
    }
    
 
    public int solution2(int[][] board, int[] moves) {
        Stack<Integer> box = new Stack<Integer>();
 
        int answer = 0;
        for (int i = 0; i < moves.length; i++) {
            int row = moves[i];
            for (int col = 0; col < board.length; col++) {
                if (board[col][row - 1!= 0) {
 
                    if (box.empty()) {
                        box.push(board[col][row-1]);
                    } else {
 
                        if (box.peek() == board[col][row-1]) {
                            box.pop();
                            answer += 2;
                        } else {
 
                            box.push(board[col][row-1]);
                        }
 
                    }
                    board[col][row-1= 0;
 
                    break;
                }
 
            }
 
        }
 
        return answer;
    }
cs

'알고리즘(추가예정) > 기타' 카테고리의 다른 글

[프로그래머스] 베스트앨범  (0) 2020.08.30

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
DP

풀이
처음에 설계를 올바르게 하지 못해 상당히 시간이 걸렸다. 30분정도 진행하다가 이내 잘 못 되었다는 것을 깨닫고 다시 설계를 해서 10분만에 끝냈다.
숫자 3개와 뭔가 규칙성이 있다는 것을 알고 있었지만, 이것을 3의 지수승으로 접근했다. 하지만 숫자에 따라서 3으로 나누면 나머지가 0,1,2가 된다는 것을 알게 되었다. 단, 1,2,4로 표현을 해야되기 때문에 나머지가 0일때는 4를 문자열에 더해주면 된다.

너무 어렵게 생각하면 독이 된다는 것을 가르쳐준 문제였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    public static String solution(int n) {
 
        String answer = "";
 
        int mod;
 
        while (n > 0) {
 
            mod = n % 3;
            n /= 3;
 
            if (mod == 0) {
                n -= 1;
                mod = 4;
            }
 
            answer += String.valueOf(mod);
 
        }
 
        return answer;
 
    }
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 네트워크  (0) 2020.08.23
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조

HashMap,ArrayList

풀이
문제를 보고 HashMap 사용을 떠올랐다. 가장 먼저 생각한 것은 자바의 콜렉션을 최소화 하여 문제를 풀어내는 것 이었다. 그리고 총 4개의 콜렉션을 사용하여 문제를 풀었다.

먼저 파악해야 될 것은 정렬의 우선순위 요소 파악이다.

“장르 우선순위 , 노래 재생 횟수, 고유번호가 낮은 순서” 이렇게 우선순위가 선정되어 정렬이 된다. 파악한 우선순위로 차례차례 문제를 풀면 간단히 해결이 된다.

  1. 각 장르별로 재생된 횟수 구하여 HashMap에 담기

  2. 노래에 대한 구조체를 만들어 ArrayList에 담기

  3. 정렬하기 : Collections.sort() 함수 이용

  4. 정렬된 ArrayList에서 장르별 순서대로 2개씩 노래 새로운 ArrayList에 담기

간단하게 표현하면 이렇게 4단계로 문제가 풀린다. 자세한건 코드를 보면서 파악하기 바란다.

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
    // before test, have to delete 'static' keywords
    public static int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genresCheck = new HashMap<String, Integer>();
        HashMap<String, Integer> inputCheck = new HashMap<String, Integer>();
        ArrayList<Song> songList = new ArrayList<Song>();
        ArrayList<Integer> outputList = new ArrayList<Integer>();
        //1. genres count
        
        
        
        for(int g_idx = 0; g_idx < genres.length; g_idx++) {
 
            String g_str = genres[g_idx];
            songList.add(new Song(g_str,plays[g_idx],g_idx));
            
            if(genresCheck.containsKey(g_str)) {
                genresCheck.put(g_str, genresCheck.get(g_str)+plays[g_idx]);
            } else {
                
                genresCheck.put(g_str, plays[g_idx]);
            }
            
        }
        //2. sort
        
        Collections.sort(songList, new Comparator<Song>() {
            
            //s1 new
            @Override
            public int compare(Song s1, Song s2) {
                
                if(s1.genresName.equals(s2.genresName)) {
                    
                    if(s1.playCount != s2.playCount) {
                        return - (s1.playCount - s2.playCount);
                    } else {
                        
                        return (s1.songNum - s2.songNum);
                    }
                    
                } else {
                    
                    return -(genresCheck.get(s1.genresName) - genresCheck.get(s2.genresName));
                    
                }
                
            }
            
            
        }); 
        //3.checking
        for(int idx = 0; idx < songList.size(); idx++) {
            
            Song song = songList.get(idx);
            
            if(!inputCheck.containsKey(song.genresName)) {
                inputCheck.put(song.genresName, 1);
                outputList.add(song.songNum);
            } else {
                
                int cnt = inputCheck.get(song.genresName);
                
                if(cnt > 1) {
                    continue;
                } else {
                    inputCheck.put(song.genresName, cnt+1);
                    outputList.add(song.songNum);
 
                }
                
            }
            
        }
        
        int[] answer = new int[outputList.size()];
        
        for(int s_idx = 0; s_idx < answer.length; s_idx++) {
            answer[s_idx] = outputList.get(s_idx);
        }
 
 
        return answer;
    }
 
    static class Song {
        
        String genresName;
        int playCount;
        int songNum;
 
        public Song(String genresName, int playCount, int songNum) {
            
            this.genresName = genresName;
            this.playCount = playCount;
            this.songNum = songNum;
 
        }
 
    }
 
cs

'알고리즘(추가예정) > 기타' 카테고리의 다른 글

[프로그래머스] 인형뽑기  (0) 2020.08.30

블로그를 다시 시작합니다. 

알고리즘은 이전에 풀어놓은것을 사용하지 않고 다시 풀면서 

업로드를 진행할 예정입니다.

연구실에서 경험한 

SDN, NFV, 컨테이너, 쿠버네티스등 다양한 분야에 관련된 글 포스팅을

진행할 예정입니다.

현재 구직중에 있습니다 

링크드인 :  https://www.linkedin.com/in/gilho0608/

 

 

'일상 > 그냥이야기' 카테고리의 다른 글

2021년 취업 성공 후기  (2) 2021.01.17

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
DFS/BFS, 그래프

풀이

간단한 DFS/BFS 문제이다. 문제를 푸는데 20분도 안 걸렸다. 이번에는 DFS를 이용해서 해당 문제를 풀었다. 이 문제를 읽고 생각을 했던 것은 2차원 배열에서 (n,n) 칸들을 기준으로 좌우 대칭이 된다는 것이다. 또한 각각의 값들이 연결관계를 표현했다. 따라서 처음에 탐색할 때는 1/2만 탐색을 하고 DFS 를 사용할 때는 연결관계를 기준으로 탐색을 하면 된다. 보통의 DFS 문제는 ‘상하좌우’로 움직이면서 문제를 해결했지만, 해당 문제는 배열의 값들이 내포하고 있는 연결관계를 이용해서 DFS 함수를 구현했다.

  1. 초기화
  2. 문제에 해당하는 조건( 배열의 값 : 1 && 아직 탐색하지 않은 칸) 찾기 ,조건을 찾을 때 마다 answer++
  3. 조건 찾고 나서 DFS 함수를 이용해 연결관계를 따라 영역표시하기
  4. 다시 2-3번 반복
  5. Answer 출력

간단한 DFS 문제이다. 실제로 삼성 시험을 봤던 사람들에게는 매우 쉬웠을 거라 생각한다. 다만 이것을 어떻게 해야 더 효율적으로 구현할 수 있을까 고민해보았다. 간단한 문제라 특별하게 적용할 것은 없었으나, 그래도 고민 해보면 좋을 것이다.

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
    public static int SIZE;
 
    // before test, have to delete 'static' keywords
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[][] visited = new boolean[n][n];
        SIZE = n;
 
        for (int c_idx = 0; c_idx < n; c_idx++)
            for (int r_idx = c_idx; r_idx < n; r_idx++) {
 
                if ((computers[c_idx][r_idx] == 1&& (visited[c_idx][r_idx] == false)) {
                    visited[c_idx][r_idx] = true;
                    dfs(r_idx, visited, computers);
                    answer++;
 
                }
            }
 
        return answer;
    }
 
    public static void dfs(int idx, boolean[][] visited, int[][] computers) {
 
        for (int col = 0; col < SIZE; col++) {
 
            if ((computers[idx][col] == 1&& (visited[idx][col] == false)) {
 
                visited[idx][col] = true;
 
                dfs(col, visited, computers);
 
            }
 
        }
 
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조

DP , 피보나치

풀이

문제에 대한 접근 방향이 중요하다. 여러 접근에 대한 후보를 떠올리고 최적의 후보를 택하여 접근해보았다. 인덱스 순서대로 접근하려고 했으나, 이내 방향을 바꿔 가장 맨 뒤를 가정하고 접근했다.

내가 N일 때, N-1, N-2에 올 수 있는 모양에 대해서 생각해보면 된다.

  • N-1 일 때 : 블록을 세울 수 밖에 없다.

  • N-2 일 때 : 세로 블록 2개 , 가로 블록 2개인 경우로 나뉠 수 있다. 하지만 세로 블록 2개인 경우에 N-1인 경우와 같다. 따라서 가로 블록 2개인 경우만 카운팅 된다.

즉, N-1, N-2가 어떠한 블록이 오느냐에 따라서 자동으로 N번째까지 블록이 채워진다.

그러므로 N-1 + N-2 개수를 합하여 더 하면 된다.

N = (N-1)+(N-2) => 피보나치

규칙을 보면 피보나치 수열이 근간이 되어 풀리는 문제다. 자세한건 코드를 보면서 파악하기 바란다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    public static int solution(int n) {
        int answer = 0;
        int s = 1000000007;
 
        int[] dp = new int[n + 1];
 
        dp[0= 0;
        dp[1= 1;
        dp[2= 2;
 
        for (int idx = 3; idx <= n; idx++) {
 
            dp[idx] = (dp[idx - 2+ dp[idx - 1]) % s;
 
        }
 
        answer = dp[n];
 
        return answer;
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 네트워크  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13


문제보기


상당히 오래 걸렸다. 

백준강의 자료를 참고해서 완성할 수 있었다. 


마징가는 태권V덕분에 가로등만 끄면 되는 편한일(?)을 맡았다는 내용,


마징가의 움직임에 살펴보자 마징가는 현재 '5'번의 위치하고 있다. 

그리고 끄려면 수평으로 움직여야 한다. 

그렇다면 어떻게 움직일 수 있는가 ? 

좌우로 움직이면 된다. 

그리고 생각해보면 만약 두칸을 움직여서 끄면 건너뛴 가로등을 다시 꺼야되는

일이 발생한다. 

두번 일하지 말고, 가면서 만나는 가로등은 다 끄도록하자.

결국

좌우로 움직이게 되고 가로등을 끄면서 켜져있는 값들을 더하면서 나가면된다. 


점화식은 

if(left - 1 >= 1) {

ans = Math.min(ans, solution(left-1,right,0) + (a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));

} 

if(right + 1 <=n) {

ans = Math.min(ans, solution(left,right+1,1) + (a[right+1]-a[now])*(s[n]-s[right]+s[left-1]));

}


이렇게 된다 왼쪽으로 움직이는 경우 마지막 index 1번까지 갈 수 있고 ,

오른쪽으로 움직이는 경우 마지막은 n까지 갈 수 있다. 

그리고 왼쪽으로 움직인경우 index를 이동해야하기 때문에 left-1, 오른쪽은 right+1하면서 이동하면된다. 


베이스 케이스는

if(left == 1 && right == n) {

return 0;

}

이렇게 된다. 


그리고 현재 켜져있는 값들을 계산해야된다. 


(a[now]-a[left-1])*(s[n]-s[right]+s[left-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
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
package Problems;
import java.util.Arrays;
/**
 * 
 * 백준 2315 가로등끄기 
 * 
 *  동적계획
 * 
 *
 */
import java.util.Scanner;
public class Boj2315dp {
    
    public static int n,m;
    public static int a[] = new int[1001];
    public static int w[] = new int[1001];
    public static int s[] = new int[1001];
    public static int d[][][] = new int[1001][1001][2];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m= in.nextInt();
        
        for(int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = s[i-1+ w[i];
        }
        
        for(int i = 0; i < 1001; i++) {
            for(int j = 0; j < 1001;j++) {
                for (int w = 0; w <2; w++) {
                    d[i][j][w] = -1;
                    
                }
            }
        }
        
        System.out.println(solution(m,m,0));
        
    }
    
    public static int solution(int left, int right, int where) {
        
        if(left == 1 && right == n) {
            return 0;
        }
        
        if(d[left][right][where] != -1) {
            return d[left][right][where];
        }
        
        int ans = 214748364;
        
        int now = where == 0 ? left : right;
        System.out.println("now  :  " + now);
        if(left - 1 >= 1) {
            ans = Math.min(ans, solution(left-1,right,0+ (a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));
        } 
        
        if(right + 1 <=n) {
            ans = Math.min(ans, solution(left,right+1,1+ (a[right+1]-a[now])*(s[n]-s[right]+s[left-1]));
            
        }
        
        d[left][right][where] = ans;
        
        return ans;
    
    
    }
 
}
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 네트워크  (0) 2020.08.23
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08

문제보기


*경우는 두 가지가 있습니다. (더하기 , 뺴기)

*조건에 따라서 필터링 해줍니다 (0보다 커야됩니다.)

*2차원으로 만들어 값을 체크하면서 진행합니다. 

 -> D[N][M]    

*곡 연주가 가능하다면 배열의 해당칸에 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package Problems;
 
/**
 * 
 * 백준 1495 dp
 *
 */
import java.util.Scanner;
 
public class Boj1495dp {
 
    public static int n, s, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        s = in.nextInt();
        m = in.nextInt();
        int max = -1;
        int[][] arr = new int[n + 1][m + 1];
 
        int[] v = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
        }
        arr[0][s] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (arr[i-1][j] == 1) {
                    if (j + v[i] > m && j - v[i] < 0) {
                        continue;
                    }
 
                    if (j + v[i] <= m) {
                        arr[i][j + v[i]] = 1;
                    }
 
                    if (j - v[i] >= 0) {
                        arr[i][j - v[i]] = 1;
 
                    }
 
                }
 
            }
        }
 
        int result = -1;
        for (int j = 0; j <= m; j++) {
            if (arr[n][j] == 1) {
                if (result < j) {
                    result = j;
                }
            }
        }
 
        System.out.println(result);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07

+ Recent posts