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

탐욕법 문제로, 여분의 체육복을 가져온 학생이 체육복을 잃어버린 학생에게 빌려줘서 최대한 많은 학생이 체육수업에 참여할 수 있도록 하는 문제입니다.

문제 정의

lost 배열: 체육복이 없는 학생 리스트 reserve 배열 : 여벌의 체육복이 있는 학생 리스트 n : 전체 학생 수 결과 : 체육 수업을 들을 수 있는 학생 수

*제약조건: *

1. 체육복은 자신의 앞 또는 뒤 학생에게만 빌려줄 수 있다.
2. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있지만, 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없다.

-> 즉, lost와 reserve배열에 동일한 학생이 존재할 수 있지만, 이 학생은 다른 체육복을 빌릴 수도, 자신의 여분을 빌려줄 수도 없다는 의미입니다.

첫 번째 시도

알고리즘

lost를 순서대로 순회하면서 현재 학생의 앞 뒤 학생이 reserve에 있는지 확인하자!

위의 알고리즘을 C++로 작성했습니다

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    int i=0, j=0; //lost 스캔 인덱스

    for(i=0; i<lost.size() i++){
        if(lost[i]-1 == reserve[j]){
            j++;
        }
        else if(lost[i]-1>reserve[j]){
            j++;
            i--;
        }
        else{
            if(lost[i]+1 == reserve[j]){
                j++;
            }
            else if(lost[i]+1<reserve[j]){
                answer--;
            }
        }
    }

    return answer;
}

결과

위의 풀이는 제출했을 때 50%의 정확도만 받을 수 있었습니다. 분명 if문에서 잘못된게 없다고 생각했는데 낮은 점수를 받아서 gpt에게 피드백을 요청했습니다.

gpt 피드백

이 피드백을 통해 제약조건을 확인하지 않았다는 것을 발견했습니다.

1. lost와 reserve가 정렬되어있지 않으면 reserve와 lost를 크기비교하는 것이 의미가 없습니다.
2. 여벌 옷이 있는 학생이 도난을 당한 케이스를 제외하지 못했습니다..(이거는 문제를 잘 안읽어서 생긴 문제)

두번째 시도

피드백을 읽고 다시 알고리즘을 작성했습니다.

알고리즘

1. 두 배열의 교집합을 제거하기
2. 교집합이 제거된 배열을 각각 정렬하기
3. reserve를 순회하면서 앞이나 뒤 학생이 lost에 있다면 해당 학생을 lost에서 제거하기

-> reserve를 순회해야 앞과 뒤 두 학생에게 중복으로 빌려주는 일이 없음

이번에는 파이썬으로 코드를 작성했습니다.

def solution(n, lost, reserve):
    answer = 0

    lost = set(lost)
    reserve = set(reserve)

    both = lost&reserve
    lost -= both
    reserve -= both

    lost = sorted(lost)
    reserve = sorted(reserve)

    for r in reserve:
        if r-1 in lost:
            lost.remove(r-1)
        elif r+1 in lost:
            lost.remove(r+1)

    answer = n - len(lost)
    return answer

결과

성공! 저는 set을 이용해 집합으로 만들어서 교집합을 구했지만 다른 사람들의 코드를 살펴보니 for문을 이용하는 경우가 많았습니다.

아래는 공부하면서 생각나는 것들과 궁금했던 점들에 대한 답변을 메모처럼 정리한 내용이다.

솔리디티란?

솔리디티란 스마트 계약 코드(contract)를 작성하기 위한 언어이다. 이렇게 작성된 스마트 계약 코드는 이더리움에 의해 컴파일되어 이더리움 블록체인에 배포, 실행된다.

솔리디티 개발은 뭘로 하는데?

솔리디티 개발은 Remix IDE를 이용해 웹 상에서 개발하거나 truffle을 이용해 로컬 환경에서 개발할 수 있다.

스마트 계약 코드(=contract)가 배포되는 이더리움은 뭐지?

이더리움이란 블록체인이 존재하는 네트워크이다.

이더리움 네트워크에는 종류가 있다.

1. 이더리움 메인넷: 이더리움의 주요 네트워크로 실제 거래와 스마트 계약이 실행된다.
2. 테스트넷: 개발자가 스마트 계약을 테스트할 수 있도록 설계된 네트워크

ERC-20은 뭐고 스마트 계약 코드는 어떻게 생겼지?

ERC-20은 이더리움 블록체인에서 토큰을 만들고 관리하기 위한 표준이다. 토큰이 어떻게 이동하고, 어떻게 토큰을 전송하는지 등을 정의한다. ERC-20표준을 따르는 토큰은 서로 호환된다.

ERC-20표준에 따른 contract 코드의 예시는 다음과 같다.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface IERC20 {
    function totalSupply() external view returns (uint256);
    function balanceOf(address account) external view returns (uint256);
    function transfer(address recipient, uint256 amount) external returns (bool);
    function allowance(address owner, address spender) external view returns (uint256);
    function approve(address spender, uint256 amount) external returns (bool);
    function transferFrom(address sender, address recipient, uint256 amount) external returns (bool);

    event Transfer(address indexed from, address indexed to, uint256 value);
    event Approval(address indexed owner, address indexed spender, uint256 value);
}

