문자열이란?

문자열(String) 이란 여러 문자가 이어진 데이터이다. 예를 들어, "Hello, Kotlin!" 은 하나의 문자열이다.

 

문자열에서 인덱스 (Index)도 중요한데 인덱스란 문자열의 각 문자의 순서를 나타내며, 첫 번째 문자는 0번 인덱스이다.

val text = "Hello"
println(text[0]) // 출력: H
println(text[1]) // 출력: e

 

Kotlin에서는 문자열을 다루기 위한 다양한 내장 함수를 제공한다.

  • reversed() : 문자열을 뒤집는다.
  • length : 문자열의 길이를 반환한다.
  • contains() : 특정 문자가 포함되어 있는지 확인한다. 리턴값은  true / false
  • split() : 문자열을 특정 구분자로 나눈다.
fun main() {
    val text = "Kotlin Programming"
    println("원본 문자열: $text")
    println("뒤집은 문자열: ${text.reversed()}")   // 뒤집기
    println("문자열 길이: ${text.length}")          // 길이 출력
    println("포함 여부 (o): ${text.contains("o")}")   // 'o'가 포함되었는지
    println("단어 분리: ${text.split(" ")}")          // 공백을 기준으로 분리
}

 

 

 

문제 예시

1. 문자열 뒤집기

  - 문제 설명 : 사용자가 입력한 문자열을 뒤집어서 출력하는 코드를 작성해보자

  - 힌트 : Kotlin의 내장 함수를 사용할 수 있다.

더보기
fun reverseString(str: String): String {
    return str.reversed()
}

fun main() {
    val input = "Hello, Kotlin!"
    println("원본 문자열: $input")
    println("뒤집은 문자열: ${reverseString(input)}")
}

 

 

2. 문자열에서 특정 문자 개수 세기

 - 문제 설명 : 주어진 문자열에서 특정 문자가 몇 번 등장하는지 계산하는 코드를 작성해보자.

 - 힌트 : 반복문과 조건문을 사용하자

더보기
fun countChar(str: String, ch: Char): Int {
    var count = 0
    for (c in str) {
        if (c == ch) {
            count++
        }
    }
    return count
}

fun main() {
    val input = "banana"
    println("문자 'a'의 개수: ${countChar(input, 'a')}")
    // 출력: 문자 'a'의 개수: 3
}

 

 

3. 문자열에서 단어 개수 세기

 - 문제 설명 : 사용자가 입력한 문장에서 단어의 개수를 출력하는 코드를 작성해보자

 - 힌트 : Kotlin의 내장 함수를 사용하자

더보기
fun countWords(sentence: String): Int {
    // 공백을 기준으로 단어 분리 후, 분리된 리스트의 크기를 반환
    val words = sentence.trim().split("\\s+".toRegex())
    return words.size
}

fun main() {
    val sentence = "Kotlin is fun and powerful"
    println("단어 개수: ${countWords(sentence)}")
    // 출력: 단어 개수: 5
}



// val words = sentence.trim().split("\\s+".toRegex()) 동작 순서

// 1. sentence.trim()
// 동작: 입력된 문자열 sentence의 앞뒤(시작과 끝)에 있는 불필요한 공백(스페이스, 탭 등)을 제거합니다.
// 예시: " Hello Kotlin! " → "Hello Kotlin!"

// 2.  .split("\\s+".toRegex())
// 동작:
// trim()으로 정리된 문자열을 기준으로, 하나 이상의 공백 문자(정규표현식 \\s+)를 찾아서 해당 부분에서 문자열을 나눕니다.
// \\s+는 정규 표현식에서 "하나 이상의 공백 문자"를 의미합니다.
// .toRegex()는 문자열 "\\s+"를 정규식 객체로 변환해줍니다.
// 예시: "Hello Kotlin!" → ["Hello", "Kotlin!"]

 

 

 

 

 

 

 

 

 

 

변수와 자료형

  • 변수 : 정보를 저장하는 상자. 예를 들어, 숫자나 글자, 논리값(true/false)을 저장할 수 있다.
  • 자료형 : 변수에 어떤 종류의 값이 들어갈 수 있는지 결정한다.  예시) 정수형 : Int / 실수형 : Double / 문자열 : String / 논리형 : boolean

 

조건문

조건문 (if문) : 주어진 조건이 참이면 특정 코드를 실행하고, 그렇지 않으면 다른 코드를 실행할 수 있다.

val score = 85
if (score >= 90) {
    println("합격")
} else {
    println("불합격")
}

// score가 90 이상이면 "합격"을, 그렇지 않으면 "불합격"을 출력한다.

 

 

반복문

반목문 (for, while) : 같은 작업을 여러 번 반복할 때 사용한다.

for (i in 1..5) {
    println("현재 값: $i")
}
// 1 부터 5까지 숫자를 차례대로 출력한다.

 

 

