728x90
반응형
SMALL

가장 먼저 작업할 내용은 AndroidDriver를 초기화해야 한다.

AndroidDriver는 어떤 역할을 하냐면, 연결된 Real Device를 PC에서 컨트롤할 수 있게 해주는 말 그대로 드라이버이다.

 

그리고 이 Driver는 모든 테스트를 돌리면서 딱 한개만 있으면 된다. 그래서, 싱글톤 패턴으로 드라이버를 초기화하는 클래스가 필요하다.

프로젝트 구조

└── src
    ├── main
    │   ├── java
    │   │   └── kro
    │   │       └── kr
    │   │           └── tbell
    │   └── resources
    └── test
        ├── java
        │   ├── AppiumSampleTest.java
        │   └── kro
        │       └── kr
        │           └── tbell
        │               ├── AppiumConnector.java
        │               ├── Constants.java
        │               ├── cucumber
        │               │   └── CucumberRunner.java
        │               └── stepdefinitions
        │                   └── PocFeatureStepDefs.java
        └── resources
            ├── env.yaml
            └── features
                └── poc.feature

 

자바 프로젝트를 만들면, src폴더 내부에 main, test 두 개의 폴더가 기본으로 생성된다.

여기서 test 폴더에서 우리가 원하는 구조를 만들어 나갈 것.

AppiumConnector 클래스

AppiumConnector

package kro.kr.tbell;

import io.appium.java_client.AppiumBy;
import io.appium.java_client.android.AndroidDriver;
import io.appium.java_client.android.options.UiAutomator2Options;
import lombok.extern.slf4j.Slf4j;
import org.openqa.selenium.WebElement;
import org.yaml.snakeyaml.Yaml;

import java.io.InputStream;
import java.net.MalformedURLException;
import java.net.URI;
import java.net.URL;
import java.util.Map;

@Slf4j
public class AppiumConnector {
    private static AndroidDriver androidDriver;

    private static final Yaml yaml = new Yaml();

    private AppiumConnector() {}

    private static AndroidDriver getAndroidDriver() {
        if (androidDriver == null) {
            Map<String, Object> env = initializeYaml();

            String udid = (String) env.get("udid");
            String url = (String) env.get("url");

            try {
                URL appiumServer = URI.create(url).toURL();
                UiAutomator2Options options = new UiAutomator2Options().setUdid(udid);

                androidDriver = new AndroidDriver(appiumServer, options);
            } catch (MalformedURLException e) {
                log.error("[getAndroidDriver]: MalformedURLException", e);
                throw new RuntimeException(e);
            }
        }
        return androidDriver;
    }

    private static Map<String, Object> initializeYaml() {
        InputStream inputStream = AppiumConnector.class
                .getClassLoader()
                .getResourceAsStream("env.yaml");

        return yaml.load(inputStream);
    }

    public static WebElement getElementById(String id) {
        return getAndroidDriver().findElement(AppiumBy.id(id));
    }
}

 

이 클래스에서 핵심은 AndroidDriver 타입의 드라이버를 한번만 초기화하고, 해당 드라이버를 통해 Real Device에 접근하는 것이다.

외부에서 직접 접근하지 못하도록 private으로 선언한 두 개의 필드.

private static AndroidDriver androidDriver;
private static final Yaml yaml = new Yaml();

 

AndroidDriver 타입의 androidDriver 필드는 Real Device와 통신하기 위한 드라이버이다.

Yaml 타입의 yaml 필드는 resources 폴더 내 .yaml 파일에서 설정한 변수들을 가져오기 위해 필요한 필드이다. 

 

그래서 드라이버를 초기화하거나, 이전에 초기화했다면 기존 드라이버를 반환하는 메서드 getAndroidDriver().

private static AndroidDriver getAndroidDriver() {
    if (androidDriver == null) {
        Map<String, Object> env = initializeYaml();

        String udid = (String) env.get("udid");
        String url = (String) env.get("url");

        try {
            URL appiumServer = URI.create(url).toURL();
            UiAutomator2Options options = new UiAutomator2Options().setUdid(udid);

            androidDriver = new AndroidDriver(appiumServer, options);
        } catch (MalformedURLException e) {
            log.error("[getAndroidDriver]: MalformedURLException", e);
            throw new RuntimeException(e);
        }
    }
    return androidDriver;
}

일단은 이 메서드는 private으로 만들었다. 외부에서 사용하지 않아도 될 것 같아서.

외부에서 사용안해도 되는 이유는 이후에 차차 만들면서 이해할 수 있다.

 

가장 첫번째는, 이 클래스의 클래스 변수인 androidDriver가 초기화 되지 않았는지를 판단한다. 초기화 되지 않았다면 초기화해야 한다.

initializeYaml() 메서드는 .yaml 파일을 읽어오기 위해 필요한 작업을 하는 메서드이다.

private static Map<String, Object> initializeYaml() {
    InputStream inputStream = AppiumConnector.class
            .getClassLoader()
            .getResourceAsStream("env.yaml");

    return yaml.load(inputStream);
}

 

내용은 간단하다. env.yaml 파일을 읽어서 InputStream으로 넣고 yaml이 해당 스트림을 읽으면 끝.

# env.yaml
url: http://0.0.0.0:4723
udid: HVA1FG23

 

yaml 변수에 저장된 값 중 udid, url 값을 읽어온다. 읽어오면 두가지 작업을 한다.

1. URL 타입으로 변환

2. UiAutomator2Options로 Capabilities를 설정할 수 있는데 여기서는 딱 하나 Udid만 설정했다.

 

AndroidDriver 인스턴스를 만들어낸 후 반환한다. 

 

이제 다음 메서드를 보자.

public static WebElement getElementById(String id) {
    return getAndroidDriver().findElement(AppiumBy.id(id));
}

이 메서드는 드라이버를 통해 Real Device와 연결해서 특정 Resource ID를 통해 UI 요소를 가져오는 메서드이다.

앞으로 이 메서드처럼 WebElement 자체를 반환하는 메서드만 public으로 만들어서 외부에서 사용하면 될 것 같아 드라이버를 받는 getAndroidDriver() 메서드는 private으로 선언했다.

 

코드 리팩토링

지금 상태에서 코드의 개선이 많이 필요해 보인다. 코드를 개선해보자.

 

첫번째, getAndroidDriver() 메서드는 멀티쓰레드 환경에서 안전하지 않다.

동시에 여러 쓰레드가 접근할 때 인스턴스가 여러번 생성될 수 있다. 이 부분을 해결해보자.

 

◾️ synchronized 키워드와 Double-Check Locking.

private static AndroidDriver getAndroidDriver() {
    if (androidDriver == null) {
        synchronized (AppiumConnector.class) {
            if (androidDriver == null) {
               // androidDriver 인스턴스 초기화 
            }
        }
    }
}

synchronized 키워드는 메서드나 코드 블럭에 대한 동시 접근을 제한해서 한 시점에 하나의 스레드만이 그 영역을 실행할 수 있게 하는 역할을 한다. 이를 사용해서 여러 스레드가 공유하는 데이터의 동시성 문제를 해결할 수 있다.

 

근데 If (androidDriver == null) 두번 체크한다.

1. 성능 최적화: 첫번째 if로 체크해서 null이 아니라면 synchronized 블록을 비롯한 추가적인 처리 없이 바로 반환된다. 이는 대부분의 호출에서 락을 획득하는 비용을 줄일 수 있다.

2. 스레드 안정성 보장: 만약, 첫번째 검사에서 null임이 판명되면, synchronized 블록으로 진입한다. 이 블록 내에서 한번 더 검사하는 이유는 두번째 스레드 이상이 동시에 블록 안으로 들어와 대기하고 있는 경우, 첫번째 스레드가 이미 객체를 생성했을 가능성을 다시 한번 검사하기 위함이다. 즉, 이중 검사를 통해 객체가 중복 생성되는 것을 방지한다.

 

◾️ try-with-resourceInputStream 자원 해제 및 에러 처리

private static Map<String, Object> initializeYaml() {
    try (InputStream inputStream = AppiumConnector.class
            .getClassLoader()
            .getResourceAsStream("env.yaml")) {

        if (inputStream == null) {
            throw new IllegalStateException("env.yaml not found.");
        }

        return yaml.load(inputStream);
    } catch (IOException e) {
        log.error("[initializeYaml]: Error occurred when loading yaml file ", e);
        throw new RuntimeException(e);
    }
}

 

1. InputStream은 사용 후 반드시 닫아야 한다. 닫는 코드를 작성하거나 아예 try-with-resource 구문으로 사용후 끝나면 자동으로 닫아주는 방식을 택해 자원 해제를 해준다.

2. 찾고자 하는 yaml 파일이 없는 경우를 대비해 if (inputStream == null) 체크를 한다.

3. yaml 파일을 읽어들이는 중 발생하는 에러를 catch 구문으로 처리한다.

 

 

◾️공개 메서드인 경우 명확한 문서화

