프로그래민👨‍💻

이 문제는 유니온파인드를 사용하는 문제이다. 유니온파인드를 사용하고 같은 그룹안에 몇개의 원소가 있는지 구하는 문제이다. 이 문제는 주의할점이 있다. 바로 입력의 형태가 문자열의 형태로 들어오기때문에 HashMap을 이용하여 이름을 인덱싱해주는 작업이 필요하다. 인덱싱을 해준후 count라는 배열을 이용하여 union할때마다 원소를 합쳐주는 과정을 거쳐 최종 결과를 출력해주면 된다. 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..

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다. 다음과 같은 로직으로 구현하였다. 1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기 2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기 3. 찾은 직선 경로에 대해 그래프의 형태를 만들기 4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기 4-1. UnionFind를 이용한 간선 기준 Kruskal알고리즘 사용 4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용 다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋..

처음에 보고 아이디어를 떠올리기 상당히 어려웠던 문제이다. 이 문제에서 전체 경우의 수를 따져본다면 전체 6팀이 경기를 하기때문에 총 15경기가 열리고, 경기마다 승,무,패 의 경우가 있기에 전체 3^15가지의 경우가 생기게 된다. 그러므로 백트래킹을 사용하여 승무패를 계속 재귀적으로 호출하면서 전체경우의 수랑 현재 테이블이랑 같아지는지 확인하여 구할수 있다. 백트래킹 문제라 전혀 생각지 못한 문제였다. 문제를 깊이 생각할 필요가 있다고 느꼈다. 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..

유니온파인드 내지는 DFS를 이용하여 1과 연결된 것을 찾는 문제이다. 첫번째로 유니온파인드로 구현해보았다. 이문제에서 유니온파인드를 사용하면서 두가지 주의할점을 찾았다. 첫째, 경로의 최적화를 하기위해 find함수에서 return find(p[num]);대신 return p[num]=find(p[num]);을 사용해주었다. 둘째로 마지막에 모든 정점에 대하여 find함수를 한번씩 실행시켜줘서 부모를 저장하고있는 p배열을 갱신해주는 작업을 하였다. 이 작업은 필수적으로 해야하는 작업인데 놓치기 쉬움으로 항상 습관적으로 해야한다. 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 ..

이 문제는 간단해 보이나 효율성을 통과하기 어려운 문제이다. 일반적인 풀이방법으로는 정확성은 통과할 수 있지만 유니온파인드 알고리즘을 사용하지 않는다면 효율성을 통과하기 어렵다. 또한, 유니온 파인드라는 것을 사용한다 하더라도 K값이 상당히 큼(10^12)으로 일차원 배열을 사용하기 어렵다. 따라서 필요한 것에 대해서만 HashMap의 형태로 유니온파인드를 사용해야한다. 이 문제는 다음과 같은 로직을 적용하였다. 1. room_number의 수를 전체 하나씩 보기 2-1. 수가 hashMap에 존재하지 않는 key이거나 (수,수) 의 형태로 존재한다면 현재 key를 배정 2-2. 그렇지 않다면 find(map.get(key))를 하여 새로운 방을 배정 3. 마지막으로 현재수와 현재수+1을 union 아이..

조합과 BFS가 합쳐진 문제이다. 이 문제는 바둑판에서 0이 되는 곳의 위치 2개를 뽑는 조합을 사용한다음, 1로 둘러쌓인 2의 최대 갯수를 구하는 BFS문제이다. 이 문제에 주의할점은 2가 테두리 혹은 1로 만 둘러쌓여야 하는데 이과정에서 나는 flag변수 possible을 하나 선언하여 0이랑 인접해있으면 count를 할수 없게 처리하였다. 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 ..

정확성과 효율성을 같이 보는 문제이다. 이 문제를 요구조건 그대로 구현한다면 어렵지 않게 풀수있고, 정확성부분에선 전부다 맞칠 수 있다. 하지만 효율성 부분에 있어선 시간초과가 나기 쉽다. 이 문제 같은 경우는 효율성을 위해선 알고리즘 기법을 사용해야하는데 나는 파라메트릭 서치 를 사용하였다. 파라메트릭 서치란 다음과 같다. 파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 푸는 것. left, right, mid 값을 사용하여 특정값을 찾는 이분탐색과 상당히 유사하며 logN의 시간복잡도를 가짐. 이분 탐색과의 차이점은 결정문제인지 아닌지의 차이. 문제로 다시 돌아가서 제한사항을 본다면 지나가는 친구들의 수는 무한이라고 주어졌다. 하지만 생각해보면 배열의 최소수인 200,000,000까지 친구들이 ..

구현할 것이 상당히 많은 문제였다. 기본적으로 벽이 갈수 있는 위치 3군대를 찾는 과정을 거치고 벽을 셋팅후 BFS하여 모든 0의 갯수를 세어주는 과정을 찾는 문제였다. 조합과 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 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..

이 문제는 조합을 사용하여 간단히 풀수있는 문제이다. (전체치킨집수)C(제한된치킨집수) 와 같은 조합식을 세우고 이대로 접근하여 풀고 그 상황에서의 치킨거리의 최솟값을 구하면 쉽게 풀 수 있는 문제이다. 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 package boj; impo..

문자열을 가지고 변환시키면서 모든경우를 다해보는 문제이다. 이 문제는 문자열을 가지고 진법변환을 해주고 HashMap을 사용하는 문제였다. 다만 주의할점은 문자열을 건드는 작업을 할때는 String 클래스를 이용하는 것보다 StringBuilder클래스를 이용해주는 것이 훨씬 시간적으로 이득이라는 점이다. 또한 문자열의 문자를 치환할때 StringBuilder 클래스의 setCharAt()함수를 이용해주면 이문제를 쉽게 풀수있다. 진법변환에 대해선 10진수를 다른 진수로 바꾸려면 Integer.pasrseInt(Num,N진법수) 와 같은 형태로 바꿀수 있지만 다른진수에서 10진수의 형태로 바꾸려면 직접해주는게 편할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..