contract MyToken is IERC20 {
    string public constant name = "MyToken";
    string public constant symbol = "MTK";
    uint8 public constant decimals = 18;

    uint256 private _totalSupply;
    mapping(address => uint256) private _balances;
    mapping(address => mapping(address => uint256)) private _allowances;

    constructor(uint256 initialSupply) {
        _totalSupply = initialSupply;
        _balances[msg.sender] = _totalSupply;
        emit Transfer(address(0), msg.sender, _totalSupply);
    }

    function totalSupply() public view override returns (uint256) {
        return _totalSupply;
    }

    function balanceOf(address account) public view override returns (uint256) {
        return _balances[account];
    }

    function transfer(address recipient, uint256 amount) public override returns (bool) {
        require(_balances[msg.sender] >= amount, "ERC20: transfer amount exceeds balance");
        _balances[msg.sender] -= amount;
        _balances[recipient] += amount;
        emit Transfer(msg.sender, recipient, amount);
        return true;
    }

    function approve(address spender, uint256 amount) public override returns (bool) {
        _allowances[msg.sender][spender] = amount;
        emit Approval(msg.sender, spender, amount);
        return true;
    }

    function allowance(address owner, address spender) public view override returns (uint256) {
        return _allowances[owner][spender];
    }

    function transferFrom(address sender, address recipient, uint256 amount) public override returns (bool) {
        require(_allowances[sender][msg.sender] >= amount, "ERC20: transfer amount exceeds allowance");
        _balances[sender] -= amount;
        _balances[recipient] += amount;
        _allowances[sender][msg.sender] -= amount;
        emit Transfer(sender, recipient, amount);
        return true;
    }
}

contract가 배포되면 무슨 일이 일어나지?

1. 컴파일: 이더리움은 contract를 바이트 코드로 컴파일한다.

2. 배포 트랜잭션 생성: 블록체인에 바이트 코드를 배포하기 위해 트랜잭션을 생성한다. 바이트 코드와 가스 비용(GAS)을 지정해야한다.

3. 트랜잭션 처리: 배포 트랜잭션이 이더리움 네트워크로 전송되어 네트워크의 노드들에 의해 검증되고 트랜잭션을 블록에 포함시켜 블록체인에 추가한다.

4. 계약 주소(contract address)할당: 배포(블록체인에 추가)에 성공하면, contract는 고유한 계약 주소를 할당받는다. 이 주소를 이용해 계약과 상호작용한다.

5. 상호작용: 계약주소를 이용해 contract에 작성된 함수를 호출하고 데이터를 조회할 수 있다.

계약과의 상호작용이 뭔데?

contract 코드에 작성했던 함수를 호출하는 것이 상호작용이다. 크게 두 가지 종류가 있다.

1. Transaction 블록체인의 상태를 변경하는 것. 토큰을 전송, 데이터를 기록, 계약 상태 변경 등. 블록체인에 기록되고 가스 비용이 발생한다.

2. call 블록체인의 상태를 변경하지 않고 데이터만 조회하는 것. 계약의 변수 값 확인 등. 블록체인에 기록되지 않고 가스 비용이 발생하지 않는다.

그래서 이걸 이용해서 뭘 할 수 있는 거지?

스마트 계약의 특징을 이용해서 다양한 서비스를 개발할 수 있다.

1. 스마트 계약은 자동 계약을 가능하게 해서 사람의 개입 없이 특정 조건이 충족되면 자동으로 작업을 실행한다.

이를 이용해 특정 가격에 자동적으로 주식을 사고팔 수 있는 자동 주식 거래 프로그램을 만들 수도 있다.

2. 작품을 토큰화하여 블록체인에 기록할 수 있다. = NFT

화면의 아래쪽을 보면 PublicIPs라고 써진 부분에 IP주소를 확인할 수 있다. 이 주소를 쳐서 접속해보기로 했다.

접속이 되지 않는다.

그 이유는 http://54.180.150.169에 접속하면 포트80번으로 자동으로 연결되는데, 우리가 열어둔 포트는 8000번이기 때문이다.

이 문제를 해결하는 것이 Nginx이다.

Nginx란?

nginx는 서버와 클라이언트 사이에 존재하는 프록시 서버로, 클라이언트의 요청을 서버로 대신 전달해주는 역할을 한다.

출처: https://velog.io/@chickenfondue/nginx-docker-compose%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EB%A6%AC%EB%B2%84%EC%8A%A4-%ED%94%84%EB%A1%9D%EC%8B%9C-%EA%B5%AC%EC%84%B1

위의 그림처럼 80번 포트로 들어온 요청을 실제로 열려있는 포트로 전달해주는 것이 nginx이다.

장점

1. 로드 밸런싱: 트래픽을 분산시킬 수 있다.
2. 보안 강화: 웹 서버가 클라이언트에게 바로 노출되어있지 않아 위험한 요청을 차단할 수 있다.(DDOS등)

Nginx 설치 및 설정

sudo apt install nginx

위의 명령어를 통해 간단히 설치할 수 있다.

설치가 되었다면 이제 8000번 포트로 링크할 수 있도록 설정해주어야 한다.

sudo vi /etc/nginx/sites-enabled/default

명령어를 입력하면 vi 편집기가 열린다.

당황하지 말고 아래로 스크롤 해서 내려가면 location이라는 부분이 보인다.

location / 뒤에 붙은 중괄호 안의 내용을 변경해주면 된다.

변경할 때는 i를 눌러 INSERT모드로 바꾸고

proxy_pass http://127.0.0.1:8000; proxy_set_header Host $http_host; proxy_set_header X-Real_IP $remote_addr; proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; proxy_set_header X-Forwarded-Photo $scheme;

이 내용을 중괄호 안에 넣어주면 된다.

저장하고 나가기 위해서 esc를 누르고 :wq!를 치고 엔터를 치면 된다.

변경사항을 반영하기 위해 nginx를 재실행 해준다.

실행하기 sudo service nginx start 재실행하기 sudo service nginx restart 종료하기 sudo service nginx stop

