WN_인생기록

가장 긴 접두사 찾는 문제이다. 처음엔 한글자씩 뽑아서 일치하면 넘어가고 그런식으로 풀어나가려고 했는데, 한글자씩 뽑는건 되는데 체크하고 다음거 넘어가고, 틀리면 구문 탈출하는 과정이 복잡한거 같아서 생각을 바꿨다. 아예 첫 글자를 기준으로 삼고, 뒤에서부터 하나씩 잘라가면서 비교하는게 나을거 같았다. 왜냐하면 앞에서부터 글자를 비교하면 글자 length를 고려해야해서 복잡할거 같았다. class Solution { public: string longestCommonPrefix(vector& strs) { if (strs.empty()) return ""; // 첫번째 단어를 기준으로 선택 string prefix = strs[0]; // 첫 번째 문자열을 제외하고 나머지 문자열을 순회 for (int ..

로마숫자를 int로 표현하는 문제이다. 단순하게 매핑된 값을 꺼내는 문제인줄 알았으나, 조건이 있는게, IIII의 경우 IV 같이 5-4 라고 표현하는 것이다. 이는, 왼쪽에서 오른쪽으로 파싱할때, 현재의 숫자가 뒷자리 보다 작으면 -를 현재의 숫자가 뒷자리 보다 크면 + 를 한다는걸 의미한다. (이게 제일 헷갈렸음) 그래서 이 조건을 따라보면, class Solution { public: int romanToInt(string s) { unordered_map a; a.emplace('I', 1); a.emplace('V', 5); a.emplace('X', 10); a.emplace('L', 50); a.emplace('C', 100); a.emplace('D', 500); a.emplace('M',..

팰린드룸(회문) 에 대한 문제이다. int 형으로 된 숫자가 회문인지 아닌지 판단하는 알고리즘을 구하는 문제이다. 예시에는 기본 상태와, 예외 처리해야할 예시들이 보여진다. (음수는 팰린드룸 X, 10 일때는 01 이기 때문에 회문이 될 수 없음) 정리하자면 앞부분과 뒷부분이 같아야 하는데, 음수이면 안되고, 10의 배수이거나 0이여서도 안됨 class Solution { public: bool isPalindrome(int x) { // 음수 제외, 10의 배수 제외, 0 제외 조건 if (x 0) { length++; ..

게임에서 쓰이는 알고리즘 중에서 가장 흔하게 쓰이는 것이 A* 알고리즘이다. 근데 A* ALgorithm이 뭐냐고 물어보면.. 암시롱 모른다고 나오니까 차근차근 알아가보자 기본적으로 그래프로 그려진 곳에서 쓰인다. 그래프는 노드와 엣지(선)으로 연결되어 있다. 가중치는 엣지에 부여된 값으로, 이동할때 그만큼의 비용이 든다는 뜻이다. 그래서 가장 적은 비용을 지불해서 시작~목적지 까지 최소한의 비용으로 도달하는게 핵심이다. 시작 노드부터 현재 노드까지의 비용을 g(n) 이라고 하고, 현재~ 목표까지의 비용을 h(n) 이라고 할때. f(n) = g(n) + h(n) 이다. 여기서 h(n)은 휴리스틱 함수라고도 하며, 이 함수의 설계에 따라서 알고리즘의 성능이 결정된다. 그래서 맨해튼 거리 함수, 유클리디안 ..

프로그래밍 하다보면 은근 lvalue 에러를 흔하게 접하게 된다. 간단한 실수에서 비롯된 에러지만 정확하게 원인을 알아서 다음번에 안 생길 문제이다. 정확한 정의와 지식을 파악해보자 Lvalue : 이름(변수) 를 통해 접근할 수 있는 값. Rvaule : 값 자체. 리터럴 1 은 rvalue 임. 임시 레지스터를 제외하면 특정 메모리 주소가 없음. int a = 1; // a는 lvalue 1은 rvlaue int b = 2; // b도 lvalue 2는 rvlaue int c; 3 = c; // error 가 남. 리터럴 상수에 rvalue이기 떄문에 특정 메모리 주소가 없기에 주소를 할당시키려고 하면 에러가 나는것. 그래서 할당 연산자 = 를 기준으로 lvalue와 rvalue를 구분하는것이 외우기..