본문 바로가기

분류 전체보기

 (233)
[프로그래머스/C++] 가장 큰 정사각형 찾기 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/12905# 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 가장 큰 정사각형 찾기 문제 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사..
[프로그래머스/C++] 카카오 프렌즈 컬러링북 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 카카오 프렌즈 컬러링북 문제 카카오 프렌즈 컬러링북 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장..
[프로그래머스/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)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다. ..

티스토리툴바