마탁이의 개발 블로그

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 최소값을 구해야 한다는 것에 초점을 맞추면 풀 수 있다. 내가 구현한 코드는 남들보다 코드 길이는 길었지만 (C++만 사용하던 사람이라는 변명...) 속도는 64ms로 조금 빠른 편이다. 더보기 inputData = list(input()) parsedList = [] number = '' for data in inputData: if '-' != data and '+' != data: nu..

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

리눅스에서 무선랜 인터페이스를 통해 주변의 Wifi를 검색하여 목록을 출력하는 기능을 구현 중, ssid가 한글이면 uft8 코드로 출력되었다. 한글 1개의 문자는 총 3개의 utf8 코드로 구성되어있으며 이를 잘 활용하면 식별할 수 있는 한글 문자(?)가 된다. 실제 기능을 구현할 때는 한글 중간 특수문자를 포함한 다양한 문자가 사이사이 올 수 있음에 주의한다. 크기 3의 char[]을 사용해 각 char 마다 utf8 코드를 넣어 한 개의 String으로 출력하였다. 아래 코드는 실제 QT Project에서 사용한 일부분이다. char hangulBuf[4] = {0,}; int hanIdx = 0; foreach (const QString& item, srcSplit) { if('x' == item..

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()는 인접한 ..