/**
 * 주어진 ID를 가진 웹 요소를 찾아 반환합니다.
 * 이 메서드는 안드로이드 드라이버를 사용하여 애플리케이션에서 해당 ID를 가진 요소를 검색합니다.
 *
 * @param id 찾고자 하는 웹 요소의 resource id 입니다.
 * @return WebElement 객체를 반환합니다. ID에 해당하는 요소가 없는 경우 {@code null}을 반환할 수 있습니다.
 * @throws org.openqa.selenium.NoSuchElementException 요소를 찾을 수 없는 경우 발생합니다.
 * @throws IllegalStateException AndroidDriver가 초기화되지 않았거나 접근할 수 없는 경우 발생합니다.
 * @throws org.openqa.selenium.WebDriverException 드라이버와의 통신 중 문제가 발생한 경우 발생합니다.
 * */
public static WebElement getElementById(String id) {
    return getAndroidDriver().findElement(AppiumBy.id(id));
}

외부에서 이 메서드를 가져다가 사용하는 클라이언트 코드 쪽(여러 서비스)에서 어떤 메서드인지 명확히 이해할 수 있게 JavaDoc을 활용하자. 어떤 파라미터를 줘야 하는지, null을 반환할수 있는지 없는지, 어떤 에러를 던질 수 있는지 등을 말이다.

 

리팩토링 후 최종 코드

AppiumConnector

package kro.kr.tbell;

import io.appium.java_client.AppiumBy;
import io.appium.java_client.android.AndroidDriver;
import io.appium.java_client.android.options.UiAutomator2Options;
import lombok.extern.slf4j.Slf4j;
import org.openqa.selenium.WebElement;
import org.yaml.snakeyaml.Yaml;

import java.io.IOException;
import java.io.InputStream;
import java.net.MalformedURLException;
import java.net.URI;
import java.net.URL;
import java.util.Map;

@Slf4j
public class AppiumConnector {
    private static AndroidDriver androidDriver;

    private static final Yaml yaml = new Yaml();

    private AppiumConnector() {}

    private static AndroidDriver getAndroidDriver() {
        if (androidDriver == null) {
            synchronized (AppiumConnector.class) {
                if (androidDriver == null) {
                    Map<String, Object> env = initializeYaml();

                    String udid = (String) env.get("udid");
                    String url = (String) env.get("url");

                    try {
                        URL appiumServer = URI.create(url).toURL();
                        UiAutomator2Options options = new UiAutomator2Options().setUdid(udid);

                        androidDriver = new AndroidDriver(appiumServer, options);
                    } catch (MalformedURLException e) {
                        log.error("[getAndroidDriver]: MalformedURLException", e);
                        throw new RuntimeException(e);
                    }
                }
            }
        }
        return androidDriver;
    }

    private static Map<String, Object> initializeYaml() {
        try (InputStream inputStream = AppiumConnector.class
                .getClassLoader()
                .getResourceAsStream("env.yaml")) {

            if (inputStream == null) {
                throw new IllegalStateException("env.yaml not found.");
            }

            return yaml.load(inputStream);
        } catch (IOException e) {
            log.error("[initializeYaml]: Error occurred when loading yaml file ", e);
            throw new RuntimeException(e);
        }
    }

    /**
     * 주어진 ID를 가진 웹 요소를 찾아 반환합니다.
     * 이 메서드는 안드로이드 드라이버를 사용하여 애플리케이션에서 해당 ID를 가진 요소를 검색합니다.
     *
     * @param id 찾고자 하는 웹 요소의 resource id 입니다.
     * @return WebElement 객체를 반환합니다. ID에 해당하는 요소가 없는 경우 {@code null}을 반환할 수 있습니다.
     * @throws org.openqa.selenium.NoSuchElementException 요소를 찾을 수 없는 경우 발생합니다.
     * @throws IllegalStateException AndroidDriver가 초기화되지 않았거나 접근할 수 없는 경우 발생합니다.
     * @throws org.openqa.selenium.WebDriverException 드라이버와의 통신 중 문제가 발생한 경우 발생합니다.
     * */
    public static WebElement getElementById(String id) {
        return getAndroidDriver().findElement(AppiumBy.id(id));
    }
}

 

Runner 클래스 만들기

BDD 방법론에 맞게 Gherkin 문법으로 테스트 시나리오를 작성을 하고, 그 시나리오를 수행하려면 Cucumber의 도움을 받아야 한다.

Cucumber가 Gherkin 테스트 시나리오를 수행할 수 있게 해주는 도구이다.

 

CucumberRunner

package kro.kr.tbell.cucumber;

import io.cucumber.junit.Cucumber;
import io.cucumber.junit.CucumberOptions;
import org.junit.runner.RunWith;

@RunWith(Cucumber.class)
@CucumberOptions(
        features = {"src/test/kro/kr/tbell/features"},
        glue = "stepDefs"
)
public class CucumberRunner {

}

 

@RunWith(Cucumber.class) 애노테이션은 JUnit 프레임워크에서 테스트를 실행할 때 사용되는 실행자(runner)를 지정한다.

여기서 Cucumber.class를 사용함으로써, JUnit은 표준 테스트 실행자 대신 Cucumber 테스트 실행자를 사용하게 됩니다.

 

이렇게 하면 다음과 같은 작업을 한다.

  • Feature 파일 파싱: features 옵션에서 지정된 경로 내의 .feature 파일들을 찾아서 파싱한다. 이 파일들은 Gherkin 언어로 작성된 사용자 스토리나 비즈니스 요구사항을 담은 테스트 시나리오들이라고 보면 된다.
  • 스텝 정의와 연결: 실행자는 각 스텝(Given, When, Then)이 구현된 자바 메서드와 .feature 파일 내의 스텝을 연결한다. 이 연결은 glue 옵션에서 지정된 패키지 내에서 이루어진다.
  • 테스트 실행: 연결된 스텝 정의를 사용하여 실제 테스트를 실행하고 결과를 보고한다.

결과적으로 @RunWtih(Cucumber.class)는 Cucumber를 사용하여 BDD 접근 방식으로 정의된 테스트를 JUnit 환경에서 실행할 수 있도록 설정한다. 


Feature 파일 만들기

poc.feature

Feature: POC Feature

  Scenario: 테스트 케이스 1번
    When 개발 HTTPS 서버 버튼 클릭
    Then 간편 비밀번호 입력 문구가 노출된다

 

BDD 접근 방식으로 정의된 Gherkin 문법으로 만들어진 테스트 시나리오를 가진 poc.feature 파일이다.

.feature 파일은 대분류 Feature가 있고 소분류 Scenario가 있다.

 

Feature는 이 .feature 파일이 어떤 부분을 커버하는지를 어떤 화면도 좋다. 어떤 파트도 좋다. 큰 분류를 담당한다.

Scenario는 그 파트에서 커버되어야 할 시나리오들을 쭉 작성하는데 하나하나의 시나리오를 말한다.

 

그래서 Given - When - Then 키워드로 시나리오를 작성한다.

StepDefinition 파일 만들기

저 Feature 파일에 정의한 각각의 스텝들(Given, When, Then)에 대한 코드를 작성하는 부분이다.

PocFeatureStepDefs

package kro.kr.tbell.stepDefs;

import io.cucumber.java.en.Then;
import io.cucumber.java.en.When;
import kro.kr.tbell.AppiumConnector;
import kro.kr.tbell.Constants;
import lombok.extern.slf4j.Slf4j;
import org.openqa.selenium.WebElement;

@Slf4j
public class PocFeatureStepDefs {

    @When("개발 HTTPS 서버 버튼 클릭")
    public void clickDevHttpsServerBtn() {
        WebElement devHttpsServerBtn =
                AppiumConnector.getElementById(Constants.DEV_HTTPS_SERVER_BUTTON_ID);

        devHttpsServerBtn.click();
    }


    @Then("간편 비밀번호 입력 문구가 노출된다")
    public void assertSimplePasswordText() {
        AppiumConnector
                .getElementById(Constants.SIMPLE_PASSWORD_TEXT_ID)
                .isDisplayed();
    }
}

 

이렇게 @When, @Then 애노테이션으로 어떤 스텝인지 명확하게 알 수 있어 가시성이 뛰어나다.

그리고 그 안에서 위에서 만든 싱글톤 패턴의 AppiumConnector 클래스의 클래스 변수 AndroidDriver를 가져와서 원하는 요소를 찾아내고 요소에 대해 어떤 행위를 한다. @Then에서 isDisplayed()는 보이지 않으면 그 자체로 에러를 반환하기 때문에 따로 Assertion이 필요가 없다. 

 

파라미터로 넘겨주는 값은 상수값으로 따로 정의를 했다.

Constants

package kro.kr.tbell;

public interface Constants {
    String DEV_HTTPS_SERVER_BUTTON_ID = "id-button-1"; //개발 HTTPS 서버 버튼 Resource ID
    String SIMPLE_PASSWORD_TEXT_ID = "id-title-1"; // 간편 비밀번호를 입력해주세요 문구 Resource ID
}

저 Resource ID는 Appium Inspector를 통해 알 수 있다. [아래 사진 참고]

테스트 실행

이제 제일 중요한 테스트를 직접 실행해보는 시간이다. 테스트 실행은 매우 간단하게 IDE에서 할 수 있다.

.feature 파일을 보면 좌측에 테스트 실행 버튼이 있고 Scenario 옆에 있는 버튼은 해당 시나리오만, Feature 옆에 있는 버튼은 해당 .feature 파일의 모든 시나리오를 수행한다.

 

실행해보면 JUnit으로 테스트하듯 똑같이 테스트가 진행된다. 

 

결과

 

테스트 실행을 IDE로 해봤지만 Jekins Pipeline을 사용하려면 IDE로 실행하는 법만 알아선 안된다.

 

