1. 문제https://www.acmicpc.net/problem/1753 이 문제는 시작점 k부터 나머지 간선까지 최단 경로를 구하는 문제다. 정점과 간선의 개수는 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000로 아주 큰 숫자다. 이를 주의해서 풀이해야 한다. 2. 문제 풀이처음에는 다익스트라 알고리즘을 사용해서, 2차원 벡터 weight에 각각의 방향 그래프를 초기화하고, distance를 업데이트하는 방식을 사용했다. 이렇게 하니까 메모리 초과가 떴다. 그 이유는 위에선 언급한 것처럼, 정점과 간선의 개수가 너무 많은데, 불필요하게 weight를 (n+1) * (n+1) 크기를 갖도록 설정해 희소행렬이 되어버렸다. #include #include #include #define INF 99..
전체 글
1. 문제https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 2. 문제 풀이이 문제는 입력받은 숫자를 검사해서 최대 이익을 구해야 한다. 단, 하루에 하나만 구매할 수 있고 매매..
신경망퍼셉트론퍼셉트론은 뉴런에서 착안한 아이디어로 다층 퍼셉트론과 딥러닝에서 핵심 개념이다. 입력층과 출력층으로 구성되며 i 번째 에지는 xi와 wi를 곱해서 출력층으로 전달된다. 출력노드 o는 d+1개의 곱셈을 모두 더한 s를 계산하고 활성함수를 적용한다. 활성함수는 뉴런을 활성화하는 과정을 모방한 함수로 퍼셉트론은 계단함수를 사용한다. 학습 알고리즘사람이 어떤 것을 학습하는 원리와 아주 유사하다. 예를 들어 사람이 수영을 한다고 하자. 수영을 위해 동작을 취하고 만족스러우면 그대로 수영하면 되는데, 만족스럽지 않다면 약간 조정해서 새로운 자세로 동작을 수행한다. 이처럼 조금 더 나은 방향을 향해 개선하는 것인데, 신경망은 가중치를 최적화하는 방향으로 개선한다. 이때 손실함수 J를 계산해서 J(w) 값..
머신러닝의 종류머신러닝의 종류는 3가지로 나눌 수 있다. supervised : 지도학습은 정해진 답을 알려주면서 학습시키는 방법이다. input으로 label(답)을 입력시키고 이것을 학습한 것을 바탕으로 예측하는 방법이다.unsupervised : 비지도학습은 정해진 답을 제공하지 않고 비슷한 데이터끼리 clustering 하는 방법이다.reinforcement : 머신러닝의 꽃이라 불리는 강화학습은 정답이 따로 없고 본인이 학습하고 난 후 보상을 받는 방식으로 학습된다. 머신러닝 모델링과 예측머신러닝에서 데이터셋은 특징 벡터와 레이블로 표현된다. 일반적으로 기계 학습 모델을 학습시키는데 쓰이는 것을 train set, 기계 학습 모델의 성능을 평가하기 위해서 사용되는 것이 test set이다. t..
Instruction Set Architecture(ISA) 명령어는 컴퓨터가 이해할 수 있는 언어이자 프로세서가 돌아가게 하기 위한 최소 단위이다. 소프트웨어와 하드웨어의 인터페이스라고 할 수 있다. 여기에서 잠시 생각해보자. 인텔 CPU와 AMD CPU는 같을까? 동일한 아키텍쳐를 가진다. 그 이유는 OS를 설치해보면 알 수 있는데, 동일한 명령어 집합을 공유하고 있기 때문이다. 그러나 마이크로아키텍쳐는 다르다. 동일한 명령어 집합을 사용하면서, 회사마다 회로 설계방식은 다를 수 있기 때문이다. 지난 글에서 언급했듯 마이크로아키텍쳐는 CPU의 하드웨어 설계를 말한다. 컴퓨터는 2개의 상태를 가지는데, register와 memory이다. 우리는 명령어를 사용해서 각각의 상태를 관리해주어야 한다. 관리하..
컴퓨터란?컴퓨터란 계산하는 기계라는 의미로, 수학적 논리적 계산을 수행하는 기계다. Von Neumann Architecture은 모든 현대 컴퓨터의 시초라고 할 수 있다. 초기 컴퓨터는 기능에 따라 회로를 하나하나 바꿔야 했다. 그러나 효율성이 크게 떨어지는 문제로 모든 프로그램을 메모리 안에 저장하기 시작했다. 이것이 Stored Program Computer(내장형 프로그램 컴퓨터)이다. 대부분 Sequential로 동작한다. Processing Unit은 산술 논리 장치와 레지스터를 의미하고 Control Unit은 명령 레지스터와 Program Counter를 의미한다. 메모리에는 프로그램에 필요한 데이터와 명령어가 저장된다.그러나 이 아키텍쳐는 병목현상이라는 문제점이 있다. 이는 CPU와 메모..
Rust 공식 문서를 참고한 글입니다. 러스트의 표준 라이브러리에 정의되어 있는 collection는 하나의 자료형에 여러 개의 값을 저장한다. build-in array나 튜플 타입과는 다르게 collection들이 가리키는 데이터들은 Heap 영역에 저장된다. 이 말은 데이터의 양이 컴파일 시점에 결정되지 않아도 되고, 프로그램 실행 중에 변화할 수 있다는 뜻이다. 1. 벡터 Vector벡터 자료형은 메모리에서 동일한 자료형 값들을 연속된 공간에 저장하는 컬렉션이다. 이는 Vec로 표기하고 Vec::new를 통해 생성한다. 이때, T에 해당하는 자료형이 무엇인지 알리기 위해서 자료형을 명시해야 한다. 벡터 선언그러나 대부분 초기값과 함께 Vec를 생성하기 때문에 값의 타입을 유추할 수 있다. 그래서..
Rust 공식 문서를 참고한 글입니다. 우리는 지금까지 하나의 파일에서 하나의 모듈 안에 프로그램을 작성했다. 만약에 프로그램이 더 커지면 여러 개의 모듈, 여러 개의 파일들로 분리해야 할 것이다. 하나의 패키지는 여러 개의 바이너리 크레이트를 포함할 수 있고 필요에 따라서 하나의 라이브러리 크레이트를 포함할 수 있다. 약간 어려운 감이 있지만 패키지 관리에 필요한 개념들을 알아보도록 하자. 우리가 앞으로 배울 모듈 시스템에는 아래와 같은 개념이 포함된다. Packages : 크레이트를 빌드, 테스트, 공유할 수 있는 기능Crates : 라이브러리나 실행 파일을 생성하는 모듈 트리Modules과 use : 구조, 범위, 경로의 접근성 제어Paths : 구조체, 함수, 모듈 등 이름을 결정하는 방식 1. ..
Rust 공식 문서를 참고한 글입니다. 열거형 Enum우리가 이전에 Rectangle이라는 구조체를 선언하고 width, height 필드를 가지도록 했다. 그런데 Rust에서는 구조체보다는 enum 을 사용하는 것이 더 적절하다. 왜 구조체보다 열거형이 적절한지 알아보자. 우리가 IP 주소를 v4 또는 v6을 사용한다고 할 때, 아래처럼 나타낼 수 있다.enum IpAddrKind { v4, v6} 이것을 사용하려면, IpAddrKind::v4로 접근할 수 있다. 이것을 사용해서 함수에 적용할 수도 있다. // 함수 정의fn route(ip_kind: IpAddrKind) {}// 함수 호출route(IpAddrKind::V4);route(IpAddrKind::V6); IP 주소 값은 열거형과 ..
Rust 공식 문서를 참고한 글입니다. 메서드메서드는 함수와 유사하게 파라미터를 가지면서 값을 반환할 수 있고 호출되면 그에 해당하는 동작을 할 수 있다. 그러나 메서드는 구조체의 context 안에 선언되고 첫 파라미터는 항상 self여야 한다. 약간 어려우니까 실제 예제를 통해서 이해해보자. #[derive(Debug)]struct Rectangle { width: u32, height: u32,}impl Rectangle { fn area(&self) -> u32 { self.width * self.height }}fn main() { let rect1 = Rectangle { width: 30, height: 50, }; ..