배열 

배열 : 여러 개의 데이터를 순서대로 저장할 수 있는 자료구조이다.

val numbers = arrayOf(10, 20, 30, 40, 50)
println("첫 번째 요소: ${numbers[0]}") // 10 출력

// 배열의 각 요소는 인덱스로 접근하며, 인덱스는 0부터 시작한다.

 

 

 

문제 예시

1. 배열 요소 출력하기

 - 문제 설명 : 정수형 배열이 주어졌을 때, 배열의 모든 요소를 한 줄에 하나씩 출력하는 코드를 작성해보자.

 - 힌트 : for 문을 사용하여 배열의 인덱스를 순회하며 출력한다.

더보기
더보기
더보기
fun printArray(arr: Array<Int>) {
    for (num in arr) {
        println(num)
    }
}

fun main() {
    val numbers = arrayOf(10, 20, 30, 40, 50)
    printArray(numbers)
}

 

 

2. 배열에서 최대값 찾기

 - 문제 설명 : 정수형 배열이 주어졌을 때, 배열에서 가장 큰 수를 찾아 출력하는 코드를 작성해보자.

 - 힌트 : 배열의 첫 번째 요소를 최대값으로 초기화하고, 반목문을 돌면서 더 큰 값이 있으면 갱신한다.

더보기
더보기
더보기
fun findMax(arr: Array<Int>): Int {
    var max = arr[0]
    for (num in arr) {
        if (num > max) {
            max = num
        }
    }
    return max
}

fun main() {
    val numbers = arrayOf(10, 20, 30, 40, 50)
    println("최대값: ${findMax(numbers)}")
}

https://school.programmers.co.kr/learn/courses/30/lessons/68935

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

여기서의 핵심은 3진법으로 바꾼배열 nums 를 뒤집어야 3진순로 변환된 문자열이 된다는 것이다.

def radixChange(num, radix):
	if num == 0: return '0'
    nums = []
    while num:
    	num, digit = divmod(num, radix) # num에는 몫이, digit에는 나머지가 담기게 된다
        nums.append(str(digit))
    return ''.join(reversed(nums)) // 예를들어 45를 3진법으로 나타냈으면 nums에는 0021이 담기게된다.
    
  def solution(n):
  	return int(radixChange(n, 3)[::-1], 3)

https://school.programmers.co.kr/learn/courses/30/lessons/12973

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

def solution(s):
	stack = []
    for case in s:
   		if stack and stack[-1] == case: stack.pop()
    	else: stack.append(sase)
    
  	return 0 if stack else 1

https://school.programmers.co.kr/learn/courses/30/lessons/12930

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

홀수와 짝수를 구별하는 문제이다. 가장 쉬운 방법은 변수를 하나 더 만들어 짝수인지 홀수인지 구별하는 것이다.

 

def solution(s):
    s = list(s)
    cnt = 0 # 짝수/홀수 구분

 

인덱스 변수를 기준으로 2로 나누어 떨어질  때(짝수), 나누어 떨어지지 않으면(홀수) 라고 정의할 수 있다. 다만 공백을 만나면 새 단어를 준비한다는 의미이므로 짝수/홀수 구분 변수의 값을 초기화 해야한다.

def solution(s):
   s = list(s)
   cnt = 0
   
   for i in range(len(s)):
       if s[i] == ' ': # 공백을 만난 경우
          cnt = 0      # cnt 변수를 초기화해준다.
          continue
       s[i] = s[i].upper() if cnt % 2 == 0 else s[i].lower()
       cnt += 1
      
      
   return ''.join(s)

https://school.programmers.co.kr/learn/courses/30/lessons/12926

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

여기서 생각해봐야 할 문제는 주어진 숫자만큼 더하다 보면 숫자가 알파벳의 범위를 벗어날 수 있다는 것이다. 만약 결과가 알파벳의 범위를 벗어나면 해당 알파벳의 처음인 a 또는 A로 돌아가야 한다.(소문자z -> 소문자 a, 대문자 Z -> 대문자 A).

 

def solution(s, n):
	s = list(s)
    for i in range(len(s)):
     	if s[i] == ' ' : continue
        corr = ord('A') if s[i].isupper() else ord('a')
        s[i] = chr((ord(s[i]) - corr + n) % 26 + corr)
        
    return ''.join(s)

'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글

프로그래머스 - 짝지어 제거하기(level2)  (0) 2024.09.04
프로그래머스 - 이상한 문자 만들기(level 1)  (0) 2024.08.27
문자열  (0) 2024.08.22
2차원 배열  (0) 2024.08.19
시간 복잡도  (0) 2024.08.16

문자열의 특징

문자열(string)이란 문자(char) 또는 문자들로 구성된 집합을 의미한다. 파이썬에서는 기본적으로 "(큰따옴표)와 '(작은따옴표) 문법을 모두 지원한다. 

 

