BOJ 1517 버블 소트


https://www.acmicpc.net/problem/1517


https://github.com/simjaemun2/BaekJoon/blob/573ed75b9d62e5d0b6131fbb55f5fa6790eff75f/BOJ1517/BOJ1517.cpp


난이도 H


버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내느 문제


비슷한 문제로 삽입 정렬을 수행할 때 숫자들을 총 몇 번 옮기는지 계산하기



일반적인 버블소트는  O(N^2) 이기 때문에

문제 조건에서의 수행 시간을 만족하지 못함


이 문제를 풀기 위해선 O(N logN) 시간을 만족해야 함


O(N logN) sort + binary search, 팬윅 트리(바이너리 인덱스드 트리) 등을 이용하는 방법이 있지만

병합 정렬을 이용해서 문제 풀이가 가능


자세한 설명은 JM Book 762 페이지를 참고

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 2186 문자판  (0) 2017.02.15
BOJ 1080 행렬  (0) 2017.01.30
이분 그래프  (0) 2017.01.16
BOJ 1167 트리의 지름  (0) 2017.01.15
BOJ 1890 점프  (0) 2017.01.04

BOJ 1080 행렬


https://www.acmicpc.net/problem/1080


https://github.com/simjaemun2/BaekJoon/blob/61c09ddf7b85d71c0afa0bcc4b8b580219db07d9/BOJ1080/BOJ1080.cpp


그리디 알고리즘

난이도 MH ~ H


배열의 첫 인덱스부터 따라가면서

A배열과 B배열의 값이 다르면

그 칸을 기준으로 A배열을 뒤집는다.


마지막에 A배열과 B배열이 다른지만 확인한다.


비트 연산으로 구현하면 속도를 줄일 수 있지만

이 문제는 N이 작아서 그런 작업이 불필요하다.

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 2186 문자판  (0) 2017.02.15
BOJ 1517 버블 소트  (0) 2017.02.13
이분 그래프  (0) 2017.01.16
BOJ 1167 트리의 지름  (0) 2017.01.15
BOJ 1890 점프  (0) 2017.01.04

https://www.acmicpc.net/problem/1476


위 문제를 O(1)로 풀 방법이 있나 찾아보다가

[중국인의 나머지 정리]라는 것을 찾았다.


이론에 대한 설명은 아래에 자세히 나와있다.


https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC#fn-10


다음은 BOJ 1476 날짜계산을 푸는 과정이다.


(28 * 19 * e) % 15 == (532 * e) % 15 == (7 * e) % 15 == 1

(15 * 19 * s) % 28 == (285 * s) % 28 == (5 * s) % 28 == 1

(15 * 28 * m) % 19 == (420 * m) % 19 == (2 * m) % 19 == 1


e == 13, s == 17, m == 10


[포인트 1]

(532 * e) % 15 == (7 * e) % 15


[포인트 2]

(7 * e) % 15 == 1

e의 값은 위 식을 만족하는 수 아무거나 고르면 되긴 하지만, 가장 작은 값을 찾는게 빠름



ANSWER = (E * 28 * 19 * 13 + S * 15 * 19 * 17 + M * 15 * 28 * 10) %  (15 * 28 * 19)

             = (E * 6916 + S * 4845 + M * 4200) % 7980

'컴퓨터공학 > Algorithm' 카테고리의 다른 글

BOJ 6588 골드바흐의 추측  (0) 2016.11.29
Trie  (0) 2015.07.27
shell sort  (0) 2013.01.04
시간복잡도  (0) 2013.01.04
Sorting  (0) 2013.01.03

새로운 기술을 익히는 10단계 학습법 by 소프트 스킬


1. 큰 그림을 보라


2. 범위를 정하라


3. 성공을 정의하라


4. 자료를 찾아라


5. 학습 계획을 세워라


6. 자료를 선별하라


7. 대충 사용할 수준까지 배워라


8. 놀아라


9. 유용한 일을 할 정도까지 배워라


10. 가르쳐라

'컴퓨터공학 > Soft Skill' 카테고리의 다른 글

개발자 8가지 유형  (0) 2017.05.21

BOJ 1707 이분 그래프


https://www.acmicpc.net/problem/1707


https://github.com/simjaemun2/BaekJoon/blob/e966b8ff93461ba2c36383c5ee9392b865eb7a6b/BOJ1707/BOJ1707.cpp


이분그래프


난이도 : MH


이분 그래프란?


그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프