Gradle + Cucumber 테스트 실행 (CLI)

우선, 커맨드라인으로 테스트를 실행하기 앞서, Gradle을 사용할땐 자주 사용되는 실행명령어가 있으면 그것을 task로 만들어 낼 수가 있다. 그래서 이 cucumber 실행 테스트를 task로 만들어보자.

 

build.gradle

configurations {
    cucumberRuntime {
        extendsFrom testImplementation
    }
}

tasks.register('cucumberRun') {
    dependsOn assemble, testClasses
    doLast {
        javaexec {

            main = 'io.cucumber.core.cli.Main'
            classpath = configurations.cucumberRuntime + sourceSets.main.output + sourceSets.test.output
            args = ['--glue', 'kro.kr.tbell.stepdefinitions',
                    'classpath:features',
                    '--plugin', 'pretty',
                    '--plugin', 'html:build/cucumber-report.html'
            ]
        }
    }
}

이 코드는 cucumber test를 위해 build.gradle에 추가적으로 설정해야 하는 코드이다.

 

configurations {
    cucumberRuntime {
        extendsFrom testImplementation
    }
}

Gradle Configuration은 빌드 과정에서 사용되는 종속성들을 관리하는 일종의 컨테이너 역할을 한다.

 

cucumberRuntime 이라는 configuration을 만들고, extendsFrom testImplementationcucumberRuntimetestImplementation으로 선언된 모든 종속성을 상속받는다는 의미이다. 즉,  testImplementation으로 선언된 모든 라이브러리 및 파일들이 cucumberRuntime에도 속하게 된다.

 

이렇게 설정하면, Cucumber와 관련된 테스트 실행 시 필요한 모든 종속성을 cucumberRuntime에 포함시킬 수 있으며, 추가적인 종속성을 cucumberRuntime에만 지정하여 관리할 수도 있다.

 

tasks.register('cucumberRun') {
    dependsOn assemble, testClasses
    doLast {
        javaexec {

            main = 'io.cucumber.core.cli.Main'
            classpath = configurations.cucumberRuntime + sourceSets.main.output + sourceSets.test.output
            args = ['--glue', 'kro.kr.tbell.stepdefinitions',
                    'classpath:features',
                    '--plugin', 'pretty',
                    '--plugin', 'html:build/cucumber-report.html'
            ]
        }
    }
}

cucumberRun 이라는 이름의 task를 만든다.

dependsOnGradle 빌드 스크립트에서 사용되는 키워드로, 하나의 Task가 다른 하나 또는 여러 Task의 실행 결과에 의존한다는 의미이다. 즉, 지정된 Task가 실행되기 전에 의존하는 Task들이 먼저 완료되어야 한다는 것을 의미한다.

 

그럼 저기서는 assemble, testClasses 두 개의 Task들이 먼저 완료가 되어야 한다는 것을 말한다.

  • assemble: 이 Task는 일반적으로 프로젝트의 모든 메인 소스 세트를 컴파일하고, 필요한 모든 리소스를 처리하며, 실행 가능한 Artifact(예: JAR파일)를 빌드하는 데 사용된다. assemble task는 메인 소스 코드가 변경되었을 때 변경사항을 반영하여 새로운 아티팩트를 만들어낸다.
  • testClasses: 이 Task는 프로젝트의 테스트 소스 코드를 컴파일한다. 테스트를 실행하기 전에 테스트 소스 코드가 최신 상태인지 확인하고 필요한 경우 컴파일을 수행하여 테스트 실행 준비를 마친다. testClasses Task는 테스트 코드에 대한 변경사항이 있을 때마다 테스트를 다시 컴파일하여 최신 상태로 유지한다.

 

그 다음 doLast는 Gradle 태스크의 생명주기 중 '실행'단계가 끝난 후 실행할 작업을 추가하는 메서드다. 태스크가 주 작업을 완료한 후 실행되어야 하는 추가적인 작업들을 정의할 때 사용된다. 그래서 do'Last'이다. 보통은 그래서 정리 작업, 로깅, 조건부 추가 작업등을 위해 사용된다. 

 

그 안에서 javaexec가 있는데 이건 Gradle에서 Java 프로그램을 실행하기 위한 built-in 함수다. 이 메서드를 통해 Java 애플리케이션을 실행하거나, Java 기반의 커맨드라인 도구를 호출할 수 있다. javaexec 블록 내에서는 실행할 Java 클래스, 클래스패스, 프로그램 인자 등을 설정할 수 있다.

 

  • main: javaexec에서 실행할 메인 클래스를 지정한다. 여기서는 Cucumber의 커맨드라인 인터페이스인 'io.cucumber.core.cli.Main'이 지정됐다. 이 클래스는 Cucumber 테스트를 실행하는 엔트리 포인트이다.
  • classpath: 실행 시 클래스패스를 지정한다. configuration.cucumberRuntime + sourceSets.main.output + sourceSets.test.output을 통해 Cucumber 실행에 필요한 모든 종속성과 컴파일된 클래스 파일들이 포함된 클래스패스를 구성했다. 'sourceSets.main.output' 이 녀석은 프로젝트의 메인 소스 셋 (src/main/java및 src/main/resources에 위치한 소스들)이 컴파일된 후 생성된 모든 클래스 및 리소스 파일들의 출력 위치를 가리킨다. 'sourceSets.test.output' 이 녀석은 테스트 소스 셋(src/test/javasrc/test/resources)이 컴파일 된 후 생성된 모든 클래스 및 리소스 파일들의 출력 위치를 나타낸다.
  • args: 프로그램 실행 시 건네 줄 인자를 작성한다.
    • --glue: Cucumber가 스텝 정의를 찾을 수 있는 패키지 경로
    • classpath:features: Cucumber가 feature 파일들을 찾을 경로 classpath에 src/test/resources가 정의되어 있으니 그 안에 features 폴더에서 .feature 파일을 찾겠다는 의미가 된다.
    • --plugin pretty: Cucumber 실행 결과를 사람이 읽기 좋게 출력하는 플러그인을 활성화
    • --plugin html:build/cucumber-report.html: 테스트 결과를 HTML 형식으로 build/cucumber-report.html에 저장

 

이렇게 설정한 Task를 커맨드라인을 통해 실행만 하면 된다.

./gradlew cucumberRun // gradlew 또는 gradle로 실행하면 된다.

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

Appium, OpenCV를 활용한 Visual Testing  (0) 2024.04.25
5. 프로젝트 환경 설정  (2) 2024.04.17
4. Appium Inspector 연결  (0) 2024.04.17
3. APK 설치  (0) 2024.04.17
2. Appium  (0) 2024.04.17
728x90
반응형
SMALL

IntelliJ 프로젝트 만들기

이제 IntelliJ로 프로젝트 환경 설정을 해보자. 우선, Gradle 프로젝트를 하나 만들자.

이름과 경로는 적절하게 설정을 해준다.

Build system은 Gradle로 설정하자. 난 Gradle을 좋아하니까.

 

JDK버전은 11이상이면 좋은데 난 가장 최신 버전인 21을 사용하겠다.

그 외 나머지는 기본 설정으로하고 'Create' 클릭

 

build.gradle

가장 먼저 확인할 파일은 역시 build.gradle 파일이다. 

plugins {
    id 'java'
}

group = 'kro.kr.tbell'
version = '1.0.0'

repositories {
    mavenCentral()
}

dependencies {
    testImplementation platform('org.junit:junit-bom:5.10.0')
    testImplementation 'org.junit.jupiter:junit-jupiter'
}

test {
    useJUnitPlatform()
}

 

가장 간단한 상태이다. 여기서 appium 관련 라이브러리를 추가해야한다.

Appium java client 추가하기

dependencies {
    ...
    testImplementation 'io.appium:java-client:9.2.2'
    implementation 'io.appium:java-client:9.2.2'
    ...
}

저렇게 두 개를 해놔야 테스트 파일이 아닌곳에서도 Appium을 사용할 수 있고 내가 원하는 구조 또한 그렇다. 그래서 testImplementation, implementation 모두 추가해주자.

참고로 버전은 9.2.2가 가장 최신버전이다. (2024년 4월 17일 기준)

 

 

추가하고 빌드를 하면 이렇게 External Libraries에 매우 많은 것들이 추가된다.

io.appium.java-client를 내려받기 위해 필요한 sub-dependencies가 이렇게나 많다.

Cucumber 라이브러리 추가하기

Cucumber는 BDD 개발 방법론에 맞게 작성된 Gherkin 테스트 시나리오를 실제로 실행할 수 있도록 해주는 툴이라고 했다.

그래서 이 툴 역시 내려받아야 한다.

build.gradle

dependencies {
   ...
   implementation 'io.cucumber:cucumber-java:7.4.1'
   implementation 'io.cucumber:cucumber-junit:7.4.1'
   ...
}

 

그 외 유용한 라이브러리 추가하기

Lombok, Slf4j, SnakeYAML을 설치한다.

// Lombok
compileOnly 'org.projectlombok:lombok:1.18.30'
annotationProcessor 'org.projectlombok:lombok:1.18.30'
testCompileOnly 'org.projectlombok:lombok:1.18.30'
testAnnotationProcessor 'org.projectlombok:lombok:1.18.30'

