본문 바로가기

ALGORITHM

 (71)
트라이 Trie (c++ 구조체 구현) Trie 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 입니다. 트리 구조로 문자열을 저장하기 때문에 단순히 비교하면서 탐색하는 것보다 효율성이 좋습니다. 주로 문자열이 키인 경우가 많습니다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않습니다. 즉, 키의 값은 자료구조 전체에 분산됩니다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하기 때문에 '접두사 트리'라고도 불립니다. 루트는 빈 문자열 입니다. 정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부릅니다. Trie 의 장점 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 유리..
[c++] 숫자 문자열과 영단어 (프로그래머스, 구현) 2021 카카오 채용연계형 인턴십 https://programmers.co.kr/learn/courses/30/lessons/81301# 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr map을 사용해서 풀었다. find() 함수도 사용 #include #include #include #include using namespace std; int solution(string s) { int answer = 0; unordered_map numbers ({ {"zero", "0"}, {"one", "1..
[c++] 더 맵게 (프로그래머스 - heap/ priority queue) https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr min heap 선언방법 기억해두고 vector min_heap; 벡터나 배열은 선언시 바로 값 대입 가능! push 하면 자동으로 정렬가능 #include #include #include using namespace std; // min heap을 통해 구현 int solution(vector scoville, int K) { int answer ..
[c++] 타겟 넘버 (프로그래머스 - dfs) https://programmers.co.kr/learn/courses/30/lessons/43165# 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr pass by reference로 answer 변수를 넘겨줘서 해결했는데 int dfs 로 return 1 했을 땐 결과가 나오지 않아서 슬퍼하는중 #include #include using namespace std; void dfs(vector &numbers, int order, int maxOrder,..
[c++] 실패율 (프로그래머스 - 구현) https://programmers.co.kr/learn/courses/30/lessons/42889# 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 간단한 구현 문제인데 역시 구현문제는 문제를 반드시 꼼꼼하고 꼼꼼하게 읽어야 한다는 것을 다시 깨달은 문제 ㅜ double 계산은 double로 compare 함수 만들 때 같으면 작은 번호가 먼저 오게 하는 조건을 마지막까지 못보고 있었다 ( b.second; } vector solution(int N, vector stages) { vector answer..
[c++] 신규 아이디 추천 (프로그래머스-구현) https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 단순한 구현 문제이지만 string STL의 여러 함수를 잘 응용하면 훨씬 쉽게 풀 수 있는 문제 #include #include #include using namespace std; string solution(string new_id) { string answer = new_id; // 1 for (int i=0; i= 'A' && answer[i] ..
[c++] string 문자열 #include 문자열에 대해 파헤쳐 봅시다 ~ ASCII 코드 가장 많이 쓰는 알파벳을 알아봅시다. A : 65 a : 97 리턴값 front, back 맨 앞 문자와 맨 뒤 문자를 뽑아주는 함수입니다. begin, end 맨 앞 iterator, 맨 뒤 iterator 입니다. find 특정 문자열을 찾으면 시작 위치를 리턴 더보기 first 'needle' found at: 14 second 'needle' found at: 44 'haystack' also found at: 30 Period found at: 51 There are two prepositions in this haystack with needles. 뒤에 붙는 숫자는 그 문자열부터 시작한다. // string::find #incl..
[공부] 바킹독의 실전 알고리즘 (ing) https://github.com/encrypted-def/basic-algo-lecture encrypted-def/basic-algo-lecture 바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub. github.com 바킹독의 실전 알고리즘을 보면서 모르거나 헷갈렸던 부분, 기억해야 하는 부분을 다시 정리하였습니다. https://www.notion.so/neuli/2edd1c3c437e4ae98e6492f515d61e21 바킹독의 실전 알고리즘 실수 자료형의 특징 www.notion.so 실수 자료형의 특징 실수의 저장/ 연산 과정에서 반드시 오차가..

티스토리툴바