본문 바로가기

전체 글

 (426)
[Algorithm] [Python] 백준/BOJ - 11286 - 절댓값 힙 11286 - 절댓값 힙 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다. 출..
[Algorithm] [Python] 백준/BOJ - 14503 _ 로봇 청소기 14503 - 로봇청소기 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1..
[Algorithm] [Python] 백준/BOJ - 3190 _ 뱀 3190 - 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길..
[Algorithm] Dynamic Programming - 동적 계획법 Dynamic Programming - 동적 계획법 DP, 동적계획법이란? 큰 문제를 작은 문제로 나누어 접근하는 방식의 문제를 일컫는 용어입니다. 어떠한 문제를 나누어 접근한다는 시각에서는 분할정복(Divide and Conquer) 와 컨셉이 비슷합니다. 하지만 나누어 접근하는 작은 문제가 중복해서 일어나는가에 대한 여부에 차이가 존재합니다. 분할정복은 작은 문제에서 반복이 일어나지 않습니다. 반면 DP는 작은 부분의 문제들이 반복되는 컨셉을 이용해 문제를 풀어나가는 방법입니다. Memoization 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 다시 사용하는 방법으로 동적계획법에 핵심이 되는 기술입니다. Memoization은 동적 프로그래밍 방식이 작은 문..
[Algorithm] DFS&BFS - 깊이 우선 탐색, 너비 우선 탐색 (그래프 탐색) DFS & BFS - 그래프 탐색 인접 리스트와 인접 행렬의 차이 인접 행렬 방식은 노드 간 모든 관계를 저장하므로 노드가 많을수록 많은 메모리가 불필요하게 낭비됩니다. 반면, 인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리를 보다 효율적으로 사용하게 됩니다. 하지만 인접 리스트 방식에 비해 특정 두 노드가 연결되어 있는지 바로바로 확인이 불가하기 때문에 정보를 얻는 속도가 느려집니다. DFS DFS의 동작 방식에 대해 알아보겠습니다. DFS는 깊이 우선 탐색 이라는 이름대로 특정 경로를 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 이후, 다시 돌아가서 다른 경로를 탐색하는 알고리즘입니다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 아래와 같습니다. 탐색 시작 노드..
[iOS] RxSwift를 이용한 Login 기능 구현 RxSwift를 이용한 Login 기능 구현 이번에는 RxSwift 와 RxCocoa 를 이용하여 간단한 Login 프로세스를 구현해보도록 하겠습니다. Layout 이번에 만들어 볼 앱의 레이아웃은 위 사진과 같습니다. 간단히 Email과 Password를 입력받기 위한 TextField 와 로그인 진행을 위한 Button을 하나 생성하였습니다. ViewModel View를 위해 ViewModel이 제공해야 하는 프로퍼티와 기능에 대하여 먼저 정의하겠습니다. Input 과 Output 을 나눠서 살펴보면 아래와 같이 정리할 수 있습니다. Input emailTextField: BehaviorRelay pwTextField: BehaviorRelay Output emailText 값과 pwText값의 유효..
[iOS] [Swift] Convenince init convenience init Swift에서 이용되는 init은 다른 언어에서의 init과 같이 동일하게 생성자 역할을 하며 designated init 과 convenience init으로 나뉘어진다. 우리가 일반적으로 쓰는 init() 이 designated init이다. designated init은 반드시 1개는 있어야 하고, convenience init은 말 그대로 보다 유연하고 간편하게 쓰려고 만드는 생성자다. class Person { var name: String var age: Int var height: Int var weight: Int init(name: String, age: Int, height: Int, weight: Int) { self.name = name self.age..
[Algorithm] [Python&Swift] BOJ/백준 - 1439 _ 뒤집기 1439 - 뒤집기 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력..

티스토리툴바