//SLF4J API 모듈
implementation 'org.slf4j:slf4j-api:2.0.9'
testImplementation 'org.slf4j:slf4j-api:2.0.9'

// Logback Classic 구현 (SLF4J의 구현체)
implementation 'ch.qos.logback:logback-classic:1.4.14'
testImplementation 'ch.qos.logback:logback-classic:1.4.14'

// SnakeYAML
implementation 'org.yaml:snakeyaml:2.2'
testImplementation 'org.yaml:snakeyaml:2.2'

 

SnakeYAML은 .yaml 파일에 내가 정의한 key/value를 넣었을 때, 원하는 key에 해당하는 value를 읽어들이는 방법이다.

이렇게까지 라이브러리를 다운받으면 지금 당장 필요한 모든 라이브러리는 다 받았다. 이제 작업을 해보자.

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

Appium, OpenCV를 활용한 Visual Testing  (0) 2024.04.25
6. Appium과 Cucumber를 이용해 UI Automation Testing  (0) 2024.04.17
4. Appium Inspector 연결  (0) 2024.04.17
3. APK 설치  (0) 2024.04.17
2. Appium  (0) 2024.04.17
728x90
반응형
SMALL

이제 Appium Inspector를 사용해서 UI 테스트를 하고자하는 App과 연결해보자.

 

UiAutomator2 Driver 설치

실행 하기전 "UiAutomator2" Driver를 설치해야 한다.

appium driver install uiautomator2

성공적으로 설치가 되면 다음과 같은 화면이 나오면 된다.

Appim Server 실행

이제 appium을 실행한다.

appium

이러한 화면이 나오면 성공!

Appium Inspector 실행

이제 Appium Inspector를 실행한다.

 

  • Remote Host: 0.0.0.0
  • Remote Port: 4723
  • Remote Path: /
  • Capability Builder
    • appium:udid: 연결할 Device udid
    • platformName: Android
    • appium:automationName: UiAutomator2
    • appium:skipUnlock: false
    • appium:autoGrantPermissions: true

여기서 Capability Builder 옵션은 그때그때 다를 수 있다. 나는 이렇게 해도 무방하기에 이렇게 설정했다.

이 옵션들이 어떤 내용인지 더 자세히 알고 싶다면 다음 링크를 참조하자.

 

GitHub - appium/appium-uiautomator2-driver: Appium driver for Android UIAutomator2

Appium driver for Android UIAutomator2. Contribute to appium/appium-uiautomator2-driver development by creating an account on GitHub.

github.com

 

우측 하단 Start Session 버튼을 클릭하면 연결된다.

이렇게 내가 연결한 Device의 화면을 캡쳐해서 각 요소들에 대한 정보들을 뽑아낼 수 있다.

 

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

6. Appium과 Cucumber를 이용해 UI Automation Testing  (0) 2024.04.17
5. 프로젝트 환경 설정  (2) 2024.04.17
3. APK 설치  (0) 2024.04.17
2. Appium  (0) 2024.04.17
1. BDD, Gherkin, Cucumber  (0) 2024.04.17
728x90
반응형
SMALL

App 테스트를 하려면 App을 설치할 Device가 필요하다.

이 때 두가지 경우로 나눌 수 있다.

  • Emulator: Android Virtual Device (AVD)
  • Real Device

Emulator를 사용하는 경우에는 Android Studio를 사용해서 AVD를 설치하면 된다. 이거는 이 포스팅 범주에서 벗어난 범위이기 때문에 여기에 작성하지는 않겠다.

 

Real Device를 사용하는 경우에는 USB Debugging을 활성화 시키면 된다. 나의 경우 Real Device를 사용할 것.

PC에 Real Device를 연결하고, USB Debugging 활성화가 됐다고 가정하고 시작한다.

 

Real Device에 APK 설치

우선, 내 APK 경로는 다음 경로에 있다.

/Users/choichiwon/apk/apkfile.apk

 

Real Device에 APK를 설치하는 방법은 다양한데 CLI를 통해 설치할 것.

CLI를 통해 설치하려면 Android SDK가 설치되어 있어야 한다. (물론 설치를 떠나서 Appium과 Andorid App을 사용해서 테스트 하려면 무조건 필요하다).

Android SDK 설치 방법
가장 쉬운 방법은 Android Studio를 설치하고, 이 경로에서 원하는 버전으로 설치하면 된다.
Settings -> Appearance & Behavior -> System Settings -> Android SDK

설치할 때 이 두가지를 설치하면 된다. 
- Android SDK Platform
- Android SDK Platform-Tools

 

설치가 다 끝나면 Platform-tools가 위치한 경로가 있다. 나의 경로는 다음과 같다.

/Users/choichiwon/Library/Android/sdk/platform-tools


여기에 "adb"라는 도구가 있다. 이건 Android Debug Bridge의 약자로 이 도구는 개발자가 Android 기기와 상호작용할 수 있도록 하는 명령줄 도구인데 이 도구를 이용해서 현재 연결된 디바이스 리스트를 가져올 수 있다.

./adb devices

 

연결된 디바이스 하나가 보인다. 이렇게 디바이스가 나오면 "adb"를 통해서 이 디바이스와 통신을 할 수 있다.

"adb" 명령어를 이용해서 apk를 설치해보자.

./adb install -r /Users/choichiwon/apk/apkfile.apk

이 명령어가 "adb"를 이용해서 apk를 설치하는 명령어이다. 경로는 당연히 apk가 있는 경로를 지정해주면 되고, 디바이스가 하나만 연결되어 있으면 디바이스 정보를 주지 않아도 된다. "./adb devices" 를 입력했을 때 여러 디바이스가 나오면 어떤 디바이스에 설치할지 명시해줘야 한다. 아래가 그 예시이다.

./adb -s HVA1FG23 install -r "apk file path"

 

옵션 정보는 다음과 같다.

  • -r: replace. 이미 설치되어 있으면 지우고 재설치, 없으면 그냥 설치

입력하면 이러한 문구가 나온다.

Success가 나오면 정상 설치가 된 것.

 

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

6. Appium과 Cucumber를 이용해 UI Automation Testing  (0) 2024.04.17
5. 프로젝트 환경 설정  (2) 2024.04.17
4. Appium Inspector 연결  (0) 2024.04.17
2. Appium  (0) 2024.04.17
1. BDD, Gherkin, Cucumber  (0) 2024.04.17
728x90
반응형
SMALL

멀티 플랫폼(Web, Mobile, Desktop, ...)을 대상으로 UI 자동화 테스트를 할 수 있게 해주는 오픈 소스 프로젝트인 Appium.

이 Appium을 사용해서 Mobile App 자동화 테스트를 진행해 볼 생각이다.

 

Appium Install

우선, Appium을 사용하려면 설치를 해야한다.

 

Install Appium - Appium Documentation

