알고리즘
알고리즘54 :: MEMO - for문 N중첩 으로 완탐하기
알고리즘54 :: MEMO - for문 N중첩 으로 완탐하기
2020.02.08완탐할때 항상 bfs, arrayList 로 sub-set, bitmask를 사용해서 접근했는데 N중첩으로 for문을 겹쳐서 사용하는 방법에 익숙하지 않아서 정리합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 //N = 7 일때 for(int i=0; i
알고리즘53 :: PROGRAMMERS_섬연결하기(Greedy) - (Collections sort, Greedy, MST, Kruskal)
알고리즘53 :: PROGRAMMERS_섬연결하기(Greedy) - (Collections sort, Greedy, MST, Kruskal)
2020.02.08크루스칼 알고리즘을 활용하여 문제를 해결할 수 있습니다. 크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬하고 그 중 간선 리스트에서 사이클을 형성하지 않은 간선을 선택하여 가장 낮은 가중치를 먼저 선택하여 최소 스패닝 트리에 추가시켜 줍니다. (이 문제의 경우에는 ans 입니다.) 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 import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.u..
알고리즘52 :: 비트마스킹 으로 문제 접근하기(1)
알고리즘52 :: 비트마스킹 으로 문제 접근하기(1)
2020.02.02최근 완탐 문제를 해결하면서 팀 나누기(스타트링크, 링크와스타트, 게링맨더링 등) 에 비트마스킹을 적용하고 해결하고 싶었습니다. 그래서 여러 강의와 문서들을 참고하였습니다. for(int i=0; i
알고리즘51 :: BOJ_12100_2048(easy)
알고리즘51 :: BOJ_12100_2048(easy)
2020.02.022048 게임은 같은 숫자가 있다면 합쳐지고, 첫 턴에서는 이미 합쳐진 숫자에 대해서 같은 숫자라 하더라도 다시 합칠 수 없습니다. 문제에서 주어진 내용을 left, right, up, down 으로 각각 구현해주고 순열을 이용해서 위 4가지 경우를 5가지 순서 있게 뽑아서 field 에 있는 최댓값을 갱신해주면 됩니다. github.com/lllilllilllilili/algorithmWithDonburi/blob/master/algorithm/b12100_2048(easy)/backjun_2048.java
알고리즘50 :: BOJ_3190_뱀
알고리즘50 :: BOJ_3190_뱀
2020.02.02뱀이 사과를 먹으면 몸의 길이가 늘어나고 그렇지 않으면 지나온 빈칸은 빈 칸이 되고 이동하게 되는 문제 입니다. 뱀의 머리 ㅡ 몸통 ㅡ 꼬리 모두를 맵에 표시하는것 보다 머리의 이동 경로를 시간을 기준으로 맵에 표시해두는것이 핵심 입니다. 즉, 뱀이 움직일때마다 current_time이 1씩 증가합니다. 맵에 표시됩니다. 사과를 먹으면 몸의 길이가 1 증가하게 됩니다. 맵의 범위에서 빠져나가게 되거나 뱀의 머리가 몸에 닿는 경우인데 이 경우는 특수한 경우로 그림을 그려 생각해보면 쉽게 접근할 수 있습니다. 1 2 3 4 5 9 8 7 6 가 있을 때 9인 위치에서 // 수정중 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 ..
알고리즘49 :: SWEA_[모의 SW 역량테스트]_수영장
알고리즘49 :: SWEA_[모의 SW 역량테스트]_수영장
2020.02.01수영장 문제에는 이용권이 존재합니다. 이용권으로 이용할 수 있는 모든 경우를 확인하여 비용의 최솟값을 갱신하면 됩니다. 달을 기준으로 DFS 탐색을 하면 되며, 12월까지 존재하므로 12월을 넘어가면 return 할 수 있도록 기저조건을 설정하면 됩니다. Code : 꽥! 클릭 클릭 해주세요. 궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀
알고리즘48 :: BOJ_17142_연구소3
알고리즘48 :: BOJ_17142_연구소3
2020.01.28연구소 3 문제는 맵에 활성 바이러스와 비활성 바이러스가 주어지게 되는데 이 두가지를 잘 이용해서 문제를 해결할 수 있습니다. 맵을 순회하면서 바이러스를 ArrayList에 저장하고 이중에서 Input으로 입력받은 개수 만큼 조합을 이용해서 선택합니다. 백트래킹을 사용하여 활성 바이러스는 -2 비활성바이러스는 -3으로 표시하여 선택된 활설바이러스 로부터 BFS()를 돌렸습니다. 1 2 3 4 5 6 7 for(int i=index; i
알고리즘47 :: BOJ_15686_치킨배달
알고리즘47 :: BOJ_15686_치킨배달
2020.01.27Code : 꽥! 클릭 클릭 해주세요. lllilllilllilili/algorithmWithDonburi Algorithm with King Donburiburi♥ . Contribute to lllilllilllilili/algorithmWithDonburi development by creating an account on GitHub. github.com 궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀 꽥님의 오픈프로필 open.kakao.com 치킨 배달 문제는 두가지만 기억하고 있으면 접근하기 쉽습니다. 1) 치킨 집을 뽑을 수 = 조합 2) 그리고 맵의 크기만큼 순회하면서 집과 선택된 치킨집간의 거릿값을 모두 더해서 최솟값을 갱신하면 됩니다. 조합은 재귀를 이용해서 구현할 수 있는데 ..
알고리즘46 :: BOJ_2138_전구와스위치
알고리즘46 :: BOJ_2138_전구와스위치
2020.01.27전구와 스위치 문제는 그리디 문제로 분류되는 유형입니다. N개의 스위치와 N개의 전구가 있을 때 1번째의 스위치를 선택 하는 경우와 선택 하지 않은 경우로 나눠볼 수 있습니다. 이렇게 함으로써 A : 000 B : 010 로 A-B 상태를 보고자 할때 A의 1번째 전구의 상태가 B의 1번째 전구의 상태와 같다면 A의 다음 스위치를 누를 필요가 없게 됩니다. 이렇게 접근해야 하는 이유는 A의 스위치로 변할 수 있는 상태가 각 전구 별로 232 에서 121로 바꿀 수 있기 때문입니다. (232 는 1번째 스위치가 1,2 변할 수 있는 경우의 수 이고 2번째 스위치가 1,2,3 변할 수 있는 경우의 수이고 3번째 스위치가 2,3 변할 수 있는 경우의 수 입니다.) 즉, 이러한 상태를 1번째 스위치를 선택 한 ..
알고리즘45 :: SWEA_[모의 SW 역량테스트]_특이한 자석
알고리즘45 :: SWEA_[모의 SW 역량테스트]_특이한 자석
2020.01.26단순 시뮬레이션 문제입니다. 이 문제를 풀때 주의해야할 점은 4개의 자석이 움직일 방향을 담을 배열을 선언해야 하는 점입니다. 이와 다르게, Queue 에 넣고 자석 하나에 대해서 (좌, 우) 모두를 보며 visit 처리해도 물론 해결할 수 있습니다. ㄴ 자석이 움직일 방향은 입력받은 움직일 자석을 기준으로 왼쪽 그리고 오른쪽을 살펴보며 왼쪽의 경우 6과 2(index 0을 기준) 오른쪽의 경우 2와 6을 살펴보면 됩니다. 자석이 움직일 방향을 미리 담아 두었다면, 시계 혹은 반시계 방향에 따라서 배열을 앞으로 한칸 혹은 뒤로 한칸 이동시켜 주면 됩니다. Code : 꽥! 클릭 클릭 해주세요. 궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀
알고리즘43 :: SWEA_[모의 SW 역량테스트]_요리사
알고리즘43 :: SWEA_[모의 SW 역량테스트]_요리사
2020.01.08이 문제의 해결방법은 1. 팀을 나눈다. ex) N=6 이라면 team1 = 3, team2 = 3 으로 나눠야 한다. 2. 나눴다면 입력받은 값들을 모두 저장한다. ex) N=6 이고 team1 = 3, team2 = 3 이라면, team1 에 대해서 i = 1~3 j = 1~3 에 대해서 값을 다 더한다. (단, i!=j) 경우에 대해서만 3. 최솟값을 갱신하면 됩니다. 덧붙이는 말 1 번에 대해서 모든 경우를 확인하는 완전탐색을 진행합니다. 2 번에 대해서 문제의 조건에 따라 값을 저장해야 합니다. 3 번에 대해서 최솟값은 testcase에 대해서 초기화를 함께 해야 합니다. Code : 꽥! 클릭 클릭 해주세요. 감사합니다!
알고리즘42 :: BOJ_15683_감시(java)
알고리즘42 :: BOJ_15683_감시(java)
2019.12.12시뮬 문제 재귀에서 리턴될 때 원래 맵으로 복구해야함 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 ..