-> 인접하고 있는 노드가 서로 다른 2개의 색을 칠하는 것이 가능한 그래프


DFS나 BFS 로 노드를 따라가면서 1이나 -1로 색을 칠한다.

이 때, 인접한 노드의 색이 자신과 같은 색으로 이미 칠해져 있다면, 이분 그래프가 아닌 것을 확인할 수 있음


그런데 인풋 맵 안에 partial graph가 존재할 수 있으므로,

반복문을 통해 모든 노드를 확인해야 함

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 1517 버블 소트  (0) 2017.02.13
BOJ 1080 행렬  (0) 2017.01.30
BOJ 1167 트리의 지름  (0) 2017.01.15
BOJ 1890 점프  (0) 2017.01.04
BOJ 11404 플로이드  (0) 2017.01.03

BOJ 1167 트리의 지름


https://www.acmicpc.net/problem/1167


트리, DFS


난이도 MH




트리의 지름이란?

트리의 한 정점(V1)에서 다른 정점(V2) 까지의 거리가 제일 큰 것을 트리의 정점이라 한다.


보통 트리의 지름을 구하는 방법은

아무 정점이나 하나 골라서 가장 거리가 먼 V1을 찾고

그 V1을 이용해 가장 거리가 먼 V2를 찾아 길이를 구하면 트리의 지름이 된다.


#define _CRT_SECURE_NO_WARNINGS 

#include 
#include 
#include 
#include 

using namespace std;

#define MAX_N 100000

int N, A, B, V;

typedef pair PAIR;
vector > input;
bool v1[MAX_N + 1];
bool v2[MAX_N + 1];

PAIR longest(int v, bool* visited)
{
	visited[v] = true;

	PAIR ret = make_pair(0, 0);

	for (int i = 0; i < input[v].size(); i++)
	{
		if (!visited[input[v][i].first])
		{
			PAIR p = longest(input[v][i].first, visited);

			if (ret.second < input[v][i].second + p.second)
			{
				ret.second = input[v][i].second + p.second;
				ret.first = p.first;
			}
		}
	}

	if (ret.first == 0)
		return make_pair(v, 0);
	return ret;
}

int main(int argc, char** argv)
{
#ifdef _WIN32
	freopen("Text.txt", "r", stdin);
#endif

	scanf("%d", &N);

	input = vector >(N + 1);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &V);

		while (true)
		{
			scanf("%d", &A);

			if (A == -1)
				break;

			scanf("%d", &B);

			input[V].push_back(make_pair(A, B));
		}

	}

	PAIR p1 = longest(1, v1);
	PAIR p2 = longest(p1.first, v2);
	printf("%d", p2.second);

	return 0;
}



'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 1080 행렬  (0) 2017.01.30
이분 그래프  (0) 2017.01.16
BOJ 1890 점프  (0) 2017.01.04
BOJ 11404 플로이드  (0) 2017.01.03
BOJ 2096 내려가기  (0) 2016.12.04

BOJ 1890 점프


https://www.acmicpc.net/problem/1890


https://github.com/simjaemun2/BaekJoon/blob/81ca03af7ed86a85aac3b94c02d39adcd4d6b7e2/BOJ1890/BOJ1890.cpp


DP


난이도 : MH


결과 값의 범위에 유의

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

이분 그래프  (0) 2017.01.16
BOJ 1167 트리의 지름  (0) 2017.01.15
BOJ 11404 플로이드  (0) 2017.01.03
BOJ 2096 내려가기  (0) 2016.12.04
BOJ 10472 십자뒤집기  (0) 2016.11.27

ReactiveX


http://reactivex.io/


Observable 스트림을 이용한 비동기 이벤트 기반 프로그래밍 프레임워크


행위(Behavioral) 디자인 패턴의 종류 중 하나인 Observer pattern을 확장


기존의 Future를 이용한 비동기 구문은 하나의 구문을 이용해 서로 다른 이벤트를 여러 차례 받는 것이 불가능하다.

이러한 Future의 단점을 극복한 것이 ReactiveX(이하 RX)



RxScala


RxJava 의 adapter

https://github.com/ReactiveX/RxScala


RxScala는 기본 라이브러리가 아니므로, 아래 Maven 경로를 이용하여 다운

https://mvnrepository.com/artifact/io.reactivex/rxscala_2.11/0.26.4



Observable[T] - T 타입의 이벤트를 만들어내는 이벤트 스트림


