오뚝이개발자

문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 나의 풀이 단순히 두 배열의 합을 구해 일일히 비교하면서 합이 T가 되는지 구해보는 방식은 O(n^2m^2)만큼의 시간복잡도가 걸려서 통과되지 않는다. 연산시간을 줄여야 하는데 A의 부분합에 대한 dictionary를 만든 뒤 (T-B의부분합)이 A의 부분합 dictionary 내에 있는지 파악해 가짓수에 더해주..

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 나의 풀이 백트래킹을 사용해서 탐색을 해주면 된다. 검사할 항목은 가로, 세로, 3x3 사각형 안에 사용된 숫자들이 무엇인지이다. 이를 c1, c2, c3에 기록해두고 겹치지 않는 숫자 candidate들을 하나씩 넣어보면서 조건에 위배되는지를 살펴보고 위배된다면 백트래킹으로 다시 값들을 복구하고 다음 후보 숫자를 넣어 탐색하면 된다. 코드 # https://www.acmicpc.net..

취직 혹은 이직은 누구에게나 힘든 일일 것이다. 나 또한 처음 취준을 하던 시기와 이직을 하던 시기에 많이 힘들었던 기억이 난다. 지금 생각해도 정말 돌아가고 싶지 않을 정도로. 시간이 지나고나서 든 생각은 누군가가 나에게 어떠한 마인드로 준비를 하면 되는지라던가 소소한 팁들을 알려주었다면 준비하는 기간이 조금은 더 짧아질 수도 있지 않았을까였다. 취업이나 이직을 준비하는 누군가에게 도움이 될까하는 마음으로 느꼈던 몇가지를 적어본다. 1. 되도록 많은 곳에 지원해라 취직은 결국 "전략" 싸움임을 인지하는 것이 중요하다. 주변에서 "딱 한군데만 지원했는데 운 좋게 붙었어요."와 같은 말을 들어본 적이 있을 것이다. 좀 배가 아프지만 채용이라는게 사실 그렇다. 나는 이 사실을 알기까지 굉장히 많은 시간이 걸..

문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 나의 풀이 그냥 n개의 원소 중 임의의 3개를 뽑아서 합을 구하는 방식으로 하게 되면 시간복잡도가 O(n^3)까지 올라가게 된다. 따라서 투 포인터를 사용해서 O(n^2)으로 풀어야 통과할 수 있다. i를 0~n-2까지 순회하면서 left와 right를 바꿔주어야 한다. 아래 코드는 python으로는 시간초과가 나왔고 pypy로 통과하였다. 서치를 해보니 대부분의 해답들..