본문 바로가기

전체 글

 (336)
C++ 연관 컨테이너 set, mutiset set, map은 유사하지만 set은 map보다 작고 모든 삽입, 탐색, 삭제 속도 모두 set이 월등하다. 단, set은 map처럼 막 변수처럼 쓸수는 없고 이 key가 있는지 없는지만 판단 가능하다. 값을 확인하려면 포인터의 접근법을 사용해야하기 때문에 댕글링 포인터나 메모리 누수가 발생할 수 있어 정교한 코딩이 요구된다. 삽입 : insert O(logN) 삭제 : delete O(logN) 탐색 : find O(logN) set은 중복 key를 허용하지 않지만 mutiset은 포함한다, 그리고 set은 자동정렬이 된다.
프로그래머스 - 이중우선순위 큐(C++) 요즘 정말 캡스톤 때문에 정신이 나갈 것 같고 학교 수업따라가기도 힘들어서 PS할 시간이없다,,, 먼저 이 문제를 보고 떠올린 키워드는 세개였다. 1. 이름부터 그렇듯 min우선순위 큐 2. max우선순위 큐 3. 덱 그리고 가장 끌렸던 것은 덱이었다. 1. 숫자를 받는다. 2. 숫자를 받다가 명령이 나오면 덱을 정렬하고 pop_front or pop_back한다. 이 방법은 명령시마다 한번씩 sort해줘야하기 때문에 좋은풀이가 아니라고 생각했다. 그러나 테스트케이스가 적어서 통과할 수 있었던 것 같다. #include #include #include #include using namespace std; vector solution(vector operations) { vector answer; dequ..
프로그래머스 - 베스트앨범(C++) 난 해시 문제를 별로 안좋아하지만 map의 사용법을 익힐 겸 문제를 추천받아 풀어봤다. 이런 생구현 문제는 확실히 먼저 구하는게 뭔지 확실히 해두고 차근차근 풀어가는게 빠르고 좋다. 처음 풀 때 중구난방하게 막 풀다가 결국 내가 내 코드를 못알아봐서 결국 다시 풀었다. 1. 장르별로 뭐가 가장 많이 재생됐고, 그 목록을 벡터로 만듦. 2. 가장 많이 재생된 장르부터 검사하며 고유번호, 재생수 형태로 매핑 3. 매핑한 컨테이너를 정렬. compare 함수 만들기 4. 반복 #include #include #include #include using namespace std; bool comp(pair& a, pair& b) { return a.second > b.second; } bool compare(pa..
백준 14500번 테트로미노 (C++) dfs를 좀 더 점검할 수 있었던 문제이다. 이번 동계학기 삼성 알고리즘 사전 문제에도 비슷한 문제가 나왔었다. 여기서 핵심은 4번의 이동으로 ㅗ ㅏ ㅓ ㅜ 모양을 제외하곤 전부 방문이 가능하므로 카운트하며 돌아가는 백트래킹이다. 1. 각 자리에서 dfs하며 지금까지 카운트가 4가 되면 백트래킹 2. dfs 인자에 지금까지 돌며 더한 값을 저장할 값이 필요함 3. 그런데 위의 모양은 조금 노가다를 해야함 4. 나의 경우 cnt 가 3일 경우 방향에 따라 값을 구하도록 했음 시간이 살짝 마음에 들지 않지만 보통 이정도 걸리는 것 같음 #include #define MAX 500 using namespace std; int N, M; int Max = -1; int board[MAX][MAX]; bool v..
백준 15661번 링크와 스타트(C++) https://tigerfrom2.tistory.com/80 스타트와 링크에서 파생된 문제이다. 스타트와 링크에서는 반드시 3대3 혹은 2대2 처럼 같은 인원수만큼의 팀원들이 있었지만 여기선 1대5, 2대4가 가능하다. 처음에 스타트와 링크를 풀어놓고 제출을 이 문제에 해서 정답률이 처참하다... 1~N까지 조합의 수를 확인해야한다. 반복문을 하나 추가하는 것 외에 스타트와 링크 문제와 다른 것은 거의없다. #include #include #include #define MAX 20 using namespace std; int N; int board[MAX][MAX]; bool check[MAX]; int answer = INT_MAX; void sol() { int team1 = 0; int team2 ..
백준 14889번 스타트와 링크(C++) 처음에 스타트와 링크를 풀어놓고는 다른문제인 링크와 스타트에 제출을 하고 있었다. 레전드 백트래킹을 통한 완전탐색문제이다. N도 최대 20이라 시간에 딱히 신경을 안쓰고 구현에 집중하면 풀 수 있는 문제다. 1. N까지 N / 2 개의 조합을 구한다. 여기서 조합에 선택된 팀1과 선택되지 않은 팀2로 나뉜다. 2. 팀1의 능력치와 팀2의 능력치를 구해 최솟값을 갱신한다. 3. 모든 조합을 구할 때 까지 반복한다. #include #include #include #define MAX 20 using namespace std; int N; int board[MAX][MAX]; bool check[MAX] = { false, }; int answer = INT_MAX; void sol() { int team1..
백준 1715번 카드 정렬하기 (C++) 우선순위 큐라는 분류를 보지않았다면 조금 해맸을 것 같다. 주어진 카드뭉치를 우선순위 큐 오름차순으로 정리하고 꺼내면서 연산하면 된다. 그러나 처음 이해한 것이 예를들어 N =3 이고 A B C라 정렬되어있다하면 (A + B) + (A + B + C) 인줄 알았다. 그래서 꺼내면서 중복처리해주면서 연산했는데 이런문제가 아니었다. 로직은 다음과 같다. 1. 두개를 꺼내 더함 2. 더한 값을 큐에 다시 넣음 3. 더한 값을 answer에 sum 해놓음 3. 1,2,3번을 큐가 빌때까지 반복, 단 큐가 끝날 때 아직 더하지 않은 요소가 있다면 덧셈함. 문제를 확실히 읽고 파악하는 연습이 필요하다. #include #include using namespace std; priority_queue q; int ma..
백준 11279번 최대 힙(C++) 자료구조 힙, 우선순위 큐, 그리디 문제를 열심히 풀어보려고 한다. 먼저 최대힙 문제를 풀어봤다. 우선순위큐를 구현하기 위해 생긴 자료구조가 힙이다. 힙은 이진트리로 구성되어있고 배열 혹은 리스트로 구현이 가능하다. 물론 이 문제는 힙같은건 구현할 필요 없고 stl만 사용해도 충분하지만 공부를 위해 배열로 구현해봤다. 기본적인 최대힙의 개념을 살펴보면 1. 부모노드는 언제나 자식 노드보다 크다. 2. 자식 노드 중 작은 노드가 왼쪽 더 큰 노드가 오른쪽이다. 이러한 배열이 있다고 치면 index 1 2 3 4 5 6 value 1 3 6 5 9 8 이걸 트리 형태로 만들어보면 1 / \ 3 6 / \ / 5 9 8 이렇게 될 것이다. 그러니까 부모노드의 index = 자식노드의 index / 2 자식노드..

티스토리툴바