코드 낙서장

C++ 에는 절댓값을 구할 수 있는 함수 abs 함수가 있습니다. abs - C++ Reference 12345678910111213 /* abs example */ #include /* printf */ #include /* abs */ int main () { int n,m; n=abs(23); m=abs(-11); printf ("n=%d\n",n); printf ("m=%d\n",m); return 0; } www.cplusplus.com 이 함수를 이용하게 되면 함수 호출에 대한 페널티를 받기 때문에 if 혹은 수의 특성을 이용해서 구해 시간을 줄일 수 있습니다. #define bit_abs(x) ~x + 1 정수형인 int, long long의 경우 왼쪽 끝의 비트가 부호를 나타내므로 0x80..

1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 문제 확인 수학을 사용해서 푸는 문제입니다. 풀이 bool 배열은 char와 마찬가지로 1byte를 사용하기 때문에 메모리 사용량이 적은 bitset 객체를 사용합니다. 조건에 따라 모든 수의 비트를 만들순 없기 때문에 min ~ max 간격의 최댓값인 1000001개의 비트를 만듭니다. min ~ max 사이에 있는 수에 각각 비트를 할당하고 각 수는 index - a 위치에 저장됩니다. 초기값은 false, 0입니다. 제곱수 4, 9, 16,..

2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제 확인 원형 큐 자료구조 형식을 응용하는 문제입니다. 모든 짚신벌레를 관리하면 메모리 초과가 일어나며 a, b, d를 고정시키고 배열을 움직이게 되면 연산이 많아져 시간 초과가 납니다. 따라서 배열의 값 대신 a, b, d를 인덱스로 이용하여 풀어야 합니다. 풀이 문제에서 주어진 d 값을 이용해 원형 큐 배열을 만듭니다. d는 최대 10000이며 이를 넘을 시 짚신벌레는 죽기 때문에 배열을 ary[10001]로 선언합니다. 초기 배열을 [1, 0, 0, ...] 으로 초기화해주고 a, b, ..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 문제 확인 dfs, 그리디로 풀 수 있지만 depth가 깊어지면 stack의 모든 상황을 확인하기 때문에 느리므로 트리 dp로 풉니다. 풀이 dp 배열을 dp[현재 노드 번호][선택 상태]로 둡니다. 선택 상태는 현재 노드가 워크숍에 참가 여부로 두고 조건을 고려합니다. dp[cur_idx][0] : 현재 노드가 워크숍에 참가하지 않을 때 팀의 최소비용, 자식 노드 중 하나 이상 워크숍에 참가가 필요합니다. dp..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제 확인 초로 환산했을 때 최대 크기가 360000이므로 배열과 prefix sum을 이용하여 풀 수 있습니다. 풀이 들어오는 string은 모두 길이가 고정이므로 간단하게 시간과 정수로 변환하는 함수를 만들어 활용합니다. log가 시작되는 지점에 +1, 끝나는 지점에 -1을 해 두고 이들을 prefix sum을 구하여 각 시간마다 시청하는 사람의 ..

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 확인 트리 dp 문제입니다. 풀이 그래프를 입력받아서 작성하고 dfs를 통해 dp 값을 채워 넣어주면 됩니다. 자신을 포함하여 서브트리의 정점 개수이므로 초기값은 1로 설정을 하고 자식들의 dp값을 합쳐주면 결과를 얻어낼 수 있습니다. for(auto child : cur.edge) if(child != prev) dp[cur] += dfs(child, cur); prev 값은 되돌아가는 것을 방..

1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 문제 확인 문자열 혹은 숫자 자릿수를 활용하는 문제입니다. 풀이 간략한 풀이를 위해 입력을 문자열로 받습니다. 최대의 숫자를 만들기 위해서는 몇 가지를 고려해야 합니다. 맨 앞자리는 1~9 중 재일 높은 수가 나와야 합니다. 모든 수를 고르고 난 후 남은 n-k개의 수는 가장 긴 자릿수 중 재일 높은 수를 선택해야 합니다. 1번을 고려할때 주의해야 할 점은 91, 9 의 경우9/91이 더 높은 숫자를 만들 수 있는 것입니다. 이를 위해..

문제 주소 : www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 문제 확인 문자열과 정렬을 이용해서 풀 수 있습니다. 풀이 입력받을 시 문자열 다음에는 공백 혹은 \0이 입력되고 이를 구분해서 풀 수 있습니다. fgets를 통해 한번에 문자열 집합을 입력받고 qsort 함수를 통해 정렬을 합니다. qsort 정렬 시 strcmp 함수를 통해 같은 굴에서 뻣어가는 굴일 경우 교차점 이전까지 문자가 모두 같기 때문에 사전 순서대로 정렬됨을 이용합니다..

문제 주소 : www.acmicpc.net/problem/2983 2983번: 개구리 공주 트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르 www.acmicpc.net 문제 확인 링크로 연결해서 풀 수 있지만 링크를 사용하는 것 자체가 인덱싱에 비하여 느리므로 그래프 형식으로 인덱스를 저장해서 풀었습니다. 풀이 개구리는 4방향 (P, P), (-P, -P), (-P, P), (P, -P) 방향으로 점프를 하기 때문에 x, y축에 대하여 식을 새워 다음과 같이 m값으로 나타냅니다. 따라서 점 x, y에서 특정 방향으로 이동하기 위해서는 x, y와 움직일 위치가 같은 m..

문제 주소 : www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 확인 트리에서 dp 문제입니다. 얼리 어답터인 경우 친구는 얼리 어답터이거나 아닐 수 있지만 자신이 얼리 어답터가 아닌 경우 친구 중 한 명은 꼭 얼리 어답터이어야 함을 이용합니다. 이 말은 즉 자신의 모든 친구가 얼리 어답터가 아니라면 자신이 얼리 어답터가 돼야 함을 의미하고 반대로 모든 친구가 얼리 어답터라면 나 자신은 어답터일 필요가 없습니다. 풀이 depth 조절과 효율성을 위해..