본문 바로가기

Algorithm39

Graph partitioning problem ProblemDivide a network of data centers into optimal local regions.Given a network of g_nodes data centers and g_edges bidirectional connections, the i-th connection connects data centers g_from [i] and g_to(i) with a latency of g_weight[i]. The max_latency of a network is the maximum latency of any connection.Divide this network into k or fewer networks by removing some of the connections such .. 2025. 4. 1.
[C++, 완전탐색] 프로그래머스 양궁대회 문제 https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 풀이 완전탐색 문제이다. 총 11개의 점수(0점 ~ 10점) 에서 라이언이 해당 점수를 선택하냐 선택하지 않느냐로 나눌 수 있다. 구현이 쉬운 dfs로 풀이하였다. 해당 문제에서 주의해야 할 점이 있다. 문제를 꼼꼼히 읽어보면 알 수 있는데 예시에도 나와있듯이 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 .. 2022. 4. 7.
[C++, 문자열, 슬라이딩 윈도우] 프로그래머스 추석 트래픽 문제 https://programmers.co.kr/learn/courses/30/lessons/17676 2022. 4. 5.
[C++, 문자열] 프로그래머스 오픈채팅방 문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 해답 Stringstream과 hash를 이용해 풀이하였다. #include #include #include #include #include using namespace std; unordered_map nameMap; class tans{ public: string ac; string h; }; vector solution(vector record) { .. 2022. 4. 4.
[C++, 문자열] 프로그래머스 다트게임 문제 https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 해답 stringsteam을 잘 활용하니 parsing을 쉽게 할 수 있었다. #include #include #include #include using namespace std; int solution(string dartResult) { stringstream ss(dartResult); int answer = 0; int answerList[3] = { 0, }; int strIdx = 0; for (int i = 0; i < 3; i++) { //parsing int score = 0; char bonus = 0, opt.. 2022. 3. 31.
[C++, 문자열] 프로그래머스 신규 아이디 추천 문제 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 해답 문자열 연습하기 정말 좋은 문제라고 생각한다. 해답 밑에 해답에서 사용한 std 함수들을 간략하게 설명하였다. #include #include #include using namespace std; string solution(string new_id) { //1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. for (int i .. 2022. 3. 23.
<Algorithm,C++> Merge Sort (병합 정렬, 합병 정렬) 개념, 구현예제 Merge Sort 는 유명한 정렬 알고리즘 중에 하나입니다. 최악의 시간복잡도가 O(n log n)라는 점 때문에 실제 알고리즘 문제에서도 많이 사용됩니다. stable sort(안정 정렬, 같은 우선순위의 값에 대해 정렬 전후 순서 동일) , 메모리가 2배로 든다는 점이 특징입니다. 다른 개념적인 설명은 뒤로하고 여기선 오로지 외워서 사용하기 편한 방법을 하나 소개합니다. 톱다운으로 구현한 방법입니다. #include #define MAX 10 int tmp[MAX]; using namespace std; void mergeSort(int arr[], int s, int e) { //base condition if (s >= e) return; //divide int m = (s + e) / 2; /.. 2021. 2. 16.
[C++, 세그먼트 트리, 데이터추가 반영] 백준 2042번 구간 합 구하기 www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 21.02.17 데이터 추가 반영하였습니다. 세그먼트 트리의 입문문제라고 할 수 있다. 따라서 세그먼트 트리 초보자에게 구현이 간편한 방법을 소개하고자 한다. update함수와 query함수 단 2개의 함수만 이용해서 해결할 수 있는 방법이다. 세그먼트 트리 초기화를 update문을 이용해서 구현하면 실행시간은 늘어나지만 구현이 간편해진다는 장점이 있다.. 2020. 11. 22.
[C++,구현, 중복 순열] 백준 17825번 주사위 윷놀이 문제풀이 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위 윷놀이, 구현에서도 어려운 축에 속한다고 생각한다. 주사위에서 나올 수 있는 10개의 수 순서에 각각 4개의 말들을 매칭 시킨다고 하면 중복 순열이다. 전체의 경우의 수는 4^10 가지가 나온다. 처음에는 아래와 같이 풀이하였다. #include #include using namespace std; typedef struct lo { int x, y; }; int pan[4][30] = { { -1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 3.. 2020. 6. 1.
최소 신장 트리 (MST , Minium Spanning Tree) 최소 신장 트리(MST, Minium Spanning Tree) 신장 트리 중에서 간선의 가중치의 합이 최소인 것 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 연결한 트리 신장 트리의 특징 모든 노드는 서로 연결되어 있다. 간선(edge)의 수 E는 노드의 수 V에서 1을 뺀 것과 같다. 트리(Tree) 그래프의 일종으로 사이클이 없는 연결그래프이다. 트리의 특징 root node를 제외한 모든 node는 단 하나의 부모 node만 가진다. 임의의 노드에서 다른 노드로 가는 경로는 유일하다. 회로(cycle)가 존재하지 않는다. 간선(edge)를 하나 자르면 트리가 두 개로 분리된다. 최소 신장 트리 구현 방법 Kruskal 알고리즘 탐욕적인 방법(greedy method)을 이용해 M.. 2020. 5. 25.
빅-오 표기법 (Big-Oh Natation), 시간 복잡도(Time Complexity) 시간 복잡도란?문제를 해결하는데 걸리는 시간과 입력의 함수 관계해당 알고리즘이 얼마나 효율적인지 정량화해 나타내는 지표빅-오 표기법이란?입력값에 따른 알고리즘의 실행 시간 성장률(시간 복잡도)을 점근적 상한선으로 나타낸 수학적 표기법 해당 알고리즘의 성능을 나타내기 위해선 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다.입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아볼 필요성이 있습니다. 이것을 실행 시간의 성장률(rate of growth)이라 합니다.성장률에서 상수 계수와 중요하지 않은 항목을 제거한 것을 점근적 표기법(asymptotic notation)이라 합니다.big-Θ중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실.. 2020. 5. 14.
vector, unordered_map 전체 순회 알고리즘 속도 비교 vector는 배열을, unordered_map은 hash_table를 사용해 hash를 구현한 모두 유명한 자료구조 컨테이너이다. unordered_map의 탐색 시간 복잡도는 O(1)이다. 그렇다면 전체 순회의 경우 vector와 비교할 때는 어떻게 될까? 단순히 시간복잡도만을 계산하면 둘 다 O(n)인데 어떤 것이 더 빠를까? 직접 해보자 #include #include #include #include #define COUNTER 1000000 int main() { using namespace std::chrono; // std::chrono::milliseconds is an instatiation of std::chrono::duration: int tmp; std::vector v; std:.. 2020. 5. 3.

티스토리툴바