Install Appium You can install Appium globally using npm: Note Other package managers are not currently supported. After installation, you should be able to run Appium from the command line: You should see some output that starts with a line like this: [Ap

appium.io

이 링크에서 Appium을 설치할 수 있다. 간단하게는 NPM이 설치되어 있다면 다음 명령어를 실행하자.

npm i -g appium

 

설치가 다 되면 다음 명령어를 실행해서 정상적으로 설치됐는지 확인해보자.

appium -v

Upgrade Appium version

Appium이 설치되어 있는 상태인데, 버전이 Outdate 상태라면 다음 명령어로 업데이트해주자.

npm update -g appium

 

Appium Inspector

Appium을 사용하면 반드시 같이 사용할 수 밖에 없는 GUI Inspector tool.

좋은점은 모든 종류의 Mobile App을 지원한다는 것이고 무료이다.

 

요래 생긴 툴이다.

 

Install

 

Releases · appium/appium-inspector

A GUI inspector for mobile apps and more, powered by a (separately installed) Appium server - appium/appium-inspector

github.com

이 링크에서 OS별, 버전별로 설치가 가능하다. 가장 최신의 버전을 선택해서 내려받으면 된다.

나의 경우 MacOS이기 때문에 .dmg 파일을 내려받아서 설치했다.

 

그리고 설치하고 실행하면 이 경고 문구가 나온다.

이제 다음 명령어를 수행하면 된다. 

xattr -cr "/Applications/Appium Inspector.app"

 

요 명령어를 수행하면 정상적으로 실행이 될 것이다. 아니면 System Settings > Privacy & Security 탭에 가서 하단에 Security 쪽에 보면 "Appium Inspector가 검사되지 않은 앱인데 실행을 할거냐?" 뭐 이렇게 물어보는데 [Open Anyway] 버튼 클릭하면 된다.

 

실행한 화면은 다음과 비슷하면 된다.

 

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

6. Appium과 Cucumber를 이용해 UI Automation Testing  (0) 2024.04.17
5. 프로젝트 환경 설정  (2) 2024.04.17
4. Appium Inspector 연결  (0) 2024.04.17
3. APK 설치  (0) 2024.04.17
1. BDD, Gherkin, Cucumber  (0) 2024.04.17
728x90
반응형
SMALL

테스트 자동화 인프라 구축 프로젝트를 여러번 진행해 오면서 알게된 내용과 필요한 내용을 정리하고자 한다.

 

BDD(Behavior Driven Development)

행위 주도 개발이라는 뜻의 개발방법론인 BDD

소프트웨어 개발 과정을 개선하기 위해 사용되는 방법론이다.

Agile 개발 방법론의 일종으로, 소프트웨어 프로젝트의 개발을 가이드하기 위해 행동 기반의 언어를 사용한다.

행동 기반의 언어라는 건 이런 것이다.

1. B 화면이 보인다.
2. B화면의 우측 상단에 [A] 버튼을 클릭한다.
3. 클릭한 버튼 하단 셀렉트 박스에 [...] 텍스트가 확인된다.

 

이 방법론의 핵심은 개발자, 테스터, 비즈니스 분석가 등 프로젝트에 참여하는 모든 사람이 소프트웨어의 동작을 명확하고 이해하기 쉬운 방식으로 정의하고, 이러한 동작을 기반으로 커뮤니케이션하며, 결국에는 테스트와 개발을 진행하는 것이다.

 

BDD는 기능적 요구사항을 사람이 읽을 수 있는 언어로 작성된 시나리오로 변환하여 기술적인 사양과 비즈니스 요구 사이의 이해를 돕는다.

 

Gherkin

BDD의 구현을 위해 사용되는 도메인 특화 언어(Domain Specific Language, DSL)이다. 

사람이 읽을 수 있는 말로 작성되며, 특정 기능이 어떻게 동작해야 하는지를 시나리오 형식으로 기술한다.

Gherkin으로 작성된 시나리오는 주로 Given - When - Then 형식을 따른다.

  • Given: 테스트의 전제 조건
  • When: 수행할 액션
  • Then: 예상 결과

이런 방식으로 Gherkin은 비즈니스 로직을 명확하게 기술하고 이를 바탕으로 테스트 케이스를 만들어 내는데 이상적인 문법이다.

 

Cucumber

Gherkin으로 작성된 시나리오도 결국 테스트 시나리오이니까 실행할 수 있는 도구가 필요하다.

그 도구가 Cucumber라는 소프트웨어 툴이다.

 

이는, BDD 프로세스를 지원하기 위해 설계되었으며, Gherkin 시나리오를 자동화 된 테스트로 변환한다.

Cucumber는 다양한 프로그래밍 언어를 지원하고 개발자가 Gherkin 시나리오를 바탕으로 테스트 코드를 작성할 수 있도록 해준다.

결과적으로 Cucumber를 사용함으로써 팀은 비즈니스 요구사항이 정확히 이해되고 충족되는지를 보다 쉽게 검증할 수 있다.

 

BDD, Gherkin, Cucumber와 자동화

이 방법론과 도구는 함께 작동할 때 가장 효과적이다. BDD는 프로세스와 커뮤니케이션의 틀을 제공하며, Gherkin은 이 틀 내에서 비즈니스 요구사항을 명확하고 일관된 형식으로 기술하는 방법을 언어적으로 풀어 제공한다. 마지막으로 Cucumber는 Gherkin으로 작성된 시나리오를 실행 가능한 테스트로 전환하여, 요구사항이 제대로 충족되었는지를 자동으로 검증할 수 있게 해준다.

 

이러한 조합은 비즈니스 요구사항을 정확하게 이해하고, 이를 기반으로 고품질의 소프트웨어를 더 빠르게 개발하는 데 도움을 준다.

또한 사람이 읽을 수 있는 언어로 애플리케이션의 기능을 설명하듯 테스트 시나리오를 만들기 때문에  애플리케이션의 특정 기능에 대한 문서화가 대체될 수 있다는 점에서 장점을 가진다고 볼 수 있다.

그래서 결국 더 예측 가능하고 관리 가능하며 비즈니스 요구사항과 기술적 구현 사이의 간극을 줄이는 데 초점을 맞추고 있다.

 

728x90
반응형
LIST

'테스트 자동화' 카테고리의 다른 글

6. Appium과 Cucumber를 이용해 UI Automation Testing  (0) 2024.04.17
5. 프로젝트 환경 설정  (2) 2024.04.17
4. Appium Inspector 연결  (0) 2024.04.17
3. APK 설치  (0) 2024.04.17
2. Appium  (0) 2024.04.17
728x90
반응형
SMALL

Hash TableKey/Value Pair를 빠르게 저장하고 읽을 수 있는 자료구조이다.

파이썬에서 Dictionary라고 부르는 것이 이 Hash Table이다.

 

예를 들어, Key: Food, Value: Kimchi를 Hash Table에 저장하고자 하면 Hash Table한테 Key가 Food고 Value가 Kimchi인 이 Pair를 저장해 줘! 하고 저장을 한 다음 이후에 Food라는 Key의 Value가 어떻게 돼?라고 물어보면 Hash Table이 Kimchi입니다라고 말해주는 자료구조.

 

Hash Table의 구현 원리

이름 그대로 Table(배열)Hash Function으로 구성되어 있다.

 

Hash Function은 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다.

 

쉽게 말하면 어떤 값이던간에 이 Hash Function에 넣으면 고정된 값(예를 들어 숫자)으로 만들어준다는 것을 말한다.

다음 그림을 보자.

어떤 값을 Input으로 만들던간에 Hash Function에 넣으면 위 조건처럼 10보다 작은 숫자 뱉어낸다.

중요한 건, Input이 같은 값이라면 Output도 무조건 같은 값으로 나온다.

 

 

그래서 Hash Table의 구성은 다음과 같다.

  • Size가 N인 배열(Table)
  • Output이 N보다 작은 Hash Function

그래서 그림으로 보면 다음과 같다.

Hash Function, Table이 있는 Hash Table.

그래서 누군가가 Key "Food", Value "Kimchi"라는 Pair를 이 Hash Table에 저장하겠다고 한다.

 

1. Hash Table은 저 Key를 Hash Function에 집어넣는다. 그리고 나온 Output은 4.

2. 4라는 숫자를 가진 인덱스에 Value를 저장한다.

 

이게 아주 간단한 Hash Table인데 문제가 있다. 충돌의 문제.

예를 들어, 10개 이상의 값을 이 Hash Table에 넣으면 결국 Hash Function은 0 -10 사이의 숫자만을 뱉어내는 녀석이기 때문에 그 값들 중엔 중복되는 값이 생길 수밖에 없다. 

 

간단한 예로, 위 그림처럼 인덱스 4에 Kimchi가 저장된 상태인데 누군가가 Key "FavoriteFood" Value "Pizza"라는 Pair를 이 Hash Table에 저장하려고 시도하는데 Hash Function이 같은 4를 뱉어냈다고 생각해 보면 아래 그림처럼 된다.

그럼 아까 Food/Kimchi를 저장했던 사람이 Food에 담긴 Value뭐야? 라고 물어보면 이 Hash Table은 Pizza라는 엉뚱한 값을 뱉을 수 있게 된다. 이걸 어떻게 해결할까?

 

Hash Table의 Collision 해결 방법

크게 두가지 방법이 있다.

  • Chaining
  • Probing

Chaining

우선 첫번째 방법인 Chaining은 그냥 배열을 쓰는 게 아니라 Linked List를 사용해서 Collision이 발생할 때마다 해당 인덱스(이 예시에선 4)에 있는 Linked List에 값을 연달아서 저장하는 것. 아래 그림을 보자.

위 문제를 이런식으로 해결했다. 해당 인덱스에 Linked List로 차곡차곡 똑같이 넣는 것. 대신 이제는 Value만 넣을 순 없다. 이 Linked List에 여러 값이 들어가니까 어떤 Key에 해당하는지 알기 위해 Key/Value를 같이 넣어줘야 한다.

 

그래서 이제 유저가 "Key가 Food인 Value 찾아줘!" 하고 Hash Table에 요청을 하면 Hash Table은 먼저 Hash Function에 Input으로 Food를 넣어서 나온 값 4를 가진 메모리에 가면 나오는 Linked List에서 Iterator를 돌려서 원하는 값(Kimchi)을 찾아내는 것.

참고: Linked List 말고 Binary Search Tree를 사용해도 된다. 이전 포스팅에서 정리한 Binary Search Tree. 이 녀석을 사용하면 원하는 값을 찾아내는 시간 복잡도는 O(log N)이기 때문에 더 효율적일 수도 있다. 상황에 따라.

 

Probing

Probing도 여러 가지 방법이 있는데 그중 가장 간단한 Linear Probing을 보면 배열을 그대로 쓰고 Hash Function이 같은 값을 뽑아내면 우선 그 자리에 가보는데 값이 있을 때 그 옆을 보는 방식이다. 아래 그림을 보자.

1. Food/Kimchi라는 Pair를 Hash Table에 넣었더니 4번에 들어간 상태이다.

2. Favorite Food/Pizza라는 Pair를 Hash Table에 넣으려고 시도하는데 같은 4번이 나왔고 4번 자리를 보니 이미 값이 있어서 Hash Table이 그 옆자리에 넣었다.

 

이게 Linear Probing이다. 그래서 Linear Probing을 정리하자면,

  • Linear Probing : 이미 자리에 값이 있으면 다음 자리에 추가한다.

근데, 이 문제의 단점이 있다. Collision이 많이 일어나면 그 주변에 병목현상이 생길 수 있다는 것.

예를 들어, 저 모양 그대로 HateFood/Coffee라는 Pair를 넣으려고 시도하는데 Hash Function이 또 4를 뱉어냈다. 그래서 4에 가보니 값이 있어서 그다음 5에 가보니 또 값이 있어서 6으로 가서야 넣게 됐다.

 

그래서 이 Linear Probing 문제를 또 해결하는 방법이 Quadratic Probing이다.

Quadratic Probing

다음 자리를 찾을 때 hash(x) + i가 아니라 hash(x) + i^2 자리에 넣는 방식이다. 그러니까 4가 나오면 Linear Probing은 5에 넣는 건데 Quadratic Probing은 16에 넣는다.

 

 

Hash Table의 시간 복잡도와 공간 복잡도

시간 복잡도

두 가지 케이스로 나뉠 수 있다.

  • Hash Collision이 없을 때
    • 데이터 추가  
      • Key 값 해시하기 O(1)
      • 데이터 넣기 O(1)
      • O(1) + O(1) = O(1)
    • 데이터 읽기
      • Key 값 해시하기 O(1)
      • 데이터 읽기 O(1)
      • O(1) + O(1) = O(1)
  • Hash Collision이 있을 때
    • 데이터 추가/읽기
      • Key 값 해시하기 O(1)
      • 최악의 경우 데이터 넣기, 읽기가 O(N)이 될 수 있음.
        • (왜냐하면, Hash Function이 잘못 만들어진 경우 계속해서 같은 Output을 만들어 내는 최악의 Hash Function이 있으면 Linked List 추가의 경우 마지막 자리를 알기 위해 1-N까지 데이터가 있을 때 처음부터 하나씩 자리를 찾아야 하고, 읽기의 경우 해당 데이터가 어디 있는지 알기 위해 N개의 노드를 다 뒤져야 할 수도 있으므로)
        • 근데, 이건 정말 최악의 경우인 거고 어지간하면 O(1)이 된다. 우선 Key 값 해시하는 건 언제나 O(1)이고 Hash Function이 문제없이 잘 만들어졌다면 바로바로 데이터를 넣거나 읽을 수 있게 된다.
    • 그래서 어지간하면 이 경우도 O(1)이 맞고, 정말 정말 잘못 만들어진 Hash Function이라면 O(N)이 될 수도 있다는 것으로 알아두면 좋을듯하다.

공간 복잡도

구분 없이 O(N)

N개의 데이터를 넣으려면 그에 맞는 배열 사이즈가 있어야 하고(N) 해당 데이터 타입의 Byte를 가지는 메모리 공간(X) = N * X => O(N).

728x90
반응형
LIST

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

배열과 Big O 표기법  (0) 2024.05.10
Binary Search Tree  (0) 2024.04.16
Tree와 BFS / DFS  (0) 2024.04.16
Stack  (0) 2024.04.15
Queue  (0) 2024.04.15
728x90
반응형
SMALL

Binary Search Tree는 진짜 중요한 개념이다.

Binary Tree를 저번 시간에 배웠고 이 Binary Tree를 다시 상기해보면 자식이 최대 2개까지만 있는 노드로만 구성되어 있는 트리를 Binary Tree라고 했고 이 트리를 탐색하는 방법 중 대표적인 두 가지 DFS, BFS가 있다고 했다.

 

DFS(Depth First Search)는 깊이 우선 탐색으로 밑으로 더 내려갈 수 없을때까지 계속 아래로 찾아나가는 방식.

BFS(Breadth First Search)는 한 노드의 모든 라인을 다 검색하고 그 바로 다음 아래 라인을 다 검색해가면서 찾아내는 방식이라고 했다.

 

Binary Search Tree

Binary Search Tree는 Binary Tree에 특정한 룰을 추가한 트리구조이다.

어떤 룰일까? 한 노드를 기준으로 왼쪽 Sub tree는 지금 노드보다 무조건 더 작은값, 오른쪽 Sub tree는 지금 노드보다 무조건 더 큰 값으로만 구성되어 있는 구조를 Binary Search Tree라고 한다.

이 트리는 완벽한 Binary Search Tree이다. 모든 노드를 기준으로 비교해도 왼쪽 Sub tree는 본인보다 작은 값을 가지고 있고, 오른쪽 Sub tree는 본인보다 큰 값을 가지고 있기 때문.

 

이 구조가 왜 좋고 왜 자주 사용될까? 절반 소거법(Binary Search), 다른말로 '분할 정복 방식'이 가능하기 때문에 효율적으로 원하는 값을 찾아낼 수 있기 때문이다.

예를 들어 저 트리에서 10을 찾고 싶다고 해보자. 다음 단계를 거쳐간다.

1단계

처음 루트 노드에게 10이거나 10보다 크니? 라고 물어봐서 10이면 끝. 10이 아닌 경우 10보다 작다고 말할 테니 오른쪽으로 이동.

여기서 오른쪽으로 이동하면 5를 기준으로 왼쪽은 볼 필요가 없어진다. 이게 절반 소거법의 장점이다.

2단계

그 다음 노드인 8에게 10이거나 10보다 큰지를 물어본다. 10이라면 끝. 10이 아닌 경우 10보다 작다고 말할테니 오른쪽으로 이동.

3단계

단 세번의 질문으로 원하는 10을 찾아냈다. 여기서 세번은 트리의 깊이(Depth)를 말한다. 

5번 노드가 있는 1 Depth.

2, 8번 노드가 있는 2 Depth.

10번 노드가 있는 3 Depth.

이렇게 트리의 깊이만큼만 질문해서 원하는 답을 찾아낼 수 있다.

 

Binary Tree vs Binary Search Tree

Binary Search Tree

N개의 노드를 가진 꽉 찬 트리의 경우 트리의 깊이는 log N이다.

그래서 이 Binary Search Tree 구조로 원하는 값을 찾을 때 시간 복잡도는 O(log N)이다.

 

Binary Tree

정렬된 트리가 아니라 원하는 값을 찾기 위해 DFS 또는 BFS를 통해 찾아낸다.

결국 최악의 경우 N개의 노드를 가진 트리에서 N의 값을 찾는 시간 복잡도는 O(N)이다.

따라서 Binary Search Tree가 더 빠른 속도로 원하는 값을 찾아낼 수 있다.

 

Binary Search Tree 코드로 구현해보기

struct Node* find_node(struct Node* root, int findValue) {
	if (root == NULL || root->value == findValue) {
    	return root;
    } else if (root->value > findValue) {
    	return find_node(root->left, findValue);
    } else {
    	return find_node(root->right, findValue);
    }
}

 

위 코드가 Binary Search Tree 구조에서 원하는 값을 찾아내는 코드이다. 역시 Recursion(자기 자신 참조)을 통해 간단하게 구현할 수 있다. 순서대로 한 번 접근해보자. 

 

1. 10을 찾고싶다고 할때, root node인 5가 최초로 들어온다.

2. root(5)는 NULL이 아니고 root(5)가 가진 값이 10이 아니므로 다음 if로 간다.

3. root(5)가 가진 값 5가 찾고자하는 값 10보다 크지 않기 때문에 다음 else로 간다.

4. 자기 자신을 호출한다 이때 파라미터는 root(5)의 오른쪽 노드 8과 찾고자하는 값 10.

5. 역시 root(8)는 NULL이 아니고 root(8)가 가진 값이 10이 아니므로 다음 if로 간다.

6. root(8)이 가진 값 8이 10보다 크지 않으므로 다음 else로 간다.

7. 자기 자신을 호출한다. 여기서 파라미터는 root(8)의 오른쪽 노드 10과 찾고자하는 값 10.

8. root(10)은 NULL이 아니지만, root(10)의 값 10과 찾고자 하는 값 10이 같으므로 이 root를 리턴한다.

9. 7번으로 돌아온다. 호출한 자기자신이 반환한 root(10)을 리턴한다.

10. 4번으로 돌아온다. 호출한 자기자신이 반환한 root(10)을 리턴한다. 끝.

 

이런식으로 절반을 소거해가면서 찾아내는 방법을 Binary Search라고 하고 그 구조가 Tree일 때 Binary Search Tree라고 한다.

 

 

Binary Search가 꼭 Tree여야하나?

그럼 여기서 질문이 생긴다. Binary Search는 꼭 트리일 필요는 없을 것 같다. 왜냐하면 배열에 값을 정렬해 놓아도 Binary Search로 검색할 수 있으니까. 맞다. 똑같이 시간 복잡도는 O(log N)이다.

이러한 정렬된 배열에 중간을 잡고 물어보면 똑같다. 

1단계

정렬된 배열에 중간에 10이거나 10보다 큰지 물어본다. 10이라면 끝. 10이 아니면 10보다 작으니 오른쪽만 보면 된다.

2단계

오른쪽을 기준으로 중간에서 10이거나 10보다 큰지 물어본다. 10이라면 끝. 10이 아니면 10보다 작으니 오른쪽만 보면 된다.

3단계

 

그럼 뭐하러 Binary Search Tree를 사용할까? 

정렬된 배열에 값이 새로 추가되거나 제거되는 경우가 없으면 정렬된 배열이 더 좋을 수 있다.

근데, 새롭게 추가되는 값이 있을 땐 그 값을 추가한 후 다시 정렬을 해야하는 과정이 필요하다.

예를 들어보자, 저 배열에 4를 추가하고 싶다고 해보자.

그럼 정렬을 위해 2와 5사이에 넣어야하고 그럼 5부터 마지막을 뒤로 전부 밀어야한다. 이 작업의 시간 복잡도는 O(N)이다.

근데! Binary Search Tree는 이 작업도 O(log N)이다.

"왜요?" Binary Search Tree에서 N개의 노드를 가진 꽉 찬 트리의 경우 깊이는 log N이라고 했고 그래서 트리에서 원하는 값을 찾을 때 질문의 횟수는 트리의 깊이(Depth)만큼이라고 했다.

그럼 원하는 자리를 찾는데 시간 복잡도는 O(log N).

원하는 자리를 찾았으니 추가하는(지우는) 시간 복잡도는 O(1). 

경우를 모두 하는 시간 복잡도는 O(log N) + O(1) = O(log N)

 

O(N)과 O(log N)을 비교하면 압도적으로 빠른 수치다. 예를 들어, 전 세계 인구가 80억명이면 log(80억명) = 32이다.

80억개의 경우의 수를 Binary Search Tree로 만들면 내가 원하는 값을 찾는데 32번만에 가능하단 얘기다. 

근데 O(N)은...? 최악의 경우.. 80억번..?? 

 

근데! 여기서 하나 더, 꽉 찬 트리가 아니면?

만약, Binary Tree는 Binary Tree인데 꽉 찬 트리가 아니라 이런 모양이면 어떻게 할까?

 

이것도 Binary Tree다. 자식이 최대 2개를 만족하고 오른쪽은 다 자신보다 크니까.

이런 경우 트리의 Depth만큼 찾아내는 시간 복잡도는 O(log N)이 아니라 O(N)이다. 

 

결론부터 말하면 이런 경우는 고려하지 않아도 된다. Self-Balancing Binary Search Tree라는게 있는데 저런 모양이 나올 수 없게 새 노드가 추가되거나 삭제될 때 Binary Search Tree가 항상 Balance가 되도록 보장해준다.

Self-Balancing Binary Search Tree의 종류로 AVL Tree, Red Black Tree 이런게 있고 이런게 있다는 것 정도만 알아두자.

 

728x90
반응형
LIST

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

배열과 Big O 표기법  (0) 2024.05.10
Hash Table  (2) 2024.04.16
Tree와 BFS / DFS  (0) 2024.04.16
Stack  (0) 2024.04.15
Queue  (0) 2024.04.15
728x90
반응형
SMALL

우선 BFS, DFS를 알기 전 Tree를 알아야 하는게 먼저더라.

Tree

트리란, 부모 자식 관계를 나타낼 수 있는 자료 구조다.

다음 그림이 트리라고 말 할 수 있다.

 

- 노드 하나에 한개의 Parent 노드가 있을 수 있다.

- 노드 하나에 여러개의 Child 노드가 있을 수 있다.

 

이런 유형의 자료구조는 실생활에서도 너무 많이 접해볼 수 있다. 

  • 회사 조직도
  • 가족 관계도
  • File System

 

이런 트리 중 특별한 트리가 있는데 'Binary Tree'라는 게 있다.

Binary Tree

한 노드에 Child 노드가 최대 2개까지만 있는 트리를 Binary Tree라고 한다.

위 그림은 그럼 Binary Tree라고 할 수 없다. 왜냐하면, 한 노드(Node 1)가 Child Node를 3개까지도 가지고 있으니까.

 

Binary Tree는 Linked List와 굉장히 유사하게 생겼다. Linked List의 구조는 다음과 같다.

그리고 이 Linked List의 한 노드를 코드로 표현한다면 다음처럼 표현할 수 있겠다.

struct Node {
    int value;
    struct Node *next;
}

 

 

 

그럼 바이너리 트리는 여기에 자식이 하나씩 더 있을 수도 있는것뿐.

다음 그림이 Binary Tree라고 표현할 수 있다.

이 Binary Tree의 한 노드를 코드로 표현한다면 다음처럼 작성할 수 있다.

struct Node {
    int value;
    struct Node *left_child;
    struct Node *right_child;
}

 

그래서, 이 바이너리 트리 구조를 메모리 상에서 어떻게 표현될지를 봐보자.

 

하나에 4 Byte 메모리 구조를 보자. 

 

Node 1은 값으로 1을 가지고 있고, left_child, right_child에 대한 각각의 주소를 가리키는 포인터를 가지고 있다.

 

Node 1의 left_child가 가리키는 주소를 따라가면 Node 2가 가진 값 2가 나온다. 

Node 1의 right_child가 가리키는 주소를 따라가면 Node 3가 가진 값 3이 나온다. 

 

Node 3은 자식이 없기 때문에 가리키는 포인터도 없다.

Node 2는 하나의 자식을 left_child가 가리키고 있고 그 주소를 따라가면 Node 4가 가지고 있는 값 4가 나온다.

Node 4도 자식이 없기 때문에 가리키는 포인터도 없다.

 

 

Tree, Binary Tree 둘 다 뭔지 알겠다. 그럼 이 트리를 어떻게 탐색할까? 이 탐색하는 방법이 앞에서 말한 DFS, BFS가 된다.

DFS (Depth First Search)

트리를 탐색하는 가장 일반적인 방법 중 하나인 깊이 우선 탐색(DFS)가 있다.

다음 트리를 보자.

DFS는 깊이 우선 탐색, 즉 한쪽 방향으로 탐색을 시작했으면 더 내려갈 수 없을때까지 아래로 내려가서 확인하는 것을 말한다.

 

그래서 Node1 부터 탐색을 시작하고 왼쪽 또는 오른쪽으로 하나 방향을 잡은 후 그 방향의 가장 하단까지 쭉 검색하고 다시 반대편으로 돌아오는 방식이라고 생각하면 된다. 

예시

1단계

2단계

3단계

 

3단계가 끝나고 더 내려갈 수 없을 만큼 내려왔으니 다시 Node 1으로 가서 왼쪽을 다 털었으니 오른쪽으로 털기 시작한다.

4단계

5단계

6단계

Node 3을 기준으로 왼쪽 끝까지 갔으니 이제 다시 Node 3의 오른쪽을 털면 된다.

 

7단계

 

그럼, DFS는 코드로 어떻게 구현할 수 있을까?

DFS 코드로 구현하기

DFS(Depth First Search)Recursion(자기 자신 참조)으로 간단하게 구현할 수 있다. 

난 JAVA를 좋아하니까 JAVA로 구현해보겠다.

 

TreeNode

package dfs.binarytree;

public class TreeNode {
    private final int value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

 

BinaryTree

package dfs.binarytree;

public class BinaryTree {
    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println("node Value = " + root.getValue());

        dfs(root.getLeft());
        dfs(root.getRight());
    }
}

 

Main

package dfs.binarytree;

public class Main {
    public static void main(String[] args) {

        TreeNode nodeOne = new TreeNode(10);
        TreeNode nodeTwo = new TreeNode(20);
        TreeNode nodeThree = new TreeNode(30);
        TreeNode nodeFour = new TreeNode(40);
        TreeNode nodeFive = new TreeNode(50);
        TreeNode nodeSix = new TreeNode(60);
        TreeNode nodeSeven = new TreeNode(70);

        nodeOne.setLeft(nodeTwo);
        nodeOne.setRight(nodeThree);

        nodeTwo.setLeft(nodeFour);

        nodeThree.setLeft(nodeFive);
        nodeThree.setRight(nodeSix);

        nodeFive.setLeft(nodeSeven);

        BinaryTree.dfs(nodeOne);
    }
}

실행결과:

node Value = 10
node Value = 20
node Value = 40
node Value = 30
node Value = 50
node Value = 70
node Value = 60

 

코드를 보면 굉장히 간단하지만 이 코드가 DFS를 구현한 코드이다.

아래 그림을 가지고 위 코드를 돌려보는 시뮬레이션을 해보자.

 

1. [root = Node 1], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

2. [root = Node 2], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

3. [root = Node 4], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

4. [root = NULL], root가 NULL이므로 return

5. 3으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

6. [root = NULL], root가 NULL이므로 return

7. 3번으로 돌아옴 모든 라인이 끝났으니 return

8. 2번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

9. [root = NULL] root가 NULL이므로 return

10. 2번으로 돌아옴. 모든 라인이 끝났으니 return

11. 1번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

12. [root = Node 3], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

13. [root = Node 5], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

14. [root = Node 7], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child. 

15. [root = NULL], root가 NULL이므로 return

16. 14번으로 돌아옴 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

17. [root = NULL], root가 NULL이므로 return

18. 14번으로 돌아옴. 모든 라인이 끝났으니 return

19. 13번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

20. [root = NULL], root가 NULL이므로 return

21. 13번으로 돌아옴. 모든 라인이 끝났으니 return

22. 12번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

23. [root = Node 6], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

24. [root = NULL], root가 NULL이므로 return

25. 23번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

26. [root = NULL], root가 NULL이므로 return

27. 23번으로 돌아옴. 모든 라인이 끝났으니 return 

28. 12번으로 돌아옴. 모든 라인이 끝났으니 return

29. 1번으로 돌아옴. 모든 라인이 끝났으니 return

 

이렇게 Recursion을 통해 DFS를 구현할 수 있다. 이제 BFS를 알아보자.

BFS (Breadth First Search)

BFS(Breadth First Search)는 넓이 우선 탐색으로 이것 역시 트리를 검색하는 방법 중 대표적인 하나이다.

이건 DFS랑 어떻게 다른지 그림을 통해 알아보자.

 

0단계

가장 최상위 노드인 Node 1을 검색한 후 다음 한 칸 밑에 있는 모든 노드를 쭉 털고, 그 다음 한 칸 밑에 있는 모든 노드를 쭉 털고, 이렇게 한 라인을 쭉 터는식으로 검색하는 방식이다.

1단계

2단계

3단계

4단계

5단계

6단계

 

이렇게 트리의 한 라인 한 라인을 쭉 터는 방식으로 검색하는게 BFS라고 생각하면 된다.

이 BFS는 코드로 어떻게 구현할까?

 

BFS 코드로 구현하기 

BFS(Breadth First Search)Queue로 간단하게 구현할 수 있다.

Queue는 저번 포스팅에서 배웠지만 FIFO구조. 그리고 Queue는 처음과 끝을 알아야하는 자료구조이다. 

 

코드로 어떻게 구현하는지 살펴보자.

void bfs(struct Node* root) {
	if (root == NULL) {
    	return;
    }
    
    struct TreeNode* queue[10000];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front != rear) {
    	struct TreeNode* curr = queue[front++];
        printf("%d ", curr->val); // 실제 작업을 여기서 하면됨, 지금은 예제니까 출력을 함
        if (curr->left != NULL) {
        	queue[rear++] = curr->left;
        }
        if (curr->right != NULL) {
        	queue[rear++] = curr->right;
        }
    }
}

