본문 바로가기

분류 전체보기

 (403)
시퀀스 컨테이너 - list 더블 링크드 리스트가 구현되어있는 라이브러리이다. 그러나 리스트 형태이기 때문에 iterator로 순회해야하고 배열 벡터 처럼 [] 조회는 불가능하다. 삽입 - list.push_back(a) - list.push_front(a) 삭제 - list.remove(a) * 중복된 원소까지 전부 삭제한다. - list.remove(*a) * 여기서 이는 iterater이다. 그 원소만 삭제한다. - pop_front() - pop_back() 탐색 find(list.begin(), list.end(), 원소) 찾으면 그 위치 주소, 아니면 마지막 주소
프로그래머스 - [1차]캐시 LRU가 무엇인지 알아야 풀 수 있는 문제다. 컴퓨터구조, 운영체제, 데이터베이스 등 필수 과목에서 한번씩 나오는 개념인데 가장 사용한 지 오래된 것을 캐시에서 빼내겠다는 뜻이다. 캐시는 매우 유용하지만 너무 커지면 오히려 느려지고 무엇보다 비용이 많이든다. 예를들어, 캐시의 크기가 3이고 캐시에 A B C 순서로 들어왔다고 하자, 그리고 D가 들어왔다. -> 가장 사용한지 오래된(들어온지 오래된) A가 빠지고 B C D 형태가 될 것이다. 그런데 D가 아니라 A가 들어왔다면, 캐시 히트로 캐시에는 변화없다. 그 다음 D가 들어왔다면? -> A는 들어온지 가장 오래되었지만 방금 캐시 히트로 썼기 때문에 사용한지 가장 오래됐고 사용한적 없는 B가 빠진다. 그러므로 A C D 형태가 된다. 이 알고리즘을 작..
C++ 문자열 자르기 split / 문자열 <-> 정수 형 변환 C++로 PS를 하다보면 가장 짜증날 때가 문자열을 다룰때일 것이다. 문자열을 파싱할때, 문자열을 정수형으로 변환하거나 역변환할때 자바 파이썬 사용자들은 편한 방법을 사용할 수 있지만 C++ 유저들은 이것 또한 암기를 하고 있어야한다. 1. #include string stream 의 약자이다. 특이하게 cin >> 으로 입력하는 방식과 다르게 > tmp) { STR.push_back(tmp); } for (auto a : STR) cout tmp) { STR.push_back(tmp); } cout
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 ..

티스토리툴바