본문 바로가기

C++

 (173)
[프로그래머스/C++] k진수에서 소수 개수 구하기 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr k진수에서 소수 개수 구하기 문제 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된..
[프로그래머스/C++] 배달 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 배달 문제 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을..
[알고리즘] 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm) 눈앞의 이익만 좇는 선택을 반복하는 알고리즘이다. 그리디 알고리즘은 당장의 경우에는 최적의 경우일지라도, 결과는 대부분 최적이 아니다. 그렇지만 드물게 최적의 답을 보장해주는 경우가 있다. 해가 만들어 질 때 까지 가장 좋아 보이는 선택을 하는 것을 반복한다. 그리디 알고리즘은 이미 앞에서 사용되었다. 바로, 최소 신장 트리를 구할 때 사용한 프림 알고리즘과 크루스칼 알고리즘이다. 또한, 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장되는 예들 중 하나이기도 하다. 그러나 이 둘이 특별한 경우이고 대부분의 경우에는 최적의 해를 보장하지 못한다. 아래와 같은 예시를 보자. 1. 이진 트리의 그리디 탐색 이진 트리에서 리프 노드를 만날 때 까지 방문한 노드..
[C++/STL] deque (덱) deque는 입력과 출력이 양쪽 끝에서 이루어지는 자료구조입니다. 큐와는 다르게 뒤에서 삭제가 가능하고 앞에서 입력이 가능합니다. 뒤에서만 입력과 출력이 가능한 스택과 달리 앞에서도 입력과 출력이 가능합니다. 그러나, 벡터와는 달리 내부 요소들이 연결만 유지한 상태이기에, 다른 공간에 흩어져 존재할 수도 있습니다. 이러한 덱을 C++에서 라이브러리로 제공합니다. #Include #include template class deque; 선언 방법 deque d1; // 빈 int형 덱 deque d2(4,100); // 4개의 100을 기본으로 넣은 덱 deque d3(d2.begin(), d2.end()); // d2의 반복자 deque d..
[프로그래머스/C++] 숫자의 표현 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/12924 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 숫자의 표현 문제 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개..
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 다음과 같은 도시들과 그 도시들끼리 이어주는 도로망이 있다고 해보자. A 도시에서 F 도시를 방문한다고 하자. 최단 거리를 찾아서 방문한다면 시간이 절약될 것이다. 그러므로, C 도시를 거쳐서 F 도시로 가는 것이 가장 짧은 경로이다. 이때의 거리는 도로의 길이의 합이 가장 짧은 60km가 된다. 가중치 그래프에서도 마찬가지이다. 한 정점 v에서 각 정점들까지의 최단 경로를 구하고자하는 경우가 있다. v에서 각 정점까지의 가중치들을 더하고, 그 가중치가 가장 작으면 최단 거리가 된다. 이렇게 한 시작 정점 v에서 모든 다른 정점들 까지의 최단 경로를 구하는 알고리즘이 다익스트라 알고리즘(Dijkstra Algorithm)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다. ..
[C++/STL] vector (벡터) C/C++에서의 배열은 한 번 선언해주면 크기를 바꿀 수 없습니다. 그래서 C언어에서는 malloc 함수를 통해서 가변 배열을 만들어줘야 했습니다.(비슷하게 C++도 new 연산자를 사용해 동적 할당으로 가변 배열을 만들 수는 있습니다.) 하지만, C++에서는 편리하게 클래스에서 가변 배열을 지원해줍니다. 그것이 vector 입니다. 이 vector에 대해서 알아보겠습니다. #include vector는 vector헤더파일을 선언해야 사용할 수 있습니다. #include template class vector; 선언 방법 vector v1; // int형의 빈 벡터 vector v2(3); // 크기를 3, 초기 값으로 0을 설정한 벡터 ..
[프로그래머스/C++] 올바른 괄호 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 문제 제목 문제 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻..

티스토리툴바