어흥

문제 링크: https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 주의할 점 - 연속된 부분의 누적 합에 대해 알고 있어야 한다 - O(N^2)보다 작은 알고리즘을 구현해야 한다 - 답이 int 범위를 벗어날 수 있다 2. 구현 - 나머지가 M으로 나눠떨어지는 누적합은 2가지의 방식이 존재한다(파란 글씨 + 빨간 글씨) - 값을 입력받으며, Sum[] 함수에 연속된 누적합을 M으로 나눈 값을 저장..

문제 링크: www.acmicpc.net/problem/1821 1821번: 수들의 합 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있 www.acmicpc.net 1. 주의할 점 - 파스칼의 삼각형을 통해 공식을 유추할 수 있어야 한다 2. 구현 - 수가 N이면, n-1C0부터 n-1Cn-1까지 총 N개의 수가 나온다. 해당 수들이 위에 배치될 숫자가 나타난 횟수다 - 조합 값을 저장해놓기 위해 Factorial[] 배열을 통해 0!~9!사이의 수를 저장한다 - setMul() 함수를 통해 n-1C0~n-1Cn-1값에 해당하는 값을 Mul[] 배열..

문제 링크: programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 1. 주의할 점 - 불량사용자와 매칭된 사용자는 탐색할 수 없어야 한다 - 예제 2번과 같이 순서가 같지만 사용자는 같으므로 순열이 아닌 조합이다 2. 구현 - 불량사용자와 매칭된 사용자들이 오름차순으로 정렬하여 Set에 저장하여 조합의 수를 구하도록 한다 - DFS(idx)를 통하여 idx번째 불량사용자와 매칭되는 i번째 사용자를 구한다 - 사용자와 매칭되려면,..

문제 링크: www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Sherlock and Anagrams | HackerRank Find the number of unordered anagramic pairs of substrings of a string. www.hackerrank.com 1. 주의할 점 - substring 길이에 따라 다른 Map에 저장한다 - 정렬을 이용한다 2. 구현 - 최대 길이 100까지 담을 수 있는 Map[]을 생성한다. Map은 형태로..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 바꿀 열을 정한다. 단, 바뀌는 열의 색이 모두 같다는 보장이 없다(최근에 TC가 추가되어 이 부분을 구현 안했다면 50번째에서 틀릴 것이다) 2. 구현 - 바꿀 열의 개수 I개를 정하고, 바꿀 열의 위치를 구한다. - 열의 위치를 정한 후, 해당 열을 어떤 색으로 바꿀지 DFS를 수행하며 Color 벡터에 저장한다. 이후, Change() 함수를 수행한다 - 바꾸는..

문제 링크: https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 1. 주의할 점 - 소수점 12자리 출력 - cout > num; result = 9223372036854775807; for (int i = 0; i > x[i] >> y[i]; } vector v; for (int i = 0; i < num / 2; i++) v.push_back(0); for (int i = 0; i < num / 2; ..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 조합, DP를 통한 풀이 방법이 있지만, DP(메모아이징)를 통해 해결한다 - 시작 전, DP[][]의 값을 전부 초기화한다 2. 구현 - DP[Idx][Remain] 배열을 통해 해당 Idx의 위치에서 Remain만큼 남은 칼로리가 있을 때, 얻을 수 있는 가장 큰 점수를 저장한다 - Knapsack 알고리즘을 통해 해당 'Idx의 위치에 있는 재료를 추가해서 얻을..

문제 링크: https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 1. 주의할 점 - 팀원을 생성할 수 없는 경우 -1을 출력한다 - 2^N -1(N이 최대 10)만큼 만들 수 있는 팀원 경우의수를 모두 구할수 있어야 한다(2^N 이상으로 구하면 어떤 경우에서 시간초과가 발생할 수 있다) 2. 구현 - 팀원 1명, 2명, 3명,....N명일 때 만들 수 있는 조합의 수를 따진다. 전부 구해도 nC1 + nC2 + nC3 +... +nC..