예제에서 Queue 사이즈는 어느정도 크게 설정했다. 어떤 문제를 푸냐에 따라 달라지겠지만 지금으로선 10000으로 충분하기 때문에.

이것도 그림과 같이 한단계씩 알아보자.

 

[root = Node 1]. root는 NULL이 아니다.

- queue를 만든다.

- Queue를 만들고 rear에 root(Node1)를 넣고 rear를 하나 추가한다. 

- front와 rear는 같지 않기 때문에 while 루프를 돌기 시작한다.

- 여기서 queue의 front값인 Node1을 curr에 넣고, front를 하나 추가한다.

- curr의 값 1을 찍는다. 

- Node1의 left child(Node2)가 NULL이 아니니까 rear 자리에 left child를 넣고 rear를 하나 추가한다.

- Node1의 right child(Node3)가 NULL이 아니니까 rear자리에 right child를 넣고 rear를 하나 추가한다.

- 루프가 끝나고 역시 front와 rear는 다르니까 계속 돈다.

- curr에 front가 가리키는 Node2를 넣고 front를 하나 추가한다.

- curr의 값 2를 찍는다.

- Node2의 left child(Node4)가 NULL이 아니니까 rear 자리에 left child를 넣고 rear를 하나 추가한다.

- Node2의 right child는 NULL이니까 아무것도 하지 않고 루프가 끝난다.

