제가 프로그래밍 초보라서 방법만 생각해 보았는데 먼저 모든 알파벳에 숫자이름을 붙여줍니다.이때 숫자들은 소수로 붙여줍니다. 예를 들어 a=2, b=3 ,c=5 ,d=7.....이렇게 대입을 해주고 나면 입력된 두개의 단어가 어떤 알파벳으로 이루어 지는지를 분석합니다(이건 잘하는 사람들이 해주겟죠....) 그 다음 각각에 알파벳에 해당하는 숫자들을 곱합니다.(예를 들어 bad이면 3×2×7) 처음이 숫자들을 모두 소수로 대입했기 때문에 두 단어의 숫자곱이 같은 경우는 알파벳 구조가 같은 경우 밖에 없습니다.따라서 곱이 같으면 true 틀리면 false라고 출력하게 하면 될것같아요
@@user-arenamaster 5년 후에 보니 많이 어린 생각이었네요. ”애너그램이라는 함수를 만들었다.“ 가 중요한 게 아니라 그 함수를 코드해 나가는 과정에서 키워야하는 사고력과 문제 해결 능력 등 이면에 있는 것들이 더 중요하다는 것을 깨닫게 되었습니다. 이 능력은 역시 어려운 언어를 코드해나가면서 배울 수 있는 점들이구요. 동의합니다.
영상의 알고리즘은 소팅 2회( 2 x nlogn ), 컴패어 1회( 1 x n ). (소팅 내부에 대입문도 매번 들어가고..) 아무래도 재연 영상인 만큼 면접 분위기를 보라는 영상인가보네요. 그런데 이 영상이 면접에 관심있는 학생분들이 많이 볼 것 같고, 실무자가 계속 리드를 해준 결과이므로 충분히 오해의 소지가 있다고 판단. 혹시나 학생분들이 영상의 최종 알고리즘이 애너그램의 정석이다 라고 오해할 수도 있을까 걱정되어 설명충이 되어보겠습니다. 영상의 알고리즘이 애너그램 판별만을 함수의 목적으로 두고 있다면 함수의 시그니처가 가지는 위험성을 제외하고는 매우 간결하고 훌륭한 구현이지만, 면접에서의 알고리즘 질문인 만큼 알고리즘 최적화가 질문의 요지라고 생각됩니다. 함수목적이 비용 최적화 우선이라 가정하면, 위에 언급한 이유로 비교 루틴을 직접 만들어야 합니다. (일반적인 소팅 1회 비용으로 결과 산출.) isAnagram("google", "eggool") → TRUE isAnagram("google", "eggfol") → FALSE bool isAnagram(string a, string b) { if(a.Length != b.Length) return false; int last_idx = b.Length; for (int i=0; i
구글 인터뷰에서 최적화 우선이라고 누가 그래요??ㅎㅎ 구글 인터뷰 팁 관련 조금만 찾아보면 그게 아니라는걸 알수있습니다. 위 영상에서 문제는 쉬운걸로 했지만, 구글인터뷰 핵심은 다 포함된것 같은데요? 본인 혼자 가정하지 않고, "이렇게 가정해도 될까요? 라이브러리 사용해도 될까요?" 이렇게 본인의 생각을 얘기해 가면서 해결해가는게 구글 인터뷰 핵심입니다. 그러다가 잘못된 길로 가는것 같으면 인터뷰어가 좀 잡아주기도 하구요. 첨부터 답 달달 외워와서 최적화된 답을 말하는것보다 Brute force 부터 차근차근 장단점 얘기해 가면서 알고리즘을 개선 시키는게 더 점수가 높아져요.
01:30 BAT 와 TAB 같이 아나그램(애나그램?) 인 단어일 경우 각 단어를 알파벳 단위로 쪼개어 배열에 넣습니다. 각각 A 와 B 라고 칭하겠습니다. A 안에 있는 원소들에 대해 반복문을 돌려 현재 반복중인 원소가 B 에 존재한다면 B 에서 해당 원소를 삭제합니다. 반복문이 끝났을 때 B 의 배열에 원소가 남아있지 않다면 두 입력은 아나그램(에나그램) 관계에 있다고 볼 수 있습니다.
이를 파이썬코드로 구현했을 경우 *입력받는 부분은 제외하고 각각 in1, in2 를 입력이라고 가정하겠습니다. array1 = in1.split("") array2 = in2.split("") for value in in1: if value in in2: in2.remove(value) if in2.len == 0: return False return True
정리 : 만약에 a가 tab고 b가 bat 면 알파벳 순서대로 a를 abt로 바꾸고 b도 abt로 바꿔서 이 둘이 같으면 true 아니면 false 를 출력하는 간단한 코드입니다 ^^ 총 통합본으로 따지면 #include #include #include #include using namespace std; bool Anagram(char a[], int a_len, char b[], int b_len){ if(a_len!=b_len){ return false; } sort(a,a+a_len); sort(b,b+b_len); return strcmp(a,b)==0; } int main() { char a[100],b[100]; int c,d; scanf("%s",a); scanf("%s",b); c = strlen(a); d = strlen(a); if(Anagram(a,c,b,d)==0){ printf("false"); } else{ printf("true"); } } 이렇게 나오네요 제가 코딩을 잘 못하지만 제 실력으로 짜 본 코드입니다
문제가 쉬워도 막상 손코딩 그자리에서 하려면 쉽지않더라구요
구글 들어가고 싶다..
문제를 주고 받는 과정을 말하고 싶은거지 실제 문제는 훨씬 어려운 문제 나올듯...
ㄹㅇ ㅋㅋ
제가 프로그래밍 초보라서 방법만 생각해 보았는데 먼저 모든 알파벳에 숫자이름을 붙여줍니다.이때 숫자들은 소수로 붙여줍니다. 예를 들어 a=2, b=3 ,c=5 ,d=7.....이렇게 대입을 해주고 나면 입력된 두개의 단어가 어떤 알파벳으로 이루어 지는지를 분석합니다(이건 잘하는 사람들이 해주겟죠....) 그 다음 각각에 알파벳에 해당하는 숫자들을 곱합니다.(예를 들어 bad이면 3×2×7) 처음이 숫자들을 모두 소수로 대입했기 때문에 두 단어의 숫자곱이 같은 경우는 알파벳 구조가 같은 경우 밖에 없습니다.따라서 곱이 같으면 true 틀리면 false라고 출력하게 하면 될것같아요
알파벳이 엄청 길다면 그 길이에 해당하는 순서의 소수를 찾아줘야겠네요. 에라토스테네스의 체 알고리즘을 사용하는데 추가적인 시간복잡도가 필요하겠네용
창의적인 방법이네요. 근데 알파벳이 길어질수록 연산량이 기하급수적으로 올라가겠어요
@@hyee3112 인코딩에 따라, 문자셋에 따라 다를거 같음. 16비트 내로 표현되는 문자면 부담 없이 사용할 수 있을거 같고 UTF-8 이모지 같이 32비트 사용하는 문자면 영상처럼 정렬을 하던지 해야할듯.
@@daehyeokwon4211 초기화 비용이라 메모리가 터지지 않으면 엄청 좋은 방법인듯. 소수 자체는 O(n loglogn) 에라토스테네스 체 말고 O(n) 만에 n 범위 내 소수들 구할 수 있는 방법이 있어서 시간복잡도 자체는 크지 않고.
아 근데 생각해보니 overflow 생각하면 시간복잡도 상 별로 좋은 방법은 아닌듯. 큰 수를 표현하려면 그만큼 연산 시간, 메모리도 늘어나서...
구글도 별거 아니라뇨.... 그냥 간단한 기술면접 재연을 보여준건데.. 구글 면접에서는 이해못했으면 물어볼수도 있고,면접관이 피드백 준다는 방식을 보여주는 거 같은데 왜케 난이도, 코드에만 집착하시지 다들..
파이썬은 set으로 둘다 만들어준다음 두 set이 같은지.아닌지를 리턴하면 O(n)이 될수도있을듯
파이썬은 set이 중복도 허용하나요? hello를 넣으면 h, e, l, o만 들어가지 않나요?
@@최강재-y9c ㅎㅎ 그래서 후에 댓글 달고나서 생각해보니까 이건 틀렸다는 생각이 들더라고요. set은 중복을 허용하지않으니 각 알파벳 숫자 갯수를 세는 list를 2개만들고 두 리스트 원소들이 모두 같은지를 판별하는게 낫겠다는 생각이들었어요
구글들어가고싶다
단어의 알파벳을 key, 빈도수를 value로 하는 해시맵을 생성해서 좌라라락 비교하면 되겠네요(정렬은 딱히 필요없는듯)
중간에 상대맵에 해당키가 없거나 있더라도 val이 다르면 false리턴
끝까지 임무를 완료하면 true리턴
대충 어떻게 하는지 코드좀 보여주실수있나여?
음 모르겠네요 결국에 마지막에 빈도수를 종합하려면 문자열 길이만큼 반복문을 쓰거나 아스키코드면 아스키코드갯수만큼의 반복문이 필요하겠네요? 그럴바엔 다른분 댓글처럼 어레이로 미리 아스키코드 갯수만큼 어레이를 두고 하는게 캐시활용면에서 이득이 아닐까 싶어요 물론 한글까지 포함시킨다면 해시맵만들고 문자열 길이만큼 한번더 반복하는게 옳을수 있구요 제가 생각지 못하는 방법으로 맵전체 빈도수를 확인할 방법이 있나요?
저 문제가 쉬워 보여도 원체 풀수 있는 방법이 많게 때문에 인터뷰어가 원하는 방식으로 푸는게 쉽지 않습니다. 그리고 화이트보드에서 하려면 진짜 힘듬.
입력 단어 A를 스펠링별로 카운트(increment)하고, 입력단어 B를 카운트(decrement)하면서 모든 카운트가 0인지 확인하면 메모리, 시간 모두 O(n)으로 해결 가능하겠네요
단어 두개 A, B가 anagram 이 아닌데 같은 합이 나오는 경우 있습니다. 예) 1+4+2, 3+3+1.
@@coolinglifee
합을 구하는 로직이 아니라, 26(A-Z) 크기의 버킷에 각 알파벳 개수에 대응하는 수를 기록합니다.
[0, 0, 0, ..., 0] := [A, B, C, ..., D]
X, Y의 각 스펠링을 회귀(i=0; i
김동욱 공간복잡도는 alphabetCounts 쓰기 때문에 O(n) 이 맞는 것 같아요. 영상에 나온 답변에 비해 빠른 대신 공간을 많이 쓰는 trade off 가 있네요.
@@coolinglifee alphabetCounts의 크기가 항상 상수 26이기 때문에 O(26) = O(1) 이네요.
오홍 이게 제일 깔끔해보여요 단 영어만 쓴다라던가 아스키코드일때라는 조건이 있다면요. Map을 만드는것보다 훨씬 빠르겠네요.
각 단어에 있는 알파벳 빈도수를 측정해서 모두 동일 하면 true 다르면 false로 풀면 될것같네요
굿아이디어네요!
@@김기우-u9z 그러면 apple 랑 paple도 아나그램 되는데 ㅋㅋ
걍 문자하나랑 문자뒤집은거랑 비교하면 O(n)에 가능함 코드로 한줄이면 가능
알고있는 개념에 대해서 물어봐도 막상 가서 저렇게 질문 들어오고 손코딩 하라고 하면 긴장타서 어버버할듯
온라인 코딩 시험에서 하두 깨져서 너무 겁나는데 며칠있다 전화 시험이있어요 ㅠㅠ 겁난다
한국은 면접을 한국어로보나보네요... 엄청좋네요 ㅎㅎ
이런 게 있을 줄은 몰랐네요; ^^
오래된 인터뷰이긴 한데 단어 길이를 돌아가면서 사전을 만들어서 사전 비교를 하면 O(n)만에 될거같네요...
어떻게 하는거죠?
그대신 space complexity가 O(n) 이 되겠죠? 저 방식은 이제 좀 느린 대신에 메모리를 거의 안 쓴다는 장점이 있어요.
bool is_anagram(string a, string b) {
if (a.size() != b.size()) return false;
vector histogram(26);
for (auto& c: a)
++histogram[c-'a'];
for (auto& c: b)
--histogram[c-'a'];
for (const auto& h: histogram)
if (h != 0)
return false;
return true;
}
많은 분들이 이 문제를 더 쉽게 코딩하는 방법들을 알려주셨네요.
파이썬으로 하면
def isAnagram(a, b):
return sorted(a) == sorted(b)
네 이렇게 하면 끝납니다.
결론 : 파이썬 공부하자
파이썬 최고
파이썬으로 코딩하면 컴퓨터의 원론은 모른체 누구나 할 수 있는 코더가 되기 쉽습니다.. 어려운 언어 배웁시다
@@user-arenamaster 5년 후에 보니 많이 어린 생각이었네요. ”애너그램이라는 함수를 만들었다.“ 가 중요한 게 아니라 그 함수를 코드해 나가는 과정에서 키워야하는 사고력과 문제 해결 능력 등 이면에 있는 것들이 더 중요하다는 것을 깨닫게 되었습니다. 이 능력은 역시 어려운 언어를 코드해나가면서 배울 수 있는 점들이구요. 동의합니다.
Map 사용하면 O(N) 으로 해결할 수 있음
자세히좀 알려주세요 아무리생각해도 각 단어별로 같은 알파벳이 몇번쓰일지 모르는 상황에 길이제한도 없어서 어떻게 map을 쓰는지 궁금해요
@@user-wj1me9qc4j JS의 Array.prototype.map 메서드나 Python의 map 함수가 아니고, Map(해시) 자료구조를 말씀하시는 것이네요.
손코딩이구나ㅜㅜ. . .
굳이 해쉬맵 쓰지않아도 char형 배열로 들어오니까. 256길이 int 배열로 알파벳 개수 세도 될듯.
저게 다뭔지 알려주실분
무언가 취업생으로 써 두렵네요
M.J.H키워드 그런가요?
영상의 알고리즘은 소팅 2회( 2 x nlogn ), 컴패어 1회( 1 x n ). (소팅 내부에 대입문도 매번 들어가고..)
아무래도 재연 영상인 만큼 면접 분위기를 보라는 영상인가보네요.
그런데 이 영상이 면접에 관심있는 학생분들이 많이 볼 것 같고, 실무자가 계속 리드를 해준 결과이므로 충분히 오해의 소지가 있다고 판단. 혹시나 학생분들이 영상의 최종 알고리즘이 애너그램의 정석이다 라고 오해할 수도 있을까 걱정되어 설명충이 되어보겠습니다.
영상의 알고리즘이 애너그램 판별만을 함수의 목적으로 두고 있다면
함수의 시그니처가 가지는 위험성을 제외하고는 매우 간결하고 훌륭한 구현이지만,
면접에서의 알고리즘 질문인 만큼 알고리즘 최적화가 질문의 요지라고 생각됩니다.
함수목적이 비용 최적화 우선이라 가정하면, 위에 언급한 이유로 비교 루틴을 직접 만들어야 합니다.
(일반적인 소팅 1회 비용으로 결과 산출.)
isAnagram("google", "eggool") → TRUE
isAnagram("google", "eggfol") → FALSE
bool isAnagram(string a, string b)
{
if(a.Length != b.Length) return false;
int last_idx = b.Length;
for (int i=0; i
taesoon kim 이런거다 어느쪽분야임 IT?
구글 인터뷰에서 최적화 우선이라고 누가 그래요??ㅎㅎ 구글 인터뷰 팁 관련 조금만 찾아보면 그게 아니라는걸 알수있습니다. 위 영상에서 문제는 쉬운걸로 했지만, 구글인터뷰 핵심은 다 포함된것 같은데요? 본인 혼자 가정하지 않고, "이렇게 가정해도 될까요? 라이브러리 사용해도 될까요?" 이렇게 본인의 생각을 얘기해 가면서 해결해가는게 구글 인터뷰 핵심입니다. 그러다가 잘못된 길로 가는것 같으면 인터뷰어가 좀 잡아주기도 하구요. 첨부터 답 달달 외워와서 최적화된 답을 말하는것보다 Brute force 부터 차근차근 장단점 얘기해 가면서 알고리즘을 개선 시키는게 더 점수가 높아져요.
이게 무슨 언어쥬?
잘봤습니다!감사합니다~
그냥 string 길이 같고 집합에 넣고 비교하면 안되나요? ^^;
01:30
BAT 와 TAB 같이 아나그램(애나그램?) 인 단어일 경우
각 단어를 알파벳 단위로 쪼개어 배열에 넣습니다. 각각 A 와 B 라고 칭하겠습니다.
A 안에 있는 원소들에 대해 반복문을 돌려 현재 반복중인 원소가 B 에 존재한다면 B 에서 해당 원소를 삭제합니다.
반복문이 끝났을 때 B 의 배열에 원소가 남아있지 않다면 두 입력은 아나그램(에나그램) 관계에 있다고 볼 수 있습니다.
이를 파이썬코드로 구현했을 경우
*입력받는 부분은 제외하고 각각 in1, in2 를 입력이라고 가정하겠습니다.
array1 = in1.split("")
array2 = in2.split("")
for value in in1:
if value in in2:
in2.remove(value)
if in2.len == 0:
return False
return True
제일깔끔하시네요
그냥 보다가 궁금해서 질문남깁니다
1. 반환값이 반대여야하지않나요?
2. b가 a의 여집합일 경우가 고려되어있지 않은것같습니다
정리 : 만약에 a가 tab고 b가 bat 면
알파벳 순서대로 a를 abt로 바꾸고 b도 abt로 바꿔서 이 둘이 같으면
true 아니면 false 를 출력하는 간단한 코드입니다 ^^
총 통합본으로 따지면
#include
#include
#include
#include
using namespace std;
bool Anagram(char a[], int a_len, char b[], int b_len){
if(a_len!=b_len){
return false;
}
sort(a,a+a_len);
sort(b,b+b_len);
return strcmp(a,b)==0;
}
int main()
{
char a[100],b[100];
int c,d;
scanf("%s",a);
scanf("%s",b);
c = strlen(a);
d = strlen(a);
if(Anagram(a,c,b,d)==0){
printf("false");
}
else{
printf("true");
}
}
이렇게 나오네요 제가 코딩을 잘 못하지만 제 실력으로 짜 본 코드입니다
걍 해쉬 테이블을 사용하면 되는데 왤캐 어렵게 하누...
해쉬는 정렬할수 없을때 사용
ㅋㅋ 그냥 떨어졌겠네...... 자기가 말하는게 어떤 효과가 있을지 계산도 없네...
소팅하고 비교하자는건 머 적당히 하겠다는건가
저 분 이미 구글 입사 하신분 ㄷㄷㄷ
어떻게 하는건지 그냥 소개영상이라 간단히 하신거 아닐까요?
+권용진 말로 다 설명했는데 이해 못하시는분 한분 추가요
Lee SG 응 그건 너야
Gyeong-il Heo 언제 입사했는데 떨어진거 같은데 니가 봄? 화술이 그네 수준인데ㅇㅇ
성공한 사람 인생 걱정하는 루저 클라스
구글도 별거 아니구나 문자열 거꾸로를 요구했는데 분포도 동일한갈 비교하다니...
+정진혁 거꾸로를 요구한게 아닙니다...이해도에 문제가 있으신듯...
+Lee SG 제가 이해도에 문제가 있어서 잘 이해를 못하겠네요 그게 아니라면 설명 부탁합니다
+정진혁 문자열 거꾸로를 요구한게 아니라 anagram을 요구한거잖아요?
정의자체가 다릅니다..
anagram 을 요구한게 맞다고 해도... 답변자의 해답은 anagram을 결론적으로 구현한게 아니잖아요.
입력으로 두개의 단어가 주어진다는 가정이 있기 때문에 분포가 같으면 무조건 아나그램입니다
코딩 1도모르긴한데 알파벳마다 고유 소수(2, 3, 5, 7, 11•••)를 부여해서 단어를 이루는 철자끼리 곱셈하게만들면 아나그램인 단어끼리만 곱셈결과가 일치할테니까 이렇게하면 될거같은데
코드나 난이도를 원한게아니라 그 안에서 나오는 일련의 과정들에 대한 피드백과 대응능력을 보는거 아니냐? 솔직히 저정도는 배운지 몇달안된 씨린이들도 걍 풀텐데?
동감합니다. 저 알고리즘 풀이 자체 보단 문제를 해결해나가는 과정이 중요한거 같아요