[코딩테스트 / c++] 봉우리, 이차원 배열 활용

문제 지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다. ▣ 입력설명 첫 줄에 자연수 N이 주어진다.(1

[코딩테스트 / c++] 멀티태스킹(카카오 먹방 문제 변형)

2019년 카카오 코딩테스트 무지의 먹방라이브 문제를 변경한 문제입니다. https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제 현수의 컴퓨터는 멀티태스킹이 가능하다. 처리해야 할 작업이 N개 들어오면 현수의 컴퓨터는 작업을 1부터 N까지의 번호를 부여하고 처리를 다음과 같이 한다. 1) 컴퓨터는 1번 작업부터 순서대로 1초씩 작업을 한다. 즉 각 작업을 1초만 작업하고 다음 작업을 하는 식이다. 2) 마지막 번호의 작업을 1초 했으면 다시 1번 작업으로 가서 다시 1초씩 후속 처리를 한다. 3) 처리가 끝난 작업은 작업 스케쥴에서 사라지고 새로운 작업은 들어오지 않는다. 그런데 현..

[코딩테스트 / c++] 백준 1158 요세푸스 문제

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 유사한 문제를 풀다가 백준에 비슷한 문제가 있어서 연습삼아 풀어보았다. 요세푸스는 조세퍼스라고도 하며 순열을 가리킨다. > 요세푸스 유사문제 포스팅 https://meongj-devlog.tistory.com/201 [코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제 문제 풀이 #include #include #include using namespace std; int main(){ int n, k, pos=0, bp=0, cnt=0, i; scanf("%d %d", &n, ..

[코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제

문제 풀이 #include #include #include using namespace std; int main(){ int n, k, pos=0, bp=0, cnt=0, i; scanf("%d %d", &n, &k); vector prince(n+1);//0으로 초기화 while(1){ pos++; if(pos>n) pos=1;//pos=9일 경우 1로 pos초기화 if(prince[pos]==0){ cnt++; if(cnt==k){ prince[pos]=1;//out cnt=0; bp++;//n-1명 out명수 체크 } } if(bp==n-1) break; } for(i=1; i

[알고리즘] 병합정렬(Merge Sort)의 개념 with c++

병합정렬 또는 합병정렬은 정렬할 데이터들을 일단 반으로 쪼개고 각 각 정렬한 후 나중에 합치는 알고리즘이다. 비교 기반 정렬 알고리즘이고, 일반적인 방법으로 구현했을 때 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다. 매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적인 문제가 있다. 이에 병합 정렬의 시간 복잡도는 어떤 상황에서도 O(N*logN)이다. 병합 정렬 c++ 코드구현 #include #include //배열 #include using namespace std; int a[101], b[101], c[300]; int main(){ // 두 배열 합치기 int n, m, i, p1=1, p2=1, p3=1;//포인트 scanf("%d", &n); f..

[코딩테스트 / c++] Inversion Sequence (삽입 정렬 풀이)

문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하는 ..

[코딩테스트 / c++] Least Recently Used(2018 카카오 캐시 문제 변형)

문제 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.) 1) Cache Miss :..

[알고리즘] 삽입 정렬(Insertion sort) 의 개념 with c++

삽입 정렬이란 자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 📌정렬 과정(오름차순) 1. 2번째 원소부터 비교 시작한다 2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다(타켓 원소는 임시변수에 넣는다) 3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다 4. 이전 데이터도 차례대로 비교하며 정렬해나간다 5. 이 방법을 반복해서 정렬한다 📌특징 구현이 간단하다 배열이 길어질수록 효율이 떨어진다 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 ..