그리고 -t옵션으로 설정 파일의 문법이 정확한지 검사할 수 있다.

sudo nginx -t

문제가 없다고 떴으니 이제 다시 서버를 열고 테스트할 수 있다.

테스트

uvicorn main:app 명령어로 서버를 열어주고

아까와 같은 IP주소를 통해 접속할 수 있다.

문제없이 잘 뜨는 것을 확인할 수 있다.

끝.

Python, FastAPI, uvicorn 설치

파이썬, pip 설치

python3 설치

sudo apt install python3

sudo apt install python3-pip

[오류] python3-pip가 설치되지 않을 때

이렇게 package 'python3-pip' has no installation candidate 오류가 발생하면

sudo apt update

위의 명령어로 업데이트 해준 후에 동일한 명령어로 설치하면 됩니다.

이어서 pip 설치

중간에 y를 눌러서 계속해주면 됩니다. 잘 설치됩니다.

FastAPI, Uvicorn 설치

fastAPI 설치

pip install fastapi pip install uvicorn

[오류] 가상환경이 필요할 때

error: externally-managed-environment 이런 오류가 발생하면 가상환경을 실행하고 그 안에 fastAPI와 uvicorn을 다운받아줘야 합니다.

sudo apt install python3-venv

설치해주고

python3 -m venv (가상공간 이름)

가상공간을 만들어준다

source (가상공간 경로/bin/activate)

이렇게 가상공간을 활성화 할 수 있다.

pwd를 이용해 현재 경로를 확인하고 그 위에 /bin/activate를 붙여주면 된다.

이어서 fastAPI, uvicorn 설치

위에서 말했던 명령어로 다시 설치하면 된다.

왼쪽 상단에 가상환경 이름이 떠있는 것을 확인할 수 있다.

테스트

두 개가 제대로 설치되었는지 확인하기 위해서 깃에 올려둔 간단한 fastAPI예제를 가져와서 실행해보기로 했다.

https://github.com/Heejae-L/SimpleFastApi.git

git clone https://github.com/Heejae-L/SimpleFastApi.git

이 명령어로 리포지토리를 클론해서 가져온다.

SimpleFastAPI폴더로 이동하여 uvicorn을 테스트해본다.

이렇게 로컬호스트8000(127.0.0.1:8000)에서 서버가 열린 것을 확인할 수 있다.

외부에서 http를 이용해 접근하는 것은 다음 포스트에서 이어서 설명하겠다.

끝.

Fast API를 EC2에 올리기 위해서는 일단 EC2인스턴스를 생성해야한다.

위의 화면에서 인스턴스 시작을 누른다

그러면 아래와 같은 화면이 뜨는데 자신이 사용할 OS를 선택해주면 된다.

나는 Ubuntu를 선택했다. 프리티어에서 사용가능하다고 표시된 것을 선택하면 돈을 내지 않고도 일정한 시간동안 사용할 수 있다.

아래로 내려가서.. 인스턴스 유형은 기본을 그대로 선택하면 된다. 키페어는 없다면 생성해주고 선택하면 된다.

다음으로 네트워크 설정인데 이거는 HTTP/HTTPS를 쓸지 말지에 따라서 선택해주면 된다. 나는 둘 다 체크해줬다.

그 다음으로 스토리지 구성은 프리티어에서 최대 30GB이므로 30으로 설정해주면 된다.

그리고 오른쪽에 인스턴스 시작을 눌러주면 된다.

성공적으로 잘 만들어졌고 이제 오른쪽 아래의 모든 인스턴스 보기를 누르면 만들어진 인스턴스를 확인할 수 있다.

인스턴스 실행

아래 있는 것이 방금 만든 인스턴스인데, 실행 중으로 나와있다. 인스턴스 ID를 누르면 자세한 정보를 볼 수 있다.

현재 이 인스턴스의 IP, 로컬 IP 등이 나와있다.

퍼블릭 IPv4 주소는 인스턴스를 실행/중지 할 때마다 바뀌기 때문에 주의해야한다.

이제 우리가 만든 ubuntu 컴퓨터를 직접 사용해 볼 수 있다. 아주 간단하게 오른쪽 위 연결을 누르면 된다.

그러면 이렇게 콘솔 화면이 나오게 된다.

이 화면을 통해 파일을 관리하고 코드를 작성하거나 서버를 띄우는 일을 할 수 있다.

이 다음 포스트에서는 FastAPI서버를 띄우는 법을 공부할 것이다.

끝.

2024년 7월

공개 SW 개발자 대회(6/29~)

6월 18일에 학부의 날 행사에 다녀온 후 동기부여가 되어 함께 갔던 동기와 공개 sw 개발자 대회를 준비하게 되었다.

매 주 2번 이상 온라인으로 회의하며 진행하고 있다.

6월 말에 아이템 선정 완료, 7월 초 부터 개발을 시작하여 FastAPI, HTML, YOLOv8을 이용해 object tracking과제를 수행하는 중이다.

모델의 성능이 잘 나오지 않고 트랙킹을 최적화하기 위해 Deep sort 모델의 사용을 고민하는 중이다.

하계 딥러닝 단기 프로그램(7/87/11 , 7/157/18)

딥러닝 기업 실무진을 초청하여 교육을 진행한다길래 빠르게 신청하였다.

기초과정과 고급과정으로 나눠져있었는데, 기초 과정은 대부분 전공 수업인 AI수학, 데이터과학, 인공지능 개론에서 다뤘던 내용들이 주를 이뤘다.