문자열이란

먼저 컴퓨터가 받아들이는 문자열과 사람이 보는 문자열은 차이가 꽤 크다. 모든 것을 숫자로 이해하는 컴퓨터가 문자를 인식하도록 하려면 '문자를 숫자로 변환하는 과정'을 추가로 거쳐야 하며, 이 과저에서 보통 문자 집합(character set)중 가장 대표적인 유니코드를 사용한다.

 

만약 변수에 문자열로 "Programmers is good"을 할당하면 컴퓨터는 사람이 선언한 문자열을 각 글자에 해당하는 숫자로 인식한다. 그리고 모든 글자에 대한 정보를 한곳에 담아야 하기 때문에 암묵적으로 배열로 선언한다. 기존의 배열처럼 [] 형태로 선언하지는 않지만 엄연히 배열로 취급하며, 배열처럼 사용한다.

 

 

1. 문자열 뒤집기

문자열을 통째로 뒤집는 것은 매우 쉽다. 문자열에 슬라이싱으로 [::-1]을 사용해 역으로 만들면 된다. 

 

2. 아스키 코드 다루기

파이썬에서는 문자를 숫자로 바꿔주는 ord() 함수와 숫자를 문자로 바꿔주는 char() 함수를 제공한다. 이러한 함수들을 사용하여 a에 1을 더하여 b로 만드는 드의 행동을 할 수 있으며, 기본적으로 알파벳 순회 같은 문제에서 자주 등장한다.

 

3. 진법 변경하기

파이썬에서는 기본적으로 자주 사용하는 2진법 bin(), 8진법 oct(), 16진법 hex() 함수를 지원하며, 이 외의 진법은 따로 함수로 구현해야 한다.

 

4. 기준에 맞춰 재정렬하기

알파벳순, 숫자순 등 특정 기준이 주어지면 그 기준으로 문자열을 정렬하거나 추출하는 작업이 필요한 경우, 가장 많이 사용하는 라이브러리는 collections 이며, 단어를 세는 것 이외에도 많은 일을 할 수 있어 여러 방면으로 활용된다.

 

5.  문자열 치환하기

string에 있는 replace() 함수를 사용하면 좋다. 

1차원 배열 + 1차원 배열?

다른 언어에서는 '배열은 한 변수에 데이터 여러 개를 선언할 수 있게 해주는 자료형'이라고 할 것이다. '배열은 연속적으로 데이터를 집어넣을 수 있는 1차원 형식의 자료 구조'라고 정의할 수 있다.

 

배열 안의 배열, 즉 2차원 배열은 어떨까? 2차원 배열은 다음 모습과 같다.

 

data = [[1,2,3],[4,5,6]]

 

1차원 배열을 선언하면 다음과 같이 한 방향으로 연속적인 데이터가 나열된다.

배열 생성 시 할당되는 구조

 

조회하려는 항목의 순서인 N에서 1을 뺀 숫자가 바로 원하는 데이터를 조회할 수 있는 인덱스이다. 여기에 배열을 하나 더 얹어 2차원으로 선언할 경우 다음과 같이 사각형이 된다.

2차원 배열을 직관적으로 나타냈을 때

 

이 배열에서 원하는 값을 찾으려면 1차원 배열과 다르게 '세로 위치 -> 가로 위치' 순으로 조회해야 한다. 세로 방향으로 먼저 행을 고른 다음, 가로 방향으로 열을 고르면 원하는 데이터를 찾을 수 있다.

 

2차원 배열의 가장 큰 핵심은 '그룹'이다. 1차원 배열과 다르게 본격적으로 데이터에 의미를 부여하기 시작하는 구조이며, 이런 정보를 기반으로 새로운 데이터를 구축하거나, 원하는 정보를 얻어내기 위해 조작을 한다. 

그림을 2차원 배열로 시각화한 예시

 

배열을 이미지로 생각하면 더욱 빠르게 정보를 이해할 수 있다.

 

 

문제 해결에 필요한 입력값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 한다. 그 중 얼마나 오래 걸리는지는 시간 복잡도라고 하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도라고 한다.

 

 

빅오(Big-O) 표기법

실제로 코드를 실행해보면 소프트웨어나 하드웨어적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다르다. 이런 차이 때문에 시간을 정확한 수치로 표현하기는 어렵지만, 문법이나 구성에서 발생하는 비용을 수치화해 문제를 푸는 데 필요한 총 연산의 수를 수학적으로 표기할 수 있다. 이를 점근 표기법이라고 하며, 세 가지 표기법 중 가장 흔하게 사용하며, 최악의 경우를 계산하는 계산법을 빅오(Big-O) 표기법 이라고 한다.

 

