분류 전체보기
프로그래머스 - 큰 수 만들기
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 처음에는 최대 길이가 백만이어서 O(n^2) 을 피하기 위해 투 포인터를 쓰면서 k 만큼 구간을 잘라서 벡터에 넣은뒤, 최대 값을 구하려고 했으나, 코드가 난잡해지고, 오류가 많이 났다. 그래서 다른 사람의 코드를 보고 훨씬 더 간단한 방법을 보게 되었다 부분 구간을 잘라서 넣는게 아니라, 그냥 처음 부터 가장 큰 값을 찾아내서, 거기서부터 시작하여 k 개를 만들어 내면 되었다. (백준이나 코포 같은 다른 사이트의 문제도 그렇고 문제에서 제시하는 있는 그대로 구현하기 보다는 최대한 단순하게 생각해보는게 첫번째로 중요한듯 하다.) - c++ #includ..
프로그래머스 - 카카오프렌즈 컬러링북
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 DFS, BFS 를 이용하여 답을 찾는 전형적인 문제이다. 백준 2667 단지 번호 붙이기 문제와 상당히 유사한 문제이다 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 ..
프로그래머스 - 프린터
programmers.co.kr/learn/courses/30/lessons/42587?language=cpp# 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 1. 우선순위 큐를 이용해 높은 수가 앞으로 오도록 한다 (기본 max heap) 2. 큐를 pair 타입으로 선언하여 인덱스와 값을 갖도록 해준다 3. 큐에서 하나씩 빼내고, 우선순위 큐의 top 과 동일한 값이면 우선순위가 일치하는 것이므로 카운팅을 하나 늘리고, 만약 그 일치하는 값의 인덱스 마저도 같으면 문제에서 요구하는 값이므로 리턴시킨다. 4...
순열
코딩테스트의 주요 유형 중 하나인 브루트 포스를 풀때, 순열(Permutation) 개념을 이용하면, 필요한 모든 경우의 수를 구할 수 있을때가 있다. C++ 에서는 Algorithm 헤더 파일에 next_permutation 과 prev_permutation 함수가 제공된다. - next_permutation() template bool next_permutation( BidirIt first, BidirIt last ); cs next_permutation 은 위와 같은 형식을 따르며, 리턴 타입은 bool 이다. - 예시 코드 #include using namespace std; int main() { vector v(4); for (int i = 0; i
BOJ 10816 - 숫자 카드 2
www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net - c++ #include #define MAX 10000000 using namespace std; int arr[MAX * 2 + 1]; int n, m; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; for (int i = 0; i > num; if (num > m; for (int i = 0; i > ..
C++ STL 정리 - 정렬
C++ 의 알고리즘 라이브러리에서 제공되는 정렬은 3가지가 있다 1. sort() : 퀵소트를 기반으로하는 일반적인 정렬 방식이다. sort() 함수 사용시 주의할 점은 RandomAccessIterator 타입만 사용이 가능하다 STL 의 컨테이너 중 Vector, Deque 만 사용 가능하다. 다른 타입의 컨테이너를 사용하면 오류발생. - 기본연습문제 1. 수 정렬하기 2 www.acmicpc.net/problem/2751 (예시 코드) #include #define endl "\n" using namespace std; int n; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; vector vec(n, 0); for (int i ..
BOJ 15683 - 감시
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net - c++ #include #define endl "\n" #define INF 987654321 using namespace std; int n, m, cntMin = INF; int board[8][8]; vector cameraPos; // y, x, camera number const int dirType[5] = {4, 2, 4, 4, 1}; // direction type void copy..
BOJ 18808 - 스티커 붙이기
www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net - c++ #include #define endl "\n" using namespace std; int n, m, k, r, c; // board y, board x, number of sticker, sticker y, sticker x int nr, nc; // new y, new x (turn direction) int board[40][40]; vector copySticker; int cntSticker..