고급 과정에서는 기초 수업의 내용을 바탕으로 실제 현장에서 물체에 띄지를 부착하거나, 불량품을 검출해내는 AI를 어떻게 학습시키는지 실습하였다.

바이오헬스의료기기융합전공에서 주최한 프로그램이기에 의료 데이터를 이용한 딥러닝 모델 학습을 주로 배우게 되었다.

의료 데이터 분야 실무를 배웠기 때문에 computer vision 분야에서 실제로 사용되고 있는 모델과 새로 등장하는 모델을 알아가는 기회였다.

학교에서 배우는 모델은 아주 기초적이고 오래된 모델이라는 것도 배웠다..

백엔드 취준(7/16~ )

가장 막막하고 큰 고민을 안겨준..

취준!!

백엔드 개발자로 노선을 정하고 나서 잠깐은 길이 보이는 기분에 이것저것 계획을 세웠었다.

하지만.. 공부를 시작하고 보니 알아야 할 기술이 너무나 많고 명확한 길도 없는 것처럼 느껴졌다.

물론 어떤 분야도 확실한 노선은 없는게 당연하지만, 나는 인공지능 전공이기에 학과 수업이 아닌 분야를 스스로 터득해야한다는 부담감이 존재했다.

7월에는 취준을 위해 두 가지를 진행했다.

1. 코딩테스트 준비

• 이것이 취업을 위한 코딩테스트다 with 파이썬 책으로 알고리즘 개념을 잡고있다.
• chapter 8 까지 완료
• 백준에서 문제를 찾아서 풀고 있다.

