본문 바로가기

코테3

[알고리즘] 최소 공통 조상(LCA) 알고리즘 🧩 최소 공통 조상(LCA) 알고리즘 최소 공통 조상(LCA): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 여기서 3번 노드와 11번 노드의 공통 조상 노드는 1번이다. ✔️ 동작 과정 모든 노드에 대한 깊이(depth)를 계산 최소 공통 조상을 찾을 두 노드를 확인 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복한다. 1) 모든 노드 깊이 계산 우선 DFS를 이용해서 루트 노드에서부터의 깊이를 구한다. 2) 공통 조상을 구할 노드 선택 두 노드의 깊이를 맞춰주고, 거슬러 올라간다. 그렇게 2번 노드가 공통 조상임을 찾을 수 있다! .. 2023. 12. 10.
[Python] 정규 표현식 (Regular Expressions) 코딩 테스트를 보면서 정규식을 알았다면 간단하게 해결될 수 있는 문제를 푼 적이 꽤 있다. 하지만 너무 어려울 것 같아 미루던 정규식을 스터디를 기회로 조금이라도 공부해보고자 한다. 전부를 알 수는 없기 때문에 이번에는 스터디 문제에서 해결했던 아이디어 위주로 알아보자! 정규 표현식(Regular Expressions): 복잡한 문자열을 처리할 때 사용하는 기법으로, 파이썬만의 고유 문법이 아니라 문자열을 처리하는 모든 곳에서 사용 1. 메타 문자 . ^ $ * + ? { } [ ] \ | ( ) 1) 문자 클래스 [ ] "[ ] 사이의 문자들과 매치"라는 의미 [a-zA-Z] : 알파벳 모두 [0-9] : 숫자 2) ^ 이 문자를 헷갈리지 않고 사용해야 된다. [^0-9] : 문자 클래스 안에서는 ^는.. 2022. 10. 3.
[SQL/Programmers] 집계함수 | MAX, MIN, COUNT, SUM, AVG, STDDEV, VARIAN 프로그래머스 문제집을 풀며 대표적인 집계함수 몇 가지를 간단히 사용해보았다. https://school.programmers.co.kr/learn/courses/30/parts/17043 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 집계함수 (Aggregate Function) 여러 행들의 그룹이 모여서 그룹당 단 하나의 결과를 돌려주는 함수 집계함수명 (ALL | DISTINCT 칼럼/표현식) - Defualt = ALL 주로 숫자 유형에 사용하며 MAX, MIN, COUNT 함수는 문자, 날짜에도 적용 가능하다. 1. MAX ([ALL|DISTINC.. 2022. 8. 15.
반응형

티스토리툴바