Observable 인스턴스는 subscribe 메소드를 이용해 observer(관찰자)를 받음


val o = Observable just (1,2,3)
o subscribe (n => println(s"first subscribe : $n"))
o subscribe (n => println(s"second subscribe : $n"))


위의 코드는 아래와 같은 결과를 비동기적으로 호출한다.


first subscribe : 1

first subscribe : 2

first subscribe : 3

second subscribe : 1

second subscribe : 2

second subscribe : 3 



아래와 같이 예외가 발생했을 때, 동작하는 코드를 작성하면 다음과 같이 동작한다.


val exception = new Exception
val o = Observable.just(1,2) ++ Observable.error(exception) ++ Observable.just(3,4)

o.subscribe(
  n => println(s"number $n"),
  e => println(s"error : $e")
)

number 1

number 2

error : java.lang.Exception


첫 번째로 넘긴 observer에서 1,2를 정상 출력 하지만,

그 다음 exception에서 예외가 발생하여 해당 이벤트를 추가로 실행시키지 않고 두 번째 observer로 넘긴다.


그리고 예외가 발생하여 해당 인스턴스가  오류 상태에 진입하여 3,4에 대하여 이벤트를 발생시키지 않는다.



Observable 객체의 상태(state)는 uncompleted, error, completed 3 가지가 있다.


이 상태들을 이용해 이벤트를 발생시키는 트레이트(trait) 는 다음과 같다.


//rx.lang.scala.Observer.scala
trait Observer[-T] extends scala.AnyRef {
  private[scala] val asJavaObserver : rx.Observer[_ >: T] = { /* compiled code */ }
  def onNext(value : T) : scala.Unit = { /* compiled code */ }
  def onError(error : scala.Throwable) : scala.Unit = { /* compiled code */ }
  def onCompleted() : scala.Unit = { /* compiled code */ }
}
object Observer extends scala.AnyRef with rx.lang.scala.ObserverFactoryMethods[rx.lang.scala.Observer] {
  private[scala] def apply[T](observer : rx.Observer[T]) : rx.lang.scala.Observer[T] = { /* compiled code */ }
  def apply[T](onNext : scala.Function1[T, scala.Unit], onError : scala.Function1[scala.Throwable, scala.Unit], onCompleted : scala.Function0[scala.Unit]) : rx.lang.scala.Observer[T] = { /* compiled code */ }
}



다음 예제는 Observer 인스턴스를 생성하고 Obervable 인스턴스에 직접 대입한다.



val exception = new Exception
val o1 = Observable.just(1,2) ++ Observable.error(exception) ++ Observable.just(3,4)
val o2 = Observable.just(1,2) ++ Observable.just(3,4)

val observer = new Observer[Int]{
  override def onNext(n: Int) = println(s"number $n")
  override def onError(error: Throwable) = println(s"error : $error")
  override def onCompleted() = println("The End!!")
}

o1.subscribe(observer)
println("------------------------------------------")
o2.subscribe(observer)


number 1

number 2

error : java.lang.Exception

------------------------------------------

number 1

number 2

number 3

number 4

The End!!


uncompleted 상태에서 error, completed 상태 두 가지 중 하나의 상태로만 이동할 수 있다.

따라서, 예외가 발생하면 오버라이드한 onError 메소드의 이벤트만 생성시킨다.




Future & Observable


Future를 이용하여 Observable 인스턴스를 생성 가능


Future 성공 => Future의 결과를 이벤트로 반환 및 onCompleted 메소드 호출

Future 실패 => onError 메소드 호출



아래 예제 코드와 같이 Future를 이용하여 Observable 인스턴스를 생성할 수 있다.

또, 주석과 같이 from 메소드를 이용하여 생성할 수도 있다.

import scala.concurrent._
import ExecutionContext.Implicits.global

val future = Future {"Back to the Future !!"}
val observable = Observable[String]{ observer =>
  future foreach {case string => observer.onNext(string)}
  future.failed foreach {case exception => observer.onError(exception)}
  Subscription()
}
observable.subscribe(println(_))
//val observable2 = Observable.from(Future {"Back to the Future 22 !!"})



Observable Combinator


Observable 객체의 장점은 바로 여러 Combinator를 이용하여 조합이 가능하다는 것이다.


아래 예제는 함수 Combinator를 이용하여 0.1초 간격으로 짝수를 생성하는 이벤트이다.



import scala.concurrent.duration._

