📌 그래프의 기본 구조 DFS와 BFS를 공부하기 앞서, 그래프의 기본 구조를 먼저 알아보자. 그래프는 노드(Node)와 간선(Edge)로 표현되며, 이때 노드를 정점(Vertex)라고도 한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한, 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩 테스트에서도 필요한 개념이니 꼭 숙지하도록 하자. 1. 인접 행렬(Adjacency Matrix) 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같은 예시 그래프가 있다고 했을 때, 이..
📌 구현(Implementation) 이란? 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이지만, 보통 특별한 알고리즘보다는 문제를 요구사항에 맞춰 코드로 풀어내는 능력 + 프로그래밍 언어의 문법의 정확한 이해를 갖추고 있는지 보는 문제라고 생각하면 될 것 같다. 예시로는 다음과 같은 것들이 있다. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 사소한 조건 설정이 많은 문제 보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 하지만 고차원적인 ..
📌 그리디 알고리즘이란? 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'으로, 단순하지만 강력한 문제 해결 방법이다. 우리는 특정 문제를 만났을 때, 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이러한 기준은 정렬 알고리즘으로 만족시킬 수 있으므로 그리디 알고리즘 문제는 정렬과 짝을 이뤄 출제된다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 크다. 그렇기 때문에, 그리디 알고리즘으로 문제의 해결책을 찾았을 때는 그것이..
오늘은 시간 복잡도와 공간 복잡도에 대해서 간단히 알아보고, 코테 문제를 풀 때 알아두면 좋을 내용을 정리해보려고 한다! 📌 시간 복잡도 알고리즘이 얼마나 오래 걸리는지 알 수 있는 척도로, 알고리즘을 위해 필요한 연산의 횟수를 의미한다. 코테 문제에는 '시간 제한'이라는 것이 있다. 여기서 말하는 시간 제한은 문제를 푸는 시간이 아니라, 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서, 프로그램을 비효율적으로 작성하면 '시간 초과' 메시지와 함께 오답 처리가 된다. 따라서, 문제를 풀 때 최악의 연산량을 계산해 내가 사용할 수 있는 알고리즘을 고르는 것이 좋다. 아래는 대표적인 시간 복잡도를 나타낸 것이다. 빅오 표기법 명칭 N=1000일..
📌 탄력적 IP 주소란? AWS EC2 인스턴스를 사용할 때 설정하는 고정 IP를 말한다. (EC2 인스턴스뿐만 아니라 로드밸런서, 넷게이트웨이에도 사용할 수 있다고 한다 - 하단 링크 참고) 프리티어를 사용하다 보면, 720시간 제한 때문에 인스턴스를 중지시켜 놓는 경우가 있다. 이렇게 인스턴스를 중지시켰다가 다시 시작하면 퍼블릭 IP 주소가 변경된다! 프로젝트를 할 때, 혹은 회사에서 사용할 때 이렇게 퍼블릭 IP 주소가 변경되면 매우매우 불편하기 때문에 탄력적 IP를 할당해 주는 것이다. 탄력적 IP를 할당하고 나면, 인스턴스를 일시중지했다가 다시 시작했을 때도 IP가 그대로 유지된다. 🚫 주의 🚫 아래에 해당하는 경우에는 과금이 될 수 있으니 주의하자! - 탄력적 IP를 생성하고, EC2 인스턴스..
📌 AWS EC2란? AWS에서 제공하는 클라우드로, Amazon Elastic Compute Cloud의 준말이다. 나는 백엔드 위주로 개발을 하다 보니, 백엔드 코드를 올리는 서버 용도로만 생각했었는데 이번에 아마존 공식 설명을 읽어보니까 기계학습 프로젝트용으로도 쓰는 것 같다. 아무튼 이번에는 프로젝트할 때 제일 많이 쓰는 ✨프리티어✨에서 사용 가능한 Ubuntu 서버 인스턴스 생성 과정을 정리해 보려고 한다. 기본 중의 기본 중의 기본!! 이지만 괜히 잘못 만들었다가 돈나오면 안되니까! 먼저 EC2 대시보드에서 '인스턴스 시작'을 눌러준다. 이때 내 계정 왼쪽에 있는 지역이 '서울'로 되어있는지 꼭 확인해준다! 그러면 아래같은 화면이 나타나는데, 여기서 Ubuntu Server 를 선택해준다. 밑..
