본문 바로가기

개발 관련 기타/알고리즘

 (20)
[백준 BOJ] C++) 1605번: 반복 부분 문자열 문제 링크 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 예제 이해 예제) tellmetellmetetetetetetetellme 의 부분문자열의 길이가 11이라고 한다 길이 11의 부분문자열을 찾는데 애를 먹었다 찾은 부분 문자열은 etetetetete 이다. 그 이유는? 풀이 접근 방식 길이 L의 부분 문자열을 찾는다. 부분 문자열을 찾고 없으면 길이 L-1의 부분 문자열을 찾는다. 소스 코드 (1차..
[프로그래머스] (C++) 야근지수 문제 링크 코딩테스트 연습 - 야근 지수 | 프로그래머스 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. 제한 사항 works는 길이 programmers.co.kr 생각해볼만한 점 가장 큰 works의 값부터 1 씩 줄여가면 되지 않을까? 결국 가장 작은 값 (최소화한 값) 이란 제곱하는 베이스가 평균적으로 가장 작게 나오는 ..
[프로그래머스] (C++) 이중우선순위큐 문제 링크 힌트 우선순위큐는 minHeap 또는 maxHeap 을 사용한다 이중우선순위큐는 minHeap과 maxHeap을 둘 다 사용하는 방법을 생각해보자 소스 코드 (1차 시도) #include #include #include #include using namespace std; vector solution(vector operations) { vector answer{0, 0}; priority_queue maxHeap; priority_queue minHeap; for (auto iter = operations.begin(); iter != operations.end(); iter++) { char action = iter->at(0); int num = stoi(iter->substr(2, st..
[프로그래머스] (C++) 방문길이 문제 링크 힌트 이미 간 곳에 대한 정보를 어떻게 저장해야 갈 수 있는 곳에 대한 정보를 쉽게 얻을 수 있을까? 어디에서 어느 방향으로 갔는지를 저장하면 되지 않을까? 소스 코드 // [프로그래머스] 방문 길이 #include #include #include #include #include int solution (std::string dirs) { int answer{0}; std::pair lastPos, nextPos; std::vector U, D, L, R; lastPos.first = 0; lastPos.second = 0; for (int i = 0; i < dirs.length(); i++) { if (dirs[i] == 'U') { if (lastPos.second == 5) contin..
[BOJ] (C++14) 2458번 문제) 키 순서 문제 링크 누가 누구보다 크다는 키 순서 쌍을 받아오면 이 키 순서 쌍을 토대로 누가 몇번째로 큰지 확실히 알 수 있는 사람의 수 힌트 플로이드-워셜 알고리즘을 쓰면 노드에서 다른 노드를 거쳐 가는 길까지 다 구할 수 있다 순서를 확실히 알 수 있는 사람: 자기보다 큰 노드의 수 + 자기보다 작은 노드의 수 = 모든 노드의 수 - 1 을 구할 수 있는 사람 플로이드-워셜 알고리즘 // vertex가 N개 있을 때 // i부터 j까지 edge의 유/무 및 weight 값은 matrix로 저장됨 // int graph[i][j]가 존재 한다고 가정 for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ..
[프로그래머스] (C++) 순위 문제 링크 코딩테스트 연습 - 순위 | 프로그래머스 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 힌트 어느 노드를 통해서 다른 노드에 다달를 수 있는데 그때 사용하는 것이 플로이드-워셜 알고리즘이다. 자신에게 올 수 있는 노드의 수와 자신이 갈 수 있는 노드의 수의 합이 N-1 일 때 확실히 자신의 순위를 알 수 있다. 소스코드 #include #include #include using namespace std; int solution(int n, vector results) { int answer{0}; // 플로이드를 써서 다른 vertex를 거쳐서라도 갈 수 있으면 edge 값 update // 나보다 큰 수 + 나보다 작은 수 =..
[프로그래머스] (C++) 매칭 점수 문제 링크 힌트 머리 (HEADER)에서 추출 해야 할 값 그리고 몸 (BODY)에서 추출 해야 할 값을 나누어 보자. 소스 코드 (1차 시도) #include #include #include #include #include #include #include using namespace std; int solution(string word, vector pages) { int answer = 0; int pageNum = pages.size(); vector pageNames; vector matchingScores; vector linkScores; vector stdScores; vector linkNums; vector linkScoresToOther; vector linkedPagesList; //..
[프로그래머스] (C++) 숫자 게임 문제 링크 힌트 정렬을 이용하자. 소스 코드 (1차 시도) // [프로그래머스] 숫자 게임 #include #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; std::sort(A.begin(), A.end()); std::sort(B.begin(), B.end()); vector::iterator B_iter = B.begin(); for (vector::iterator iter = A.begin(); iter != A.end(); iter++) { while (B_iter != B.end()) { if (*B_iter >= *iter) { answer++; B_iter++; b..

티스토리툴바