2. 스프링 부트 강의 수강(7/

이 수업을 듣기 시작한것은 저번 학기 중반이었는데, 중간에 시간이 없다는 핑계로 미뤘다가 이번에 다시 듣고 있다.

HTTP 공부(7/29~7/31)

스프링 강의를 들으면서 기본적인 웹 지식이 부족함을 느끼고 http강의를 수강하였다.

TCP, UDP, IP나 PORT관련 내용은 학교 네트워크 수업을 바탕으로 이해할 수 있었다. 학교에서 다루지 않았던 HTTP 메서드들간의 차이와 상태코드를 정리할 기회도 됐다. 웹 개발자가 되려면 꼭 필요한 부분이라고 생각한다.

velog 작성 & 토이프로젝트(6/22~ )

벨로그를 한 주에 한 번은 작성하려고 노력했다. 6월 22일에 시작해서 5주 동안 10개를 썼으니까 일주일에 2개 정도 작성했다.

벨로그를 작성하면서 매번 ppt나 미리캔버스로 썸네일을 만드는게 귀찮아서 간단한 토이프로젝트를 진행했다.

썸네일을 만들 수 있는 웹 서비스다. 이번 주 내로 프론트는 마무리해서 벨로그에 작성할 예정이다. 생성형ai의 api를 가져와서 추가하는 것도 생각중이다.

https://github.com/Heejae-L/thumbnail-maker

기타

• 깃허브 리드미 정리
• 건강 챙기기(탄수화물 줄이기 + 꾸준한 산책)
• 여름 휴가

결론...

회고를 쓰게 된 계기는 이렇다. 방학이 끝나가는데 대체 어떤 일로 시간을 보냈는지 기억이 나지 않았다. 이상하게도 자꾸 취업시장과 IT시장이 얼어간다는 소식만 듣게 되면서 취업에 대해 막연한 걱정을 매일하는 지경이었다.

작성하면서 보니 꽤 알차다면 알차게 보낸 듯 하다. 너무 걱정하거나 비교하지 말고 스스로 반성하며 삶을 이끌어가는 것이 중요함을 느낀다.

끝.

상속

: (is-a관계) 한 클래스가 다른 클래스의 변수와 메소드를 받아오는 것. 자식 클래스가 부모클래스를 상속받는다. 필요한 변수나 메서드를 추가할 수 있다.

특징

• 일반적인 특성을 부모 클래스에서 구현하고 구체적인 부분은 자식 클래스에서 구현할 수 있다
• 클래스에 새로운 기능을 일관되게 넣어 일관성을 유지한다.
• 유지 보수 용이

사용

class [자식 클래스] extends [부모 클래스] {}

예제

// 부모 클래스
class Vehicle {
    protected String brand; // 차량 브랜드
    protected int year;     // 제조 연도

    public Vehicle(String brand, int year) {
        this.brand = brand;
        this.year = year;
    }

    public void start() {
        System.out.println("Vehicle is starting");
    }

    public void stop() {
        System.out.println("Vehicle is stopping");
    }
}

// 자식 클래스 1: Car
class Car extends Vehicle {
    private int doors; // 차량의 문 개수

    public Car(String brand, int year, int doors) {
        super(brand, year); // 부모 클래스의 생성자 호출
        this.doors = doors;
    }

    // 추가 메소드 정의
    public void openTrunk() {
        System.out.println("Opening the trunk");
    }
}

// 자식 클래스 2: Truck
class Truck extends Vehicle {
    private double loadCapacity; // 적재 용량

    public Truck(String brand, int year, double loadCapacity) {
        super(brand, year); // 부모 클래스의 생성자 호출
        this.loadCapacity = loadCapacity;
    }

    // 추가 메소드 정의
    public void unload() {
        System.out.println("Unloading cargo");
    }
}

// 메인 클래스로 실행을 위한 코드
public class Main {
    public static void main(String[] args) {
        Car myCar = new Car("Toyota", 2021, 4);
        Truck myTruck = new Truck("Ford", 2019, 5.0);

        myCar.start();
        myCar.openTrunk();
        myCar.stop();

        myTruck.start();
        myTruck.unload();
        myTruck.stop();
    }
}

다중 상속 불가능

: 한 클래스는 단 하나의 부모클래스를 가져야한다.

하지만 여러 클래스의 메서드가 필요한 경우가 있다. 이때, 인터페이스를 이용하여 하나의 클래스가 여러 인터페이스를 구현함으로써 이 부분을 어느 정도 극복할 수 있다.

예제

//인터페이스1 정의
public interface Sell {

    void sell();

}
//인터페이스2 정의
public interface Buy {

    void buy();

}
//인터페이스1,2를 모두 구현하는 클래스 정의
public class Customer implements Buy, Sell{

    @Override
    public void sell() {
        System.out.println("customer sell");
    }

    @Override
    public void buy() {
        System.out.println("customer buy");        
    }

    public void sayHello() {
        System.out.println("Hello");
    }
}

public class Main {
    public static void main(String[] args) {
        Customer customer1 = new Customer();
        customer1.sell();  // 출력: customer sell
       customer1.buy(); //출력: customer buy
    }
}

인터페이스

: 메소드의 이름, 파라미터 리스트, 반환 유형을 명시하지만 코드적인 구현은 포함하지 않은 껍데기 클래스.

특징

• 구현과 인터페이스를 분리해서 독립적인 개발이 가능하도록 한다.
• 다중 상속과 비슷한 기능을 지원한다. ➜ 상속 부분 참고

정의

interface [인터페이스] {}

사용

class [클래스] implements [인터페이스 이름] {}

class [클래스] implements [인터페이스1],[인터페이스2] {}

위와 같이 두 개의 인터페이스를 구현할 수 있다.

예제

// Animal 인터페이스 정의
interface Animal {
    void speak();  // 모든 동물은 말할 수 있어야 함을 정의
}

// Dog 클래스가 Animal 인터페이스를 구현
class Dog implements Animal {
    // 인터페이스의 speak 메서드 구현
    @Override
    public void speak() {
        System.out.println("멍멍!");
    }
}

public class Main {
    public static void main(String[] args) {
        Dog myDog = new Dog();
        myDog.speak();  // 출력: 멍멍!
    }
}

추상 클래스(abstract class)

: 인터페이스와 유사한 역할.

특징

인터페이스와의 차이점은 일부 메소드의 구현을 포함한다는 것이다. 또한 클래스 내에 변수(멤버 변수)를 가질 수 있다.

➜ 결과적으로 공통 부분을 추상 클래스에서 구현하여 코드의 중복을 줄인다.

정의

abstract class [추상 클래스 이름] {}

사용

class [클래스 이름] extends [추상 클래스 이름] {}

예제

// Vehicle 추상 클래스 정의
abstract class Vehicle {
    abstract void startEngine();  // 엔진을 시작하는 추상 메서드

    // 공통 기능을 제공하는 비추상 메서드
    void stopEngine() {
        System.out.println("엔진 정지!");
    }
}

// Car 클래스가 Vehicle 클래스를 상속받음
class Car extends Vehicle {
    // 추상 메서드 구현
    void startEngine() {
        System.out.println("엔진 시동!");
    }
}

public class Main {
    public static void main(String[] args) {
        Car myCar = new Car();
        myCar.startEngine();  // 출력: 엔진 시동!
        myCar.stopEngine();   // 출력: 엔진 정지!
    }
}

DFS란?

DFS는 깊이 우선 탐색 알고리즘입니다. 즉 한 노드를 탐색하면 그 노드와 연결된 노드 중 방문하지 않은 곳이 없을 때까지 타고타고 들어가며 탐색하는 알고리즘입니다.

스택으로 구현될 수 있는 알고리즘이기도 합니다.

위의 그림을 스택을 이용해 설명하면 이렇습니다.

1. 1을 방문처리한 후 스택에 넣습니다

2. 1과 연결된 2를 방문처리하고 스택에 넣습니다.

3. 2와 연결된 3을 방문처리하고 스택에 넣습니다.

4. 3과 연결된 노드가 없으므로 3을 스택에서 꺼냅니다.

5. 2와 연결된 노드 또한 없으므로 2를 스택에서 꺼냅니다.

6. 1과 연결된 노드 4를 스택에 넣습니다.

7. 반복

이렇게 스택의 구조를 이용해서 구현할 수 있습니다.

다시 말해 DFS는 한 길로 쭉 파고 들어가는 알고리즘이라고 할 수 있습니다.

DFS의 구현

재귀함수를 이용한 구현

코드

def dfs(graph, v, visited):
    visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
graph = [
    [],
    [2, 3],
    [1, 4],
    [1, 3, 4],
    [2, 4]
]

visited = [False] * 5

dfs(graph, 1, visited)

코드 설명

graph배열은 각 노드에 연결된 노드를 나타냅니다. 예를 들어 graph[1]은 노드 1에 연결된 모든 노드를 리스트 형태로 확인할 수 있습니다.

visited 배열은 각 노드가 방문되었는지 저장합니다.

dfs함수는 graph, v(현재노드), visited를 인자로 받습니다.

visited[v] = True
print(v,end=' ')

먼저 v에 방문처리를 해줍니다. 방문했으므로 출력도 해줍니다.

for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

자신과 연결된 모든 노드를 확인하기 위해서 graph[v]로 반복문을 실행합니다. 각 노드들이 방문되었는지 확인하고, 방문하지 않은 노드인 경우에만 dfs를 호출합니다.

장점

재귀함수를 이용하였기 때문에 스택을 사용할 필요가 없습니다. 또한 이해가 아주 쉽습니다.

단점

제가 부딪힌 한계이기도 한데, 파이썬에는 최대 재귀한도 깊이 에러(RecursionError: maximum recursion depth exceeded in comparison)가 존재합니다. 이는 재귀함수가 또 다른 재귀함수를 부르는 과정이 1000번 이상 반복되면 발생하는 오류입니다.

파이썬의 최대 재귀 한도는 1000입니다. 만약 1001개의 노드가 한 줄로 연결 되어있다면 오류가 발생하게 됩니다.

이 문제를 해결하는 방법은

1. 한도를 늘려주기 2. 반복문을 사용하기

입니다.

저는 반복문과 스택을 이용해 dfs함수를 다시 만들어보겠습니다.

반복문 이용한 구현

코드

def dfs(graph, v, visited):
    stack = [v]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=' ')
            for node in graph[v]:
                if not visited[node]:
                    stack.append(node)

