https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 자체는 어렵지 않지만 조건을 나누는 것이 상당히 까다롭다. 코딩테스트 풀 때도 이 문제 풀이 능력을 살리기 위해서 최대한 쉽게 코드를 짜려고 해보았다. 고려한 엣지 케이스 1. 0이 있는 경우 - 0, 3, -3 - 0, 1, 2 2. 음수가 있는 경우 - -1, -2, -4 3. 동일한 값이 여러 개 있는 경우 - 1, 1, 2 이 때문에 multiset을 썼다. 4. 복합적인 케이스 - 0, 0 3, 3, 3, 3 ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net DFS, DP 방법을 시도하였으나 결국엔 다익스트라로 풀면 깔끔한 문제이다. 참고로 DFS로 풀면 시간 초과가 발생한다..ㅠ 다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로서, 이 문제 또한 출발점이 [0][0]인 하나로 지정되어있기에 가능한 풀이이다. 대신 기존의 풀이방식과 달라서 처음부터 다익스트라로 푸는 것을 떠오르지 못했다. 왜냐하면 2차..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이제 알고리즘 문제풀이 방식을 조금 바꿨다. 이제는 더이상 미리 문제 유형을 보지 않고 도전하기로 했다. 그리고 엣지 케이스를 스스로 찾는 능력을 키우기 위해 질문 게시판도 자제하기로 노력하기로! 아무래도 그동안 외부의 힌트를 구한 탓인지 혼자 알고리즘을 풀 때 제대로 문제를 해결해나가지 못한 경우가 많았기 때문이다. 이러한 전환의 첫 시작이 된 문제, 숨바꼭질3..

https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 푼 문제인데, 복습을 위해서 다시 정리해보았다. 서로의 번호를 매치하며 서로의 번호가 prefix인지를 확인한다. 하나는 prefix 번호, 다른 하나는 mateched 번호로 설정해서 이중 루프를 돌며 검색한다. 그런데 그렇게 되면 Hash가 아니라 일반 배열로 검색해도 되지 않을까? 라는 의문이 들 수 있다. 배열에서 matched 되는 번호를 매번 찾으면 시간 복잡도가 $O(N)$이다..

https://atcoder.jp/contests/abc261/tasks/abc261_d D - Flipping and Bonus AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp DFS로 문제를 풀었는데, 시간이 초과되어서 결국 컨테스트 시간 내에 해결하지 못한 문제이다. [문제 해석] 1부터 $i$번째 코인부터 던져서 만약 head가 나오면 카운터를 1 증가하고, $X_i$ 엔을 받는다. 만약 tail이 나오면, counter를 0으로 리셋하고 돈을 받을 수 없다. 추가적으로 M개의 스트라이크 보너스가 있다. $i$번째..

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아주아주 풀어보는 게 다행인 문제였다. 이 문제를 보자마자 Union-Find 문제라는 점은 알아차렸고, 최적화도 적용했다. 하지만 몇 개의 테스트 케이스가 자꾸 통과하지 못해서 문제가 이상하나? 라고 생각했으나, 내가 이상한 거였다. Testcase #7. 테스트 케이스7번을 통과하지 못한 이유는 union 함수를 잘못 짰다. void _union(int x, int y) { int parent..