cchanmi

최근에 알고리즘 문제를 풀다가 백트래킹이라는 개념을 사용해야 하는 문제를 접하게 되었는데, 어떤 개념인지 잘 짚고 넘어가면 좋을 것 같아서 정리해 보려고 합니다! 백트래킹이란? 제약 조건 만족 문제에서 해를 찾기 위한 전략입니다. 보통 DFS랑 같이 사용되곤 하는데요. 문제에서 요구하는 해를 찾기 위해 제약 조건에 따라 점진적으로 방문하다가, 해당 노드가 제약 조건에 만족할 수 없다고 판단하였을 때, 즉시 이 노드는 더이상 방문할 필요가 없음을 판단하고, 뒤로 돌아가 다른 노드를 탐색하며, 최적의 해를 찾는 방법이라고 설명할 수 있습니다. 조건에 맞지 않을 경우 더이상의 탐색을 포기하는 것을 가지치기라고 얘기하며, 주어진 해를 찾는 탐색의 시간을 절약하는 기법입니다. 결론적으로 백트래킹은 DFS로 트리 ..

swift로 알고리즘 문제를 풀다 보면 string의 index에 접근해야 할 상황이 종종 있습니다. swift는 다른 언어들처럼 index를 정수로 받지 않아서 조금 까다롭더라구요. let hello = "hello" let first = hello[0] // error 그래서 우리는 swift에서는 string의 index를 가리키기 위해서는 String.index라는 타입을 이용해야 합니다. String.index란? 공식 문서에 따르면 문자열에서 문자 또는 코드 단위의 위치라고 정의되어 있습니다. Apple Developer Documentation 첫번째 index를 가리키는 법 그럼 String.index를 사용하여서 0번째 인덱스를 가리키려면 어떻게 해야 할까요? let first = str..

안녕하세요. :) 알고리즘 문제를 풀다 보면 reversed, sort, sorted와 같은 문자열 재정렬 함수를 사용하게 되는 경우가 종종 있는데요. 좀 더 정확하게 알기 위해 블로그에 정리해 보겠습니다. reversed 먼저 공식 문서를 살펴보았습니다... https://developer.apple.com/documentation/swift/string/reversed() Apple Developer Documentation developer.apple.com reversed 함수는 컬렉션 요소를 역순으로 표시해 준다고 적혀 있네요. 또, reserved 함수를 호출하여 사용했을 때, 새로운 배열을 반환하는 것이 아니라, 기존의 컬렉션을 래핑하여 요소를 역순으로 정렬해 준다고 적혀 있습니다! 예를 들..