마탁이의 개발 블로그

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그냥 for문으로 loop를 순회하면 시간 초과가 발생한다. 따라서 몫을 구해 계산한다. 더보기 nk = list(map(int, str(input()).split())) N = nk[0] K = nk[1] costList = [] for idx in range(N): cost = int(input()) if(cost

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘을 생각하며 해결하면된다. 단계별로 풀어보기의 그리디 알고리즘 중 가장 간단한 문제이다. 더보기 N = int(input()) PList = list(map(int, str(input()).split())) PList.sort() answer = 0 timeSum = 0 for time in PList: timeSum += time answer += timeSum print(answer)

https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 파이썬에서는 간단히 2진수로 나타낼 수 있었기 때문에 빨리 풀 수 있었다. 더보기 def calc(answer, n, arr): for i, item in enumerate(arr) : binList = list(str(bin(item).replace('0b', ''))) convertedList = [0 for idx in range(n)] conver..

https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 처음에는 각 번호 별로 score를 1 ~ 7 까지 점수를 지정해 식으로 풀려고 했으나 잘 풀리지 않아 dictitonary를 이용해 풀었다. 충분한 속도가 나오고 카카오에서는 lv1이면 1번문제이니 너무 많은 시간을 낭비하지 않도록 한다. 더보기 de..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 재귀를 이용한 백트래킹을 사용해야 풀 수 있는 문제다. 나는 문제를 풀었지만 452ms 가 나왔고 채점 현황에서 다른 사람들과 비교했을 때 매우 느린 수준이다. 따라서 다시 문제를 분석하여 코드를 개선할 필요가 있다. 나는 0이 나오는 위치를 pair로 저장하여 사용했다. 가장 예제로 좋은 것은 9 x 9 의 칸이 모두 '0' 일 경우 일까? 더보기 #include #include #include..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 재귀를 이용해 간단히 풀 수 있다. 연산자 갯수를 저장하는 배열을 만들고 연산자의 개수가 N-1개 주어진다는 점을 활용한다. 더보기 #include #include #include #include #include #define N_MAX 11 int N; int operatorArr[4]; // +, -, *, / int maxValue; i..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 푸는 방법에는 재귀, 순열, 비트 마스킹 3가지가 존재한다. 나는 재귀를 이용해서 풀었으며 star 팀을 N/2 될 때까지 먼저 구한 후 link팀을 구하여 값을 계산하였다. 더보기 #include #include #include #define N_MAX20 int N; int minValue; bool checkArr[N_MAX + 1] = { false, }; std::vector inputList; std::ve..

www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 처음에 보기에 설명이 부족하네? 라고 생각했지만 예제 2개를 보고 정렬 단계에서 제공되는 문제라는 것을 생각하여 풀었을 시 답이 쉽게 나온다. 1024ms가 나왔는데, 다른 사람들은 더 빠르게 푼 Case들이 많아 다시 풀어봐야한다. std::sort()와 std::unique()로 vector의 중복을 제거 할 수 있다. - std::unique()는 인접한 ..

programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 에라토네스의 체를 이용해야 효율성 채점을 통과할 수 있다. 에라토네스의 체는 아래와 같은 구조로 코드를 구현한다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (자기 자신은 지우지 않는다.) 2부터 시작하여 지우지 않은 수를 출력한다. 더보기 #include #include using namespace s..

programmers.co.kr/learn/courses/30/lessons/12915 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers.co.kr 간단히 char 를 int로 생각하여 비교하면 될 문제지만 만약 같다면 사전순으로 정리하는 문제이다. 사전순으로 정리하는 것에서 조건을 정확히하면 쉽게 풀 수 있다. 더보기 #include #include #include using namespace std; vector solution(vector strin..