오뚝이개발자

문제 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/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로 통과하였다. 서치를 해보니 대부분의 해답들..

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 나의 풀이 dp를 사용하면 된다. dp 2차원 리스트에 각 위치에는 (0,0)부터의 부분합을 저장한다. 주황색 부분의 부분합을 구하려면 전체 합에서 A, B, C 부분을 빼주면 된다. 식으로 나타내면, (x2,y2)까지의 부분합 - (A+B) - (A+C) + A 가 된다. A부분이 두번 빼지니까 마지막에 한 번 더 더해주면 된다. 코드 # http..

문제 https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b3a1c Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 단순히 brute-force 방식으로 풀면 시간 초과 에러가 난다. 이 문제에서 핵심은 search를 어떻게 효율적으로 할 것인가..

문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d9a88#problem Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 문제가 조금 복잡하지만 구현 자체는 생각보다 단순하다. d = {'R':['R'], 'B':['B'], 'Y':['..

문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008da461 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 단순한 구현 문제이다. 우선 F를 set으로 바꿔주어야 한다. 어차피 우리가 필요한 것은 S에 F의 글자가 있는지만 확인하면 되니..

문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 나의 풀이 사실 처음엔 itertools 모듈의 중복조합을 사용해 구했다. 물론 답은 맞았지만 조금 더 nice해 보이는 코드가 있어 첨부한다. 이 문제는 브루트 포스 문제로 그냥 가능한 경우를 모두 카운트 해주면 된다. 문제에서 주어진 조건 중 1000이하의 자연수만 입력으로 주어진다고 했기 때문에 1000 이하의 모든 유레카 수를 구해두면 된다. eureka라는 flag 배열을 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 나의 풀이 dp를 사용하면 되는 문제이다. 케이스는 두 가지이다. 첫 번째 스티커를 사용하는 경우와 사용하지 않는 경우이다. 따라서 dp1,dp2 두 개의 dp 배열을 만들어 저장하면 된다. dp1의 경우 첫 번째 스티커를 사용하므로 dp1[0] = sticker[0], dp1[1] = dp1[0]이다. dp2의 경우 첫 번째 스티커를 사용..