graph = [
    [],
    [2, 3],
    [1, 4],
    [1, 4],
    [2, 3]
]

visited = [False] * 5

dfs(graph, 1, visited)

코드 설명

스택에 첫 노드를 추가합니다(초기화)

1. 스택에서 노드를 하나 빼냅니다.
2. 그 노드가 방문된 것인지 확인하고 아니라면 방문표시를 합니다.
3. 그 노드와 연결된 노드 중 방문하지 않은 노드를 모두 스택에 넣습니다.
4. 스택이 모두 빌 때까지 반복합니다.

오늘은 dfs에 대해서 두 가지 방법으로 코드를 작성하고 정리해보았습니다. 아직 백준1012번을 풀지 못했지만... 풀게 되면 올리도록 하겠습니다!

끝.

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

1) 큰 수부터 차례대로 나누기(실패)

거스름돈 문제처럼 가장 큰 수 5로 최대한 나눈 후 나머지를 3으로 나눠서 해결하려고 하였다.

*알고리즘 *

• N 을 입력 받기
• N 을 5로 나눠서 몫을 result에 저장하기
• 5로 나눈 나머지를 N에 다시 저장하기
• N 을 3으로 나눈 몫을 result에 더하기
• 3으로 나눈 나머지가 있다면 result = -1
• result 출력

코드

N = int(input())
result=0
for i in [5,3]:
    result += N//i
    N = N % i
if N>0 :
    print(-1)
else :
    print(result)

문제 발생

입력이 11일 때, 5로 나눈 후 나머지는 1이 되어 결과가 -1로 나온다.

하지만, 실제로는 (5+3+3)으로 결과는 3이 나와야 한다. 무조건 큰 수로 먼저 나누는 것은 안되는 결과가 나왔다.

이유는 5가 3의 배수가 아니라서 3의 배수를 완전히 커버할 수 없기 때문이다. 그리디 알고리즘 문제를 풀 때 가장 흔히 하는 실수다.

해결

3을 하나씩 늘려가면서 5로 나누어 떨어지는지 확인하는 방법을 사용하기로 하였다.

2) 3의 개수를 하나씩 늘려가기(성공)

알고리즘

