Algorithm
-
[프로그래머스] - 가장 긴 팰린드롬Algorithm/프로그래머스 2022. 9. 15. 16:12
문제 [프로그래머스] - 가장 긴 팰린드롬 https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합..
-
[Algorithm] - LCA ( 최소 공통 조상 )Algorithm/Algorithm 2022. 9. 15. 00:46
LCA ( Lowest Common Ancestor ) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 아래 그림에서 노드 13번과 15번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 5번 노드가 공통 조상이다. 아래 그림에서 노드 13번과 11번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 1번 노드가 공통 조상이다. 알고리즘 1. a,b 노드의 깊이를 파악한다. 2. 깊이가 동일하다면 상위 노드를 찾아가면서 동일한 노드가 나올 때까지 추적 그렇다면 노드의 깊이를 어떻게 파악할 것인가? DFS로 root 노드로 부터 깊이를 미리 구해둔다. 또한, 깊이를 구하면서 자신의 부모 노드를 기억하여 두고 부모 노드로 추적할 수 있게끔 할 수 있어야한다. ..
-
[BOJ] - 11437번Algorithm/BOJ 2022. 9. 15. 00:46
문제 [BOJ] - 11437번 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 이해 더보기 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트..
-
[Algorithm] - 유클리드 호제법 ( 최대 공약수 , 최소 공배수 )Algorithm/Algorithm 2022. 9. 15. 00:21
유클리드 호제법 ( 최대 공약수 ) 2개의 자연수에서 최대 공약수를 구하는 알고리즘 자연수 a , b 가 주어졌을 때 ( a>b 필수조건 ) r = a를 b로 나눈 나머지 값과 같다. a,b = b,r 가 반복되며, r이 0이 될 때 b의 값이 최소 공약수이다. 만약 여러 개의 수의 최대 공약수를 구하기 위해서는 a,b를 구하고 나온 값으로 계속 반복하여 구하면 구할 수 있다. a,b,c => gcd ( gcd(a,b) , c ) def GCD ( a , b ) : if b==0 : return a return GCD ( b , a%b ) print( GCD(78696,19332) ) LCM ( 최소 공배수 ) 최대 공약수를 활용하여 최소 공배수를 구하는 방식 a,b의 곱에서 최대 공약수로 나누면 값 된..
-
[프로그래머스] - 단어 변환Algorithm/프로그래머스 2022. 9. 14. 16:26
문제 [프로그래머스] - 단어 변환 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", targ..
-
[프로그래머스] - 단속카메라Algorithm/프로그래머스 2022. 9. 14. 15:08
문제 [프로그래머스] - 단속카메라 https://school.programmers.co.kr/learn/courses/30/lessons/42884# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요..
-
[프로그래머스] - 베스트앨범Algorithm/프로그래머스 2022. 9. 8. 23:12
문제 [프로그래머스] - 베스트앨범 https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은..
-
[프로그래머스] - 최고의 집합Algorithm/프로그래머스 2022. 9. 8. 16:47
문제 [프로그래머스] - 최고의 집합 https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4..