본문 바로가기

Algorithm38

[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.
[C++, Hash] 프로그래머스 베스트앨범 문제 풀이 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play programmers.co.kr 풀이 참고하지 않고 스스로 한 번에 풀어서 더욱 뿌듯한 문제이.. 2019. 12. 12.

티스토리툴바