빅오 표기법은 알고리즘이 해당 차수이거나, 그보나 낮은 차수의 시간 복잡도를 가지는 점근적 상한 표기 방법을 의미한다. 쉽게 '최악의 경우 이 정도의 시간이 걸린다'로 이해하면 된다.

 

수학적으로 정의하면 다음과 같다.

 

예를 들어 a 변수에 +1 을 하는 코드를 작성했다고 한다면 (코드로 a += 1) 이를 실행하기 위해 필요한 연산은 총 1번이다. 만약 데이터 개수가 n개라면 프로그램을 실행할 때 발생하는 비용을 f(x)라고 가정하면 데이터 개수만큼 연산을 1번 수행하므로 f(n) = n 이라고 표기할 수 있고, 이를 빅오 표기법으로 나타내면 O(n)이 된다.

 

n개의 데이터를 수행하는 데 걸리는 시간이 제곱만큼, f(n) = 4n^2 + 4n + 1이라고 한다면 동일 최대 차수인 최소 단위 시간 복잡도  g(n) = n^2이 있을 때 f(n) <= cg(n)이 성립하는 상수 c가 존재하므로 결론적으로 표기법 O(x)를 사용하여 최소 단위인 O(n^2)으로 표현할 수 있다.

 

즉, 연산 횟수가 최고 차항에 비례하는 흐름을 보인다면 부가적인 연산은 신경 쓸 필요가 없다. 가령 n^2 + 2n + 1 의 시간 복잡도 역시 최고 차항만 계산하여 O(n^2)으로 줄어든다. 같은 이유로 99n의 시간 복잡도는 O(n)으로 줄어든다.

 

 

시간 복잡도 그래프

시간 복잡도 그래프

 

각 시간 복잡도에 따른 연산 횟수를 정리하면 다음과 같다.

입력 데이터 수에 따른 시간 복잡도의 연산 횟수

 

자주 사용하는 자료 구조에 따른 시간 복잡도

 

  • 모든 순환함수는 반복문(iteration)으로 변경 가능하다.
  • 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.
  • 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
  • 하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)
  • 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
  • 모든 case는 결국 base case로 수렴해야 한다.

 

연습

 

미로찾기

미로

 

입구는 (0,0)이고 출구는 (n-1, n-1)일때 입구에서 출구까지 도착하는 경우의 수를 찾아보자

 

현재 위치에서 출구까지 가는 경로가 있으려면

  1. 현재 위치가 출구이거나 혹은
  2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경우가 있거나

둘 중 하나이다.

 

우선 답이 yes 인지 no 인지 경로가 있는지 없는지 생각해보자

boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
	if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
    	return true;
    } else {
    	for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
        	if (x', y') is on the pathway { // 벽이 아니라면
            	if findPath(x', y') {
                	return true;
                }
            }
        }
        return false;	
    }
}

 

간략하게 생각해보면 위와 같이 생각해볼 수 있다. 위에 코드가 무한루프에 빠지는지 반드시 확인해봐야 한다. 

이건 무한루프에 빠질 수 있다. (x',y') 입장에서 (x, y)는 다시 인접한 셀이된다. 그래서 무한하게 양쪽 셀을 반복하는 경우가 발생할 수 있다.

 

그렇기 때문에 내가 방문했던 적이 있는 셀인지 아닌지 확인하는 코드가 더 들어가야 한다.

 

boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
	if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
    	return true;
    } else {
    	mark (x, y) as a visited cell; // 방문했다고 표시한다.
    	for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
        	if (x', y') is on the pathway and not visited { // 벽이 아니고 방문한 적이 없는 경우
            	if findPath(x', y') {
                	return true;
                }
            }
        }
        return false;	
    }
}

 

 

자바코드로 풀이해보자

입력값

 

public static boolean findMazePath(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N) { // x,y가 범위를 벗어나는 경우
    	return false;
    } else if (maze[x][y] != PATHWAY_COLOUR) { // 길이 아닌 경우
    	return false;
    } else if (x == N-1 && y == N-1) { // 도착지점에 도착한 경우
    	maze[x][y] = PATH_COLOUR;
        return true;
    } else { 
    	maze[x][y] = PATH_COLOUR; // 방문한 곳으로 변경한다.
        if (findMazePath(x-1, y) || findMazePath(x, y+1) 
        	|| findMazePath(x+1, y) || findMazePath(x, y-1)) {
            	return true;
            }
            maze[x][y] = BLOCKED_COLOUR; 
            return false;
    }
}

'자료구조&알고리즘' 카테고리의 다른 글

시간복잡도  (0) 2023.09.19
Array에서 Index는 왜 0부터 시작할까?  (1) 2023.09.15
List 와 Set  (0) 2023.09.12
Array List 와 Linked List  (0) 2023.09.08
Array 와 List 의 차이  (0) 2023.09.08

+ Recent posts