알고리즘

프로그래머스 H-index (C++)

1. 문제 설명2. 문제 해결정렬만 할 줄 안다면 크게 어려울 문제는 아니었다. 3 0 6 1 5를 오름차순으로 정렬하여0 1 3 5 6 으로 만들고, H-index를 찾기 위해서 위 배열에 상응하는 5 4 3 2 1 배열을 (가상으로) 만들어서  오름차순으로 정렬한 벡터가 배열보다 크거나 같아지는 시점에 반환하도록 하였다.처음에 등호를 안 넣어서 헤맸었다..  3. 코드#include #include #include using namespace std;int solution(vector citations) { int answer = 0; sort(citations.begin(), citations.end()); int len = citations.size(); for (int i ..

프로그래머스 기능개발 (C++)

1. 문제 설명2. 문제 해결배열의 길이가 길지 않은 걸 보니 따로 최적화를 할 필요는 없는 구현 문제라고 판단된다. 그냥 문제에서 하라는 대로 차근차근 하면 되어서 어려운 문제는 아니다. 나의 경우 v에 걸리는 시간을 넣어두고, map 자료구조를 사용해서 값을 갱신하는 형태로 코드를 작성하였다. 내 코드도 나쁘지 않다고 생각했는데, 다른 사람들의 풀이를 보니 훨씬 잘 최적화한 경우가 있었다. 내가 놓친 부분은 다음과 같다.  1. 작업일수를 구하기 위해 내부 반복문을 작성하지 않아도 된다. 99에서 현재 작업량을 빼고 속도로 나눠주면 된다. 2. 이 문제에서는 v를 선언해서 계속해서 값을 저장해둘 필요는 없다. int 변수에 지금까지 중 최대 작업량만 넣어두면 된다.   3. 꼭 map 자료구조를 사용..

프로그래머스 의상 (C++)

1. 문제 설명 2. 문제 해결경우의 수를 생각하면 쉽게 해결할 수 있다. 만약 한 카테고리에 의상이 2개 있으면, (안 입음, 1개입음, 2개입음) 해서 총 경우의 수가 3가지이다. 그렇게 (카테고리 내 의상의 수 + 1 )를 모두 곱해준다음 1을 빼주면 된다. (모두 안 입는 경우의 수는 존재하지 않으므로) 자료구조는 c++에 있는 map을 활용하였다.  몰랐던 부분 : map 내 초기화가 되지 않은 Key가 들어갈 때 자동으로 0이 초기화되기 때문에, 굳이 조건문을 나눌 필요가 없다. 그리고 for문을 쓰기가 애매해서 auto를 처음 써 보았다.   3. 코드#include #include #include using namespace std;int solution(vector> clothes) { ..

프로그래머스 구명보트 (C++)

1. 문제설명 2. 문제해결전형적인 그리디 문제이다. 정렬을 하고 처음 인덱스와 마지막 인덱스를 더했을 때 limit 이하라면, 그것이 최적의 수임을 보장한다는 사실을 알면 어렵지않게 풀 수 있다. 순간 answer 개수를 어떻게 세야 할 지 모르겠어서 전체 길이 (다들 따로 타는 최악의 수)로 답을 초기화하고, 두명이 탈 때마다 하나씩 빼는 식으로 개수를 세었다. 3. 코드#include #include #include using namespace std;int solution(vector people, int limit) { int answer = people.size(); sort(people.begin(), people.end()); int start = 0; int end..

프로그래머스 전화번호목록 (C++)

1. 문제 설명2. 트러블슈팅c++에서 해쉬맵을 사용안한지 오래 되어, 관련해서 다음 게시물을 참고하였다.https://hanyeop.tistory.com/80 [C++] Map과 Hash Map(unordered_map) 차이 (STL)Map과 Hash Map(unordered_map) 차이 (STL) 맵과 해시맵은 key와 value를 pair 형태로 가진다는 점은 같으나 맵은 자동으로 정렬( key를 기준으로 정렬하며 오름차순으로 정렬)을 해주며 해시맵은 정렬하지 않hanyeop.tistory.comhttps://life-with-coding.tistory.com/305 [C++][STL] map 사용법 정리인트로 안녕하세요. 오늘은 C++ STL 연관 컨테이너 중 하나인 map에 대해 알려드리겠습..

프로그래머스 조이스틱 (C++)

1. 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42860# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr그리디 문제 유형인데, 그리디 유형은 다른 유형처럼 어떠한 풀이법이 정해져있는 것이 아니어서, 더 어렵게 느껴진다. 처음에 문제를 풀었을 때 자꾸 반례가 발생해서 결국 다른 사람들의 풀이법을 참고하고 다시 풀었다.  2. 트러블 슈팅처음에 내가 짠 코드는 굉장히 복잡하고 긴데, 잘못 짠 부분은 다음과 같다.이 문제는 크게 두 가지를 고려해야 한다. (1) 방향키 위 아래 (2) 방향키..

백준 15686번 치킨 배달 (C++)

문제 설명 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해결 그리디가 아닌, 완전 탐색을 해야 풀리는 문제이다. 이 점만 알고 접근한다면 그리 어려운 문제는 아니다. 문제 조건을 보면 알 수 있듯이, M, N의 수가 그리 높지 않아 완전 제곱으로 충분히 문제를 해결할 수 있다. 과정은 다음과 같다. 1. M개 치킨집을 뽑는다. (조합의 원리를 생각하면 된다.) 2. M개에 대한 치킨 거리를 계산한다. 3. 최솟값을..

백준 1039번 교환 (C++)

문제설명 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 완전 탐색으로 풀었고, DFS, BFS 둘다 가능할 것 같은데 나는 BFS로 풀었다. 하나의 스텝 안에서 중복을 체크하기 위해 visit이라는 이름의 set 자료구조를 선언했다. 이 중복 체크를 DFS에서 하려면 재귀에 대해 잘 이해하고 코드를 짜야할 것 같다. 인덱스로 관리하기 위해 입력은 string 형태로 받았으며, while 문 안에서는 총 3번의 반복문이 이루어진다. 1. 기존 q에 있었던 값들 (즉, 이전 스텝에서 q에 넣었던 수들)을 ..