• N을 입력 받는다
• N 에서 3 * i를 뺀다.(i는 0 ~ N//3)
• 뺀 결과가 0이거나 5로 나누어지는지 확인한다
• 맞다면 result에 i+(N-3*i)//5를 저장하고 출력, N = 0.
• 아니라면 i를 1늘려 반복한다.
• 반복이 끝나고 N>0 이라면 -1출력

코드

N = int(input())
result=0

for i in range(N//3 +1):
    if (N - 3*i)<0:
        break
    if (N - 3*i)==0 or (N - 3*i)%5 == 0:
        result += (i+((N - 3*i)//5))
        N=0
        print(result)

if N>0 :
    print(-1)

복잡도

이 코드의 복잡도는 반복문을 주목하면 되는데, 반복문이 N/3 번 반복되기 때문에 O(N) 이라고 할 수 있다.

결론

*그리디 알고리즘 * 카테고리에서 문제를 선택했기 때문에 당연히 가장 큰 수부터 나눠야 할 것이라고 생각했다. 중간에 3과 5의 최소공배수로도 나눠보고, 5를 하나씩 늘리는 방법도 시도했으나 반례에 부딪혔다.

그리디 문제를 풀 때 배수관계에 대해서 주의깊게 살펴야겠다. 쉬운 문제지만 혼자 힘으로 풀어냈다는 점이 뿌듯하다.

끝.

array = list(map(int, input().split()))

파이썬으로 코딩테스트를 준비하면서 가장 어려웠던 점은 C와의 자잘한 문법의 차이였습니다. 특히 입력이 헷갈렸는데, 모두들 당연하게 위의 방법을 사용하고 있었습니다. 외우기보다는 이해하는 것이 더 손에 익을 것 같아 코드를 뜯어보기로 했습니다.

input을 이용해 입력받기

array = list(map(int, input().split()))

위의 한 줄 중 어느 정도까지 이해가 되나요? 저는 map부터 막혔는데 이제는 설명할 수 있습니다. 같이 공부해봅시다!

input().split()이란?

input()은 문자열을 받아오는 메서드입니다.

1 2 3 4 5

위와 같이 입력이 들어왔다면 아래의 코드로 받아올 수 있습니다.

in = input()
print(in)

하지만 input은 한 줄씩 읽어오기 때문에 "1 2 3 4 5" 라는 하나의 문자열을 반환하게 됩니다.

이때 split()메서드를 이용해 문자열을 공백을 기준으로 나누어줄 수 있습니다.

in = input().split()
print(in)

위처럼 리스트 형태로 반환된 것을 확인 할 수 있습니다. 또 하나 눈에 띄는 것은 리스트 안의 각각의 요소가 문자 형태라는 점입니다.

문자를 숫자로 변환해주기 위해서 map() 메서드를 사용할 수 있습니다.

list( map( 함수, 리스트 ) )이란?

map은 리스트의 요소를 지정된 함수로 처리해주는 메서드입니다. 다시 말해서 오른쪽의 입력된 리스트의 각각의 요소를 함수에 통과시켜서 그 결과로 다시 새로운 리스트를 만듭니다.

출처:https://dojang.io/mod/page/view.php?id=2286

왜 list를 이용하는지 궁금해졌기 때문에 map함수에 대해 알아보았습니다. 아래는 map의 결과를 찍어본 결과입니다.

a = map(int, input().split())
print(a)
print(type(a))

map()함수의 반환값은 map 객체입니다. 따라서 이를 리스트로 만들어주기 위해서 list()라는 메서드를 다시 이용하는 것입니다.

결론

처음 코드로 돌아가보겠습니다.

array = list(map(int, input().split()))

이 문장을 이제 완벽하게 이해할 수 있습니다.

input으로 문자열을 받아서 split으로 공백 기준으로 나눠 리스트를 만들고 map을 이용해 요소 각각을 정수로 바꾼 다음 다시 리스트로 만드는 과정입니다.

끝.

코딩 테스트 개념잡기 첫 번째로 그리디(greedy)알고리즘에 대해서 정리해보려합니다.

출처:https://commons.wikimedia.org/wiki/File:Greedy-search-path-example.gif

그리디 알고리즘은 말 그대로 욕심쟁이 알고리즘입니다. 탐욕법이라고도 부르는데, 현재 상황에서 가장 좋은 것을 고르는 방법입니다.

위의 예시처럼 그리디 알고리즘을 이용해 그래프에서 가장 큰 수를 찾으려고 한다면, 현재 위치(7)과 연결된 두 노드 중 큰 노드(12)를 고르는 것입니다. 그리고 이동한 노드(12)에서 또 다시 가장 큰 수를 찾으면 결과적으로 6에 도달하게 됩니다.

단점

전체 문제에 대한 최선의 결과가 아닐 수 있다.

다시 말해서 위의 예시처럼 각 노드에서 가장 큰 수를 골랐지만 결과적으로 전체에서 가장 큰 수를 고르지는 못한 경우입니다.

장점

빠르게 최적해로 가는 근사치를 구할 수 있다

하지만 위와 같은 단점이 있기 때문에 특정 조건에서만 사용 가능합니다.

그럼 어떨 때 사용할 수 있을까?

1. 탐욕적 선택 특성(Greedy choice property) 2. 최적 부분 구조(Optimal substructure)

우리는 위의 두 가지 조건에서 그리디 알고리즘을 적용할 수 있습니다.

다시 위의 예시를 보겠습니다. 우리가 12를 고르게 되면서 3으로 가는 경우가 사라졌습니다. 이러면 12를 고른 결정이 최종 결과에 영향을 미치게 됩니다.

이는 탐욕적 선택 특성에 어긋납니다.

탐욕적 선택 특성이란, 지금의 선택이 다음 선택에 영향을 주지 않는 것을 의미합니다.

유명한 다른 예시를 들어보겠습니다. 서울에서 대전을 거쳐서 부산으로 가장 빨리가는 방법을 찾는 문제입니다.

출처:https://yganalyst.github.io/concept/algo_cc_book_1/

서울에서 대전까지의 경로가 대전에서 부산까지의 경로에 영향을 미치지 않습니다.

그래서 서울에서 대전까지 가장 빠른 경로 7, 대전에서 부산까지 가장 빠른 경로 22를 고르면 결과적으로 서울에서 부산까지 가장 빠른 경로를 찾을 수 있는 것입니다.

각 부분의 최선의 선택의 합이 전체의 최선의 결과가 되는 것이 최적 부분 구조입니다.

따라서 코딩테스트에서 특정 문제를 만났을 때 그리디 알고리즘을 사용하고 싶다면, 현재 상황의 최선의 선택의 조합으로 문제가 해결되는지 판단하는 것이 핵심입니다.

예제 종류

• 거스름돈 문제 : 가장 적은 수의 동전을 이용해 특정 값을 지불하는 문제입니다

• 1이 될 때까지 : 어떤 수 N이 1이 될 때까지 -1또는 %K를 반복 수행 하여 가장 적을 횟수로 1을 만드는 문제입니다.

위의 문제들은 제가 풀이하면 올리도록 하겠습니다 끝.

김영한의 spring boot 강의를 들으면서 따라하던 중 spring boot 프로젝트 생성 부분에서 막혔습니다.

문제사항

Could not resolve all dependencies for configuration ':compileClasspath'.

Failed to calculate the value of task ':compileJava' property 'javaCompiler'.

Cannot find a Java installation on your machine matching this tasks requirements: {languageVersion=17, vendor=any, implementation=vendor-specific} for MAC_OS on aarch64.

No locally installed toolchains match and toolchain download repositories have not been configured.

대충 해석해보면, 일치하는 java를 찾을 수 없다는 것인데요.

이렇게 17버전을 쓴다고 해놓고 정작 jdk버전 19로 설정되어있어서 그런 것 아닐까 하는 생각이 들었습니다.

자바 버전 확인

터미널에 아래 명령어를 실행해 현재 저의 자바 버전을 확인했습니다.

> java --version

19버전이 메인 버전으로 설정되어있다는 것을 확인했습니다.

컴퓨터의 깔려있는 모든 sdk를 확인하기 위해서는 아래의 명령어를 실행하면 됩니다.

> /usr/libexec/java_home -V

원하는 자바 버전이 없다면 brew를 통해 설치할 수 있습니다.

> brew info openjdk@17   

저는 17버전을 깔았습니다.

자바 환경변수 설정

자바 17버전을 메인으로 설정해주기 위해서 환경변수를 설정해주었습니다. 꼭 메인으로 설정하지 않더라도 프로젝트 생성은 가능할 듯 합니다.

> vi ~/.zshrc

위의 명령어로 vi를 열어줍니다 i를 눌러 INSERT(수정)모드로 바꿔주고

export PATH=$HOME/bin:/usr/local/bin:$PATH
export JAVA_HOME=/Library/Java/JavaVirtualMachines/openjdk-17.jdk/Contents/Home

이거를 추가해줍니다. 경로이름을 모르겠다 하시는 분은 직접 파인더를 열어

Library/Java/JavaVirtualMachines

들어가면 확인할 수 있습니다

변경하고 나면 esc 누르고 :wq를 입력해 저장하고 나가줍니다.

위에 변경한 내용을 적용해줘야합니다.

> source ~/.zshrc

터미널에 입력해 환경변수를 적용해주면 됩니다.

버전 재확인

정상적으로 변경된 것을 확인할 수 있습니다.

해결!

끝.

웹서버 vs. 웹 어플리케이션 서버

웹서버(Web server): 정적 컨텐츠를 처리. HTML, CSS, JavaScript파일. 처음 페이지가 실행됐을 때. 보통 http요청을 직접 받는(엔드포인트) 역할을 수행. 보안 등 http통신 관리. 어플리케이션 서버로 요청 전달.

예) apache, nginx

어플리케이션 서버(WAS): 동적 컨텐츠 처리. 정보 조회, 로그인 등등.

예) Node.js

http 요청이 처리되는 과정

웹서버에게 http요청이 들어옴

→ 정적 컨텐츠일 경우 웹서버가 파일을 찾아 반환

→ 동적 컨텐츠일 경우 요청을 어플리케이션 서버로 전달

→어플리케이션 서버는 요청을 처리, 응답 생성

→응답을 웹서버에 전달

→웹 브라우저가 응답을 해석하고 화면에 표시(client side javascript가 처리)

웹브라우저: 콘텐츠 렌더링, 사용자 인터페이스, 자바스트립트 파일 실행, http통신 관리, 세션 관리, 보안, 멀티미디어 재생 기능 수행

아나콘다를 정상적으로 다운받았다고 생각했는데 아래 오류때문에 실행이 되지 않았습니다.

'bytes' object has no attribute 'get' 에러..

터미널을 통해 접속해도 같은 문제가 발생했습니다.

구글에 검색했더니 같은 문제를 겪는 사람이 엄청(!!)많았습니다. https://github.com/ContinuumIO/anaconda-issues/issues/13288

정리하자면 몇 가지 방법이 있는 것 같았습니다.

1. 아나콘다를 삭제 후 재설치

답변 중 대부분은 다시 깔아보라는 내용이었습니다.

지우는 법은 간단합니다. finder에서 Macintosh HD로 들어갑니다. opt폴더를 찾습니다 (숨겨져있기 때문에 cmd+shift+. 로 숨김폴더를 확인해야합니다)

위와 같이 opt폴더로 들어갔다면 anaconda3라는 폴더가 보일텐데 그냥 삭제해주면 됩니다. 응용 프로그램에서도 anaconda-Navigator를 지워주면 됩니다.

이후 다운로드 파일을 이용해 다시 설치할 수 있습니다.

결론적으로 저는 실패했습니다.

미련이 남아서 3번이나 재설치했는데 안됐습니다.

2. 아나콘다 업데이트

두번째는 아나콘다를 업데이트하는 방법입니다. 터미널을 통해 아래 명령어를 입력합니다.

conda update anaconda-navigator

파이썬의 버전과 아나콘다의 버전이 맞지 않아서 문제가 될 때 사용할 수 있는 코드인 듯 합니다.

근데 conda 명령어가 동작하지 않는 저로서는 같은 오류가 반복 될 뿐이었습니다.

하지만 한가지 수확이 있었는데, 에러 메시지에서 권한 관련 문제를 발견한 것입니다.

PermissionError: [Errno 13] Permission denied: '/Users/LeeHeejae/.config/conda/.condarc'

그러면 sudo를 이용해 conda를 실행할 수 있지 않을까???

3. sudo 권한 이용하기

sudo conda

일단 콘다가 실행됐습니다.

하지만 이런 방법은 터미널로만 아나콘다를 이용해야 하기 때문에 불편합니다. sudo를 매번 붙여주고 비밀번호도 써줘야해서 더더 불편합니다.

오기가 생겼습니다. 또한 예전부터 sudo로만 실행되는 오류가 항상 있어서 고쳐야겠다고 생각했습니다.

최종 .config에 대한 권한 얻기

이쯤 되니 미룬 구몬 숙제같은.. sudo를 해결하지 않았던 것에 대한 업보 청산에 가까웠습니다..

30분가량 구글링한 결과 https://apple.stackexchange.com/questions/320682/ownership-of-the-config-folder-in-home-directory

sudo chown -R <username> .config

이런 간단한 코드로 해결할 수 있더군요

이거지예..

모든 'bytes' object has no attribute 'get'에러가 이런 방식으로 해결될 수 있을지는 모르겠습니다.

에러 메시지도 좀 더 뜯어봐야겠지만 딥러닝 프로젝트를 시작할 수 있게 된 것 만으로 만족합니다.

뭘 하든 개발환경 만드는 게 제일 어렵네요.. 끝!![]