- front와 rear가 다르니까 루프는 계속된다.

- 현재 front의 node(Node3)를 curr에 넣고 front를 하나 추가한다.

- curr의 값 3을 찍는다.

- Node3의 left child(Node5)가 NULL이 아니니까 rear에 left child를 넣고 rear를 추가한다.

- Node3의 right child(Node6)가 NULL이 아니니까 rear에 right child를 넣고 rear를 추가한다.

- 루프가 끝나고 다시 front와 rear는 다르기 때문에 또 돈다.

- 현재 front가 가리키는 Node4를 curr에 집어넣고 front를 하나 추가한다.

- curr의 값 4를 찍는다.

- curr의 left child와 right child모두 NULL이니까 아무것도 하지 않고 다음 루프로 간다.

- front와 rear는 다르니까 루프가 계속된다.

- 현재 front에 담긴 Node5를 curr에 담고 front를 하나 추가한다.

- curr의 값 5를 찍는다.

- curr의 left child(Node7)는 NULL이 아니니까 rear에 넣고 rear를 하나 추가한다.

- curr의 right child는 NULL이니까 다음 루프로 간다.

- 여전히 front와 rear는 다르니까 루프는 계속된다.

- 현재 프론트에 담긴 Node6을 curr에 담고 front를 하나 증가시킨다.

