메이쁘

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..

https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비� www.acmicpc.net Disjoint - Set 알고리즘 중 하나. 처음에 풀긴 풀었는데 브루트 포스 처럼 풀어서 속도랑 메모리가 엄청났었다. 하지만 Disjoint-Set (Union-Find) 알고리즘으로 해결한 굇수님의 코드를 보고 한 대 쎄게 맞은 느낌이 들었다. 아직 나는 부족한 것이 많고, 배울 것이 많다. 처음에 하단 소스코드를 보면 무조건 헷갈리고 어려울 것이다. 핵심만 기억하자. - 처음 비행장 게이트 배열..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 그놈의 시간 초과 때문에 (제한시간 1초) 그리고 나만의 이진 탐색 방법을 사용하려고 하다보니 예외가 계속 나와서 그거 해결하느라 시간이 오래걸렸다. 결국에는 내 탐색 알고리즘으로 문제를 해결했으나.. *** 실제 이진탐색을 사용하는 방법도 있다. 베스트 정답을 보니 이렇게 쉽게 풀 수 있는 방법이 있었어? 생각이 들며 이 방법을 공부했다. *** 정말 감사합니다..

https://www.acmicpc.net/problem/10711 10711번: 모래성 문제 명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 �� www.acmicpc.net 시간초과 때문에 꽤나 애먹었던 문제.. 핵심 키워드는 이거다. "모래성이 아닌 빈 모래를 활용하라." BFS, DFS, Deque, 2중 for문 등등 여러 방법을 동원해봤지만 테스트케이스는 통과하는데 시간은 초과되는 문제가 계속 일어났다. 그러던 중, 번뜩 떠올랐다. "굳이 파도 한 번마다 모래성 주위 8방향을 탐색하며 갯수 셀 필요가 있을까?" "모래성은 어차피 줄어들고,..