메이쁘

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 문제 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 www.acmicpc.net 이분탐색 문제이다. 도저히 고민하다가 못풀겠어서 풀이 방법을 살짝(많이) 보고 이해한 다음 해결했다.. 이분탐색 어렵다. 계속 관련 유형 문제들을 풀어봐야겠다. 핵심은 문제에 있다. 1. 모든 보석을 N명의 학생들에게 나눠줘야 한다. 모든 보석이다. 하나라도 남으면 안된다. 2. 보석을 받지 못하는 학생이 있어도 된다. 즉, 모든 보석을 나눠줘야 하지만 한명당 꼭 하나 이상씩 나눠줄 필요는 없다. ..

https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 기본 백트래킹 문제. K 개 중 중복없이 6개를 뽑아서 사전순으로 정렬해서 출력하는 문제 이다. 근데 말이 사전순 정렬이지 백트래킹을 사용할 때, 앞에서부터 순차적으로 탐색하면 자동적으로 사전 순 정렬이 된다. 즉, KP6 을 구하는 문제. 이를 백트래킹으로 순열 함수를 구현하면 된다. 자세한 사항은 하단 소스코드 를 참고해주세요. 감사합니다. 소스코드

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 브루트 포스 문제. 순열 을 사용했다. 순열을 통해 부호를 순차적으로 선택하며, 선택할 때 마다 차곡차곡 계산해서 패러미터로 담아 재귀호출한다. 그래서 모든 부호를 선택한 경우에 지금까지 계산한 결과값들 중 최솟값을 찾아 출력하면 끝! 더 자세한 사항은 아래 소스코드를 참고해주세요. 감사합니다. 소스코드

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 왜 정답률이 낮은지 모르겠는 문제.. 문자열 개수가 상당해서 처리하는데 2초를 초과하는 경우가 많나보다.. 나도 그럴 뻔 했지만 문자열 탐색에서는 HashMap이 가장 효율이 좋다는 것을 들어서 이를 활용해서 바로 해결했다. 여기서는 문자열 번호 양 쪽이 연결되어 있어야 한다. 문자열로 번호를 찾거나 번호로 문자열을 찾거나 둘 중 하나를 찾는 문제이기 때문에. 그래서 ..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 브루트 포스 문제이다. 감소하는 수 중 N번 째의 수를 찾는 문제. 핵심은 - 한 자리의 수 i는 i번째 수에 해당한다. - K 자리를 가지는 수 중 K 자리에 들어올 수는 최소 K - 1 이상이다. ex. 2 자리를 가지는 수 중 최소 -> 10 4 자리를 가지는 수 중 최소 -> 3210 8 자리를 가지는 수 중 최소 -> 76543210 - 최대 10자리까지 가능하다. 1..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. www.acmicpc.net 대표적인 에라토스체네스의 체 를 활용한 문제이다. 난이도는 크게 어렵지 않은데 생각보다 실수로 인해 틀릴 수 있는 문제 헷갈린 것 중 Q. n = a + b 일 때, a 와 b는 같은 숫자여도 되는가? A. 된다. 6 = 3 + 3 일 때도 성립한다. Q. 홀수 중에 1은 안되고 3부터 인가? A. "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 즉, 3부터 가능. 끝이다...

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Disjoint - Set 알고리즘 분류 문제인데 일반적인 방법으로 풀었다. 두 가지 전부 작성하겠다. 우선, 이 문제의 중점은 "경로 중복 가능하고, 이전 경로를 되돌아갈 수 있다." 는 것이다. 기존의 그래프 문제(특히, 다익스트라 같은) 들은 대부분 중복된 경로를 허용하지 않는다. 그렇기때문에 다른 알고리즘을 사용하는 것이고. 하지만 여기서는 반대로 가능하기 때문에 Disjoint - Set..

https://www.acmicpc.net/problem/9938 9938번: 방 청소 문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 � www.acmicpc.net 너무 이해가 되지 않아 풀이를 참고한 문제. 난이도는 좀 높다. 이게 생각을 살짝 바꾸면 해결할 수 있는데 그게 어렵다. 그리고 문제에서 형광칠한 부분이 조금 이해가 안됬었다. - 만약 Union - Find 알고리즘을 사용해야 한다면 술을 다른 서랍으로 이동시키기 위해 parent를 어떻게 설정할 건지 - 술을 서랍에 넣었을 때를 체크해두는 방법 이렇게 두 가지를 해결못해 풀이 참고를 했었..

https://www.acmicpc.net/problem/10774 10774번: 저지 문제 학교 대표팀은 1부터 번호가 매겨진 저지를 학생 선수들에게 배분하고자 한다. 저지의 사이즈는 S, M, L 중 하나이다 (물론 S=small, M=medium, L=Large다). 각각의 선수들은 구체적인 저지의 번호와 www.acmicpc.net Disjoint Set 인줄 알았지만 단순 알고리즘 문제였다. 쉬운 방법을 두고 Disjoint Set 알고리즘을 어떻게 사용할까 고민하다가 시간만 축낸 문제. 여기서 한가지 깨달은 것은 필자가 Disjoint Set 알고리즘 분류를 선택해서 찾은 문제이기 때문에 무조건 Disjoint Set 알고리즘을 사용하여 해결한다. 는 생각이 자리잡혀 시야가 좁아졌다는 것. 항..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이 www.acmicpc.net 처음에 Union - Find 알고리즘을 생각도 못하고 정공법으로 풀려고 했으나 제한 시간과 여러 변수들이 많아 어떤 알고리즘으로 풀어야했는지 검색했었다... 그 다음 Union - Find 알고리즘을 사용해서 정답은 유추했으나 시간 제한이 걸려버렸다. (심지어 3초인데도..) 그래서 이것저것 바꾸다가 알게된 사실은 HashMap이 탐색 시 가장 빠르다는 것. 필자는 처음 문자열과 그 문자열의 index..