val even = Observable.interval(0.1.seconds).filter(_%2==0).map(n => s"number : $n").take(7)
even.subscribe(println(_), exception => println(s"exception : $exception"), ()=>println("no more even number"))
Thread sleep 2000


number : 0

number : 2

number : 4

number : 6

number : 8

number : 10

number : 12

no more even number




스칼라의 for 내장 기법을 이용하면 더 짧은 코드로 프로그래밍이 가능하다.


val even2 = for(n <- Observable.from(0 until 12); if n%2==0)
      yield s"number : $n"



내포된 Observable(고차 이벤트 스트림 Higher-order event stream)


고차함수의 예

foreach : (T => Unit) => Unit 처럼 함수 타입 안에 함수가 내포되어 있음


고차 이벤트 스트림

Observable[ Observable[ T ] ] 와 같이 이벤트가 내포


오래 걸리는 연산을 하는 Future 를 바탕으로 생성한 Observable 객체가 있다고 가정



import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global

def longObservable : Observable[String] = Observable.from(Future{
  val random = scala.util.Random.nextInt(10)
  Thread sleep 100 * random
  "Long Long Exec : " + random
})

def observable : Observable[Observable[String]] = Observable.interval(0.1.seconds).take(4).map {
  n => longObservable.map(exec => s"exec $n : " + exec)
}


내포된 Observable[ Observable[String] ] 객체에서 String이벤트를 처리하기 위해 두 가지 방법이 있음


먼저 concat 함수는 이벤트의 실행 순서를 유지하면서 이벤트 결과를 반환한다

observable.concat.subscribe(println(_))
Thread sleep 2000


exec 0 : Long Long Exec : 2

exec 1 : Long Long Exec : 2

exec 2 : Long Long Exec : 1

exec 3 : Long Long Exec : 0 



두 번째로, flatten 함수는 이벤트의 실행 순서를 보장하지 않고

먼저 완료되는 대로 결과를 반환한다


flatten 은 특정 이벤트가 완료하지 않거나, 무한정 이벤트를 발생시킬 수 있을 때 사용

observable.flatten.subscribe(println(_))
Thread sleep 2000



exec 3 : Long Long Exec : 4

exec 1 : Long Long Exec : 7

exec 0 : Long Long Exec : 9

exec 2 : Long Long Exec : 8



flatten + map 조합의 경우

flatMap 으로 대치하여 사용할 수 있다.


def observable : Observable[String] =
Observable.interval(0.1.seconds).take(4).flatMap{ n => longObservable.map(exec => s"exec $n : " + exec)}

observable.subscribe(println(_))
Thread sleep 2000




flatMap을 사용한 경우는

for 내장식으로 바꿔서 코드를 더 간결하게 사용 가능하다.


def observable = for {
  n <- Observable.interval(0.1.seconds).take(4)
  exec <- longObservable
} yield s"exec $n : " + exec

observable.subscribe(println(_))
Thread sleep 2000


Ref) 스칼라 동시성 프로그래밍

BOJ 11404 플로이드


https://www.acmicpc.net/problem/11404


https://github.com/simjaemun2/BaekJoon/blob/4bf0ae92959236c131b54630b87312a8833a0e0a/BOJ11404/BOJ11404.cpp


https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm


그래프, 플로이드-마샬, 최단 경로


난이도 : MH

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 1167 트리의 지름  (0) 2017.01.15
BOJ 1890 점프  (0) 2017.01.04
BOJ 2096 내려가기  (0) 2016.12.04
BOJ 10472 십자뒤집기  (0) 2016.11.27
BOJ 11004 K번째 수  (0) 2016.11.27

BOJ 2096 내려가기


https://www.acmicpc.net/problem/2096


https://github.com/simjaemun2/BaekJoon/blob/7e1e8fa7ca3f040ecabc41ea9954532166dc81ca/BOJ2096/BOJ2096.cpp


분류 : DP


난이도 : MH


문제 조건에서 메모리가 4MB밖에 되지 않으므로,

슬라이딩 기법 등 메모리를 적게 사용하는 방법을 이용한다.

'컴퓨터공학 > Program Solving' 카테고리의 다른 글

BOJ 1890 점프  (0) 2017.01.04
BOJ 11404 플로이드  (0) 2017.01.03
BOJ 10472 십자뒤집기  (0) 2016.11.27
BOJ 11004 K번째 수  (0) 2016.11.27
BOJ 1874 스택 수열  (0) 2016.11.27

+ Recent posts