아기의 세상살이

[Swift] Swift로 중복문자가 없는 가장 긴 부분 문자열 찾기

문제 설명주어진 문자열에서 중복된 문자가 없는 가장 긴 서브스트링을 찾아야 합니다. 또한, 해당 서브스트링의 길이도 함께 출력해야 합니다.예제입력 : "aabcbbc"출력 : 3 // "abc"입력 : "bbbbbb"출력 : 1 // "b"입력 : "aaaaabbbcedfg"출력 : 6 // "bcedfg"해결 방법이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법과 해시셋(Hash Set) 을 사용합니다.슬라이딩 윈도우: 문자열을 순회하면서, 현재 서브스트링의 길이를 유지하면서 중복 문자가 나오면 윈도우의 시작을 조정합니다.해시셋: 현재 윈도우에서 중복 문자가 존재하는지 빠르게 확인하기 위해 사용합니다.이제 Swift 코드로 구현해보겠습니다.Swift 코드 구현import Fou..

코딩 테스트 준비, 어디부터 시작해야 할까?

1. 코딩 테스트란?코딩 테스트는 개발자의 문제 해결 능력을 평가하는 중요한 절차입니다. 특히 IT 기업에서는 알고리즘 및 자료구조를 활용한 문제 해결 능력을 요구하며, 대기업 및 스타트업 모두 채용 과정에서 이를 활용합니다. 최근에는 생성형 AI(Generative AI)의 등장으로 인해 코딩 테스트의 형태가 변화하고 있습니다.2. 생성형 AI와 코딩 테스트의 변화생성형 AI, 특히 ChatGPT, GitHub Copilot, Google Bard 등의 AI 도구가 등장하면서 개발자들은 보다 효율적으로 코드를 작성하고 디버깅할 수 있게 되었습니다. 하지만 코딩 테스트의 패러다임 역시 변하고 있습니다.(1) 단순 구현 문제가 줄어듦기존의 코딩 테스트에서는 알고리즘 구현 및 자료구조를 활용한 문제 풀이가 ..

이번 포스트에서는 비트연산에 대해 살펴보도록 하겠습니다. 프로그램에서 사용하는 n비트 정수는 내부적으로 n개의 비트로 구성된 이진수 형태로 저장이 됩니다. 예를 들어 32Bit int 자료형에서 42는 아래와 같습니다. 00000000000000000000000000101010 이진수를 10진수로 변경하는 방법은 각 자리 수에 2의 n-1제곱을 곱해주면 구할 수 있습니다. (중학교 때 배운 것으로 간주하고 넘어가겠습니다.) 부호가 있는 n비트 정수 변수에는 -2^(n-1) 부터 2^(n-1)-1까지의 정수를 저장할 수 있습니다. 부호가 있는 정수 표현에서 가장 왼쪽 비트는 부호를 나타내며 0은 양수를 나타내고 1은 음수를 나타냅니다. 나머지 n-1개의 비트는 정수의 크기를 표현하게 됩니다. 부호가 없는 ..

이번 포스트에서는 문제 풀이를 위한 프로그래밍 기법 두번째 재귀적 알고리즘에 대해서 알아보도록 하겠습니다. 재귀를 사용하면 알고리즘을 잘 구현할 수 있게 되는 경우가 많이 있습니다.(안좋은 경우도 있지만) 문제 풀이를 하면서 답이 될 수 있을 만한 재귀적 풀이 후보들을 소개해보고자 합니다. 1. 부분집합 생성하기 재귀를 사용하는 예 중 부분집합 생성하기에 대해 살펴보도록 하겠습니다. 원소가 n개인 집합의 모든 부분집합을 생성하는 알고리즘을 구현해야하는 상황에 있다고 생각해봅시다. {1, 2, 3}의 부분집합은 (공집합), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 이렇게 있습니다. 우선 부분집합을 구하는 search라는 함수는 다음과 같은 벡터를 사용합니다. 1 vec..

알고리즘 문제 풀이를 위한 프로그래밍 기법에 대해 간단히 정리해보고자 한다. 단순 입/출력에서도 어떤 함수를 써야 실행 시간이 조금이라도 짧아질 수 있는지 알아보자. #include using namespace std; int main() { // 이 부분에 원하는 코드 } #include 는 표준 라이브러리 전체를 포함시키는 g++ 컴파일러의 기능이다. iosttream, vector, algorithm 등의 라이브러리를 개별적으로 포함시키지 않아도 자동으로 사용할 수 있게 된다. 작성된 소스 코드의 컴파일은 터미널에서 아래와 같은 명령어로 컴파일한다. g++ -std=c++11 -02 -Wall test.cpp -o test 컴파일러는 c++11 표준을 따르고(-std=c++11) 코드를 최적화 하며..