알고리즘18 [프로그래머스] 디펜스 게임 c++ *O(nlogn)안에 풀어야 할 때 최소 힙 생각하기 풀이 1.최소 힙을 통해서 enemy 벡터를 앞에서부터 정렬해준다. 2. 최소힙의 사이즈가 k개가 넘어가면 최소힙의 제일 작은 원소 즉 0번째 값을 삭제하고 sum에 더한다. (top(), pop() 사용) 3. sum이 n보다 커지면 for문을 탈출한다. 이때 i값이 답. 모든 라운드를 막을 수 있을때는 enemy의 size 반환. **제일 큰 k개에 "무조건"을 써야되기 때문에 최대힙을 써야할줄 알았는데 최소힙을 써야했다. 왜냐하면 pop()을 할때 맨 앞에 있는 원소를 삭제하는데 제일 작은 원소를 삭제하기 위해서이다. #include #include #include using namespace std; int solution(int n, int .. 2023. 1. 1. [프로그래머스] Lv2. JadenCase 문자열 만들기 문제 자체는 어렵지 않았는데 대문자 변환과 소문자 변환이 헷갈렸다. 편집기의 자동완성 기능에 의존하다 보니까 함수의 사용법이 헷갈렸다. 그리고 A와 a의 아스키코드를 까먹어서 찾아보고 풀었다. a:97 ,A:65 1. 대문자변환 toupper(s[i]), 소문자 변환 tolower(s[i]) 2.대문자 변환 s[i]-32 , 소문자 변환 s[i]+=32 풀이: 1.글자가 숫자면 넘어간다. 2.공백이면 check를 true로 바꾼다. 3. 전글자에 공백이 나오고 소문자이면 대문자로 바꾸어준다. 4.전글자에 공백이 나오지 않았는데 대문자이면 소문자로 바꾸어준다. https://school.programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스 코드 중심의 개발자 .. 2022. 11. 25. [백준]15686치킨배달 c++ https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 각 집과 치킨집과의 거리를 계산한다. 아래 케이스의 경우 집이 6개 치킨집이 5개이므로 30개의 값을 계산한다. 2. 백트래킹 알고리즘을 통해서 치킨집 개수 중에서 m개를 고른다. 이때 1,2,5번을 고르나 2,1,5번을 고르나 똑같기 때문에 오름차순으로 인덱스를 골라서 arr에 넣어준다. 3. 치킨집을 정했으면 각 집마다 정해진 치킨집과의 최소의 거리를 구하고 그 거리.. 2022. 9. 26. [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review 도입 단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있지만 없음을 증명할 수 없다. 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘 증명을 공부해야 하는 이유 : 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문. 수학적 귀납법과 반복문 불변식 수학적 귀납법 : 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법 단계 나누기 -> 첫 단계 증명 -> 귀납 증명 반복문 불변식 (loop in - variant ) : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건 이진 탐색에서 int binsearch (const vector&A,int x){ int n =A.size(); .. 2022. 5. 22. 이전 1 2 3 4 5 다음
