문제 1.4 회문 순열: 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. 입력: Tact Coa 출력: True (순열: “taco cat”, “atco cta” 등) 제한 사항 문자에 대한 제한은 없는가? (알파벳을 제외하고도, 아스키 코드 범위) 대문자와 소문자를 같은 문자로 취급한다. 공백은 무시해도 되는 것인가? 아이디어1 문자가 키가 되는 해시테이블을 생성한다. 각 문자의 출현 빈도를 값에 담는다. 홀수 개의 문자의 개수를 조사한다. 홀수 개의 문자가 1개 이하이면 True이다. 공간복잡도 ..
문제 1.3 URL화: 문자열에 들어 있는 모든 공백을 ‘%20’으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다(자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다). 입력: “Mr John Smith”, 13 출력: “Mr%20John%20Smith” 제한 사항 공백은 스페이스 몇 개이든 상관이 없는가? 충분한 공간이 이미 확보 -> 이게 무슨 말인지?, 공간복잡도를 O(1)로 풀라는 이야기인가?, 공간을 사용해도 된다는 이야기인가? 최종 길이가 함께 주어진다. 아이디어1 문자열을 하나하나 검사한다. 새로운 문자 변수에 공백이 ..
문제 1.2 순열 확인 : 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라. 제한 사항 순열 관계가 무엇인지 알아야 함. -> 같은 문자로 구성 되었지만 순서가 다른 문자열. 문자열 길이의 제한이 없다. 문자 또한 알파벳에 대한 제한이 없다. 주어진 문자열의 순서를 바꾸어도 되는지에 대한 제한이 없다. 두 문자열의 길이가 다르면 False다. 아이디어1 각각의 문자열을 정렬한다. -> O(nlogn) 앞에서 부터 한 문자 비교한다. -> O(n) 공간복잡도 주어진 문자열을 건드려서 안되면 O(n) 상관없다면 O(1) 시간복잡도 O(nlogn) 아이디어2 하나의 문자열의 문자를 키로 해쉬테이블을 만든다. 해쉬테이블의 값은 하나의 문자열 문자의 카운트를 한다. 다음 ..
문제 1.1 중복이 없는가: 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. 제한 사항 문자열의 길이 제한 없음. 문자열의 중복 여부만 판단하면 됨. 문자열이 정렬되어 있는지 아닌지는 없음. 문자의 구성이 알파벳이라는 제한도 없음. 자료구조를 추가로 사용해서 안 됨. (추가사항) 대소문자 구분에 대한 이야기도 없음. 아이디어1 문자를 키값으로 해쉬테이블에 한 문자 씩 넣는다. 각 해쉬테이블의 값의 크기를 조사한다. 크기가 2 이상이 발견되면 True, 발견되지 않으면 False 공간복잡도 O(n) 시간복잡도 O(n) 아이디어2 (자료구조 사용 X) 문자열을 정렬한다. -> O(nlogn..
왜 알고리즘을 공부하는가? 나는 현재 27살이다. 현역으로 서강대학교 컴퓨터공학과에 입학하여 학점 2.85의 성적에 대학교를 졸업했다. 대학 공부를 솔직히 소홀히 했다. 친구들의 도움을 받아서 겨우겨우 시험을 봤다. 나는 개발자가 되고 싶은 마음이 없었다. 막상 졸업할 때가 되니 다른 친구들의 취업 소식을 보면서 초조해졌다. 그래도 개발자로 살아봐야겠다는 생각에 좋은 스타트업에 취직할 수 있었다. 그곳에서 안드로이드 개발을 배웠다. 잘 못했다. 그런데 정말 많이 배웠다. 처음 회사에서 '클린 코드' 책을 추천 받았다. 이 때까지 대학교에서 잘못된 방향성으로 코딩을 하고 있던 것을 깨달았다. 깃 사용법과 애자일 소프트웨어 개발 방식을 배우며 협업의 중요성과 프로젝트 다운 프로젝트를 진행해보았다. 사실 창업..