- curr의 값 6을 찍는다.

- curr의 left, right child가 모두 NULL이므로 아무것도 하지않고 다음 루프로 간다.

- 여전히 front와 rear는 다르기 때문에 루프는 계속된다.

- 현재 front가 가리키는 Node7을 curr에 넣고 front를 하나 추가한다.

- curr의 값 7을 찍는다.

- curr의 left, right child 모두 NULL이니까 루프가 끝난다.

- 루프의 조건 front != rear를 만족하지 않으므로 루프는 끝난다. 

 

정리

DFS, BFS 모두 트리를 탐색할 때 방법 중 하나이다. DFS(Depth First Search)는 깊이 우선 탐색, BFS(Breadth First Search)는 넓이 우선 탐색의 줄임말로 둘 다 어떻게 탐색하는지 꼭 알아두면 좋을것같다.

 

728x90
반응형
LIST

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

Hash Table  (2) 2024.04.16
Binary Search Tree  (0) 2024.04.16
Stack  (0) 2024.04.15
Queue  (0) 2024.04.15
Array vs Linked List  (0) 2024.04.15
728x90
반응형
SMALL

Stack은 위에만 구멍이 뚫린 박스라고 생각하면 된다.

이 그림이 Stack 구조이다.

먼저 들어간 데이터가 가장 마지막에 나온다.

가장 마지막에 들어간 데이터가 가장 먼저 나온다. LIFO.

 

Stack은 중간에 데이터를 넣는것도 불가능하고 맨위에 데이터를 새로 넣거나 맨위에 있는 데이터를 빼거나해야 한다.

 

코드적으로 접근해보기

Stack은 보통 이러한 메서드들을 가지고 있다.

  • pop(): 가장 최근에 추가된 데이터 빼기
  • push(item): 데이터 새로 추가하기
  • peek(): 가장 최근에 추가된 데이터 읽기
  • isEmpty(): Stack이 비어있는지 확인하기

다음 그림과 같이 사이즈가 7인 Stack이 있다고 해보자.

 

1. 이 상태에서 push(8)을 하면 다음 그림이 된다.

2. 이 상태에서 또 push(10)을 하면 다음 그림이 된다.

3. 이 상태에서 peek() 메서드를 호출하면 10을 반환한다. 가장 마지막에 넣은 녀석을 가져오는 메서드니까.

4. 이 상태에서 isEmpty() 메서드를 호출하면 false를 반환한다.

5. 이 상태에서 pop()을 호출하면 10이 나온다.

6. 이 상태에서 pop()을 한번 더 호출하면 8이 나온다.

7. 여기서 isEmpty()를 호출하면 true가 나온다.

 

그래서 Stack의 특징은 맨 위(가장 마지막)만 알면 모든 처리가 가능하다.

 

Stack의 예시 코드

#define MAX_SIZE 100

typedef struct {
	int stack[MAX_SIZE];
    int pop;
} Stack;

void initialize(Stack* s) {
	s->top = -1; // 최초에는 아무 데이터도 들어가지 않으니까 -1
}

int pop(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack Underflow: Cannot pop element from the stack.\n");
        return -1;
    }
    
    int item = s->stack[s->top--];
    return item;
}

void push(Stack* s, int item) {
	if (s->top == MAX_SIZE -1) {
    	printf("Stack Overflow: Cannot push element onto the stack.\n");
        return;
    }
    
    s->stack[++s->top] = item;
    printf("%d pushed onto the stack.\n", item);
}

int peek(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack is empty.\n");
        return -1;
    }
    
    return s->stack[s->top];
}

bool isEmpty(Stack* s) {
	return (s->top == -1);
}

 

Stack test

int main() {
    Stack stack;
    initialize(&stack);
    ...
}

여기까지 하면 이런 그림이 된다.

 

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    ...
}

여기까지 하면 이런 그림이 된다.

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    ...
}

여기까지 하면 이런 그림이 된다.

이 상태에서 peek()메서드를 호출하면? 30을 반환한다.

 

다음과 같이 pop()메서드를 호출하면 어떻게 될까?

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    pop(&stack);
    ...
}

이런 그림이 된다.

 

정리

이런 자료구조를 Stack이라고 한다. 그럼 자주 들어봤던 Stack Overflow는 어떤 순간에 발생하는걸까?

일단 Overflow니까 꽉 차서 더 못넣는다는 얘기인데, 자바 메모리 구조를 생각해보면 항상 실행하는 메서드를 순차적으로 Stack에 집어넣게 되어 있다.

 

최초의 main() 메서드가 실행되고 main()에서 A()라는 메서드를 호출하고 A()메서드가 B()라는 메서드를 호출하면 처리하는 순서는 B -> A -> main이 된다. 이게 정확하게 Stack의 구조다.

 

그래서 이 Stack에 계속해서 쌓이는 무언가가 Stack Overflow를 일으키는데 대표적인 예시가 자기 자신을 무한하게 호출하는 경우가 그렇다. 자기가 자기 자신을 계속 호출 호출 호출 무한루프에 빠지는거지. 그럴때 이제 더 이상 Stack에 넣을 자리가 없어서 Stack Overflow가 발생한다.

 

728x90
반응형
LIST

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

Hash Table  (2) 2024.04.16
Binary Search Tree  (0) 2024.04.16
Tree와 BFS / DFS  (0) 2024.04.16
Queue  (0) 2024.04.15
Array vs Linked List  (0) 2024.04.15

+ Recent posts