브랜치명이 다른 원격 브랜치에 push해야 하는 경우에는
아래와 같은 형식으로 쓰면 된다.
git push 원격저장소명 로컬브랜치:원격브랜치 |
예시)
git push origin patch:gh-pages
원격 저장소로부터 pull을 받는 경우
아래와 같이 순서를 바꾸어서 쓴다.
git pull 원격저장소명 원격브랜치:로컬브랜치 |
만약 대상 브랜치가 HEAD가 가리키고 있는 브랜치이면 로컬 브랜치를 생략하여
git pull 원격저장소명 원격브랜치
와 같이 쓸 수 있다.
리눅스 환경에서 C언어를 사용하여 빠른 프로세스간 통신(IPC)를 구현해야 할 때에 공유메모리를 사용할 수 있다. 그러나 한 프로세스가 데이터를 읽는 도중에 다른 프로세스가 해당 공간에 대해 쓰기 작업을 한다면 데이터 부정합이 발생할 수 있다. POSIX 세마포어 중 이름 있는 세마포어(named semaphore)를 사용하여 공유자원에 대한 동시 접근 문제를 해결할 수 있다.
공유메모리를 사용하기 위해 아래와 같은 함수들을 사용해야 한다.
shmget()
임의의 키값과 메모리크기를 매개면수로 주어 공유메모리 생성을 커널에 요청하고, 정상적으로 생성되었을시 id를 받아온다.
shmat()
공유메모리를 현재 프로세스에 붙인다(attach) 반환값으로는 공유메모리의 포인터가 나오고 이 포인터를 통해 메모리에 접근할 수 있다.
shmdt()
공유메모리를 현재 프로세스에서 분리한다(detach)
shmctl()
sem_open()
named 세마포어를 생성하고 세마포어 구조체 포인터(sem_t *)를 받아온다.
sem_wait()
공유자원에 접근하기 전에 세마포어를 잠근다. 만약 해당 자원에 접근할 수 있는 프로세스가 최대 1개이고, 잠겨있는 상태이면 block되어 풀릴 때까지 대기한다.
sem_trywait()
sem_wait()의 논블로킹 함수로, 자원이 잠겨 있어도 일단 -1을 반환하며 함수가 종료되고, errno를 통해 추가적인 처리를 할 수 있다.
sem_post()
공유자원에 대한 접근이 끝났을 때 세마포어 잠금을 해제한다.
sem_close()
해당 프로세스에서 세마포어를 닫는다.
sem_unlink()
세마포어를 파괴한다.
예제코드는 아래와 같이 컴파일하였다.
clang provicer.c -o provider -std=gnu99 -lpthread
provider.c
#include <stdio.h> #include <stdlib.h> sem_unlink("mysem"); |
consumer.c
#include <stdio.h> #include <unistd.h> sem_close(mysem); |
출처
Koreatech Online Judge(링크)
문제이해
양의 정수를 1부터 일렬로 나열했을 때 (ex 123456789101112...) P번째에 오는 숫자를 구하는 문제이다.
문제접근
자리수가 1개인 수(1~9), 2개인 수(10~99), 3개인 수(100~999), ... 를 구분하여 계산한다
구현
아래와 같은 규칙이 있다.
- 자리수가 1개인 수를 모두 썼을 때는 길이가 9인 문자열이 생성된다.
- 자리수가 2개인 수를 모두 썼을 때는 길이가 90*2 = 180 인 문자열이 생성된다.
- 자리수가 3개인 수를 모두 썼을 때는 길이가 900*3 = 2700인 문자열이 생성된다.
만약 P 값으로 2889가 입력된다면, 그 수는 9+180+2700 이므로 세 자리 숫자 중 가장 마지막에 오는 숫자(999)일 것이다.
같은 방법으로, 임의의 P가 있을 때 이 수가 몇 자리 수로 이루어진 정수까지 썼을 때 나온 길이인지 계산할 수 있으며, 해당 자리 수를 가진 수 중 가장 작은 수까지 썼을 때 문자열의 길이도 구할 수 있다.
1부터 n까지 수를 일렬로 나열했을 때 문자열의 길이를 f(n)이라 한다면,
예를 들어, f(1000)과 f(10000)을 미리 계산할 수 있으므로, P가 이 사이의 값이라면 P는 네 자리 수까지 썼을 때의 값이다. 이 P값에서 f(1000)을 뺀 후 4로 나누고, 1000을 더하면, n값을 알 수 있는 것이다.
실행결과
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1068/1068.cpp
2015년 12월부터 만들기 시작한 시간표 프로그램.
수강신청을 할 때 선택한 과목의 시간을 바로바로 알 수 있는 웹페이지이다.
과목코드, 과목명, 교수님 검색이 가능하며 이미지저장기능과 공유기능이 있다.
아직 전체적으로 미완성인 상태이며 점차 새로운 기능을 추가할 계획...
Javascript, jQuery3, Ajax 사용.
사이트 주소 : http://hanpyo.com
소스코드 : https://github.com/zetagate/hanpyo (라이센스 : GPL v3)
xor연산자를 사용하여 Javascript로 canvas에 간단한 패턴 이미지를 그려보았다.
for(var i=0; i<height; i++) { for(var j=0; j<width; j++) { pixels[i*width + j] = (i^j)%256; } } |
xor연산자 대신 atan2()함수를 사용한 결과
for(var i=0; i<height; i++) { for(var j=0; j<width; j++) { var dist = getDist(j-width/2, i-height/2); //거리 var dir = getDir(j-width/2, i-height/2); //각도 pixels[i*width + j] = (256-dist)/(dir/96); } } |
전체 소스코드 : https://github.com/tibyte/visual/tree/master/xor
출처
Koreatech Onlinejudge(링크)
문제이해
-50000이상 50000이하 정수로 이루어진 배열이 입력된다. 두 개의 수를 제외한 나머지 수는 모두 2개씩 존재한다. 단 하나씩만 존재하는 두 수를 크기가 작은 것부터 출력하는 문제이다.
문제접근
유일한 수를 찾는 문제에서는(링크) 모든 배열원소들을 XOR연산으로 누적하여 쉽게 구할 수 있었다. 그러나 이 문제에서는 2개를 찾아야 하므로 단순히 XOR로는 구할 수 없다.
1. 배열 이용
입력되는 수의 범위가 -50000부터 50000까지 100001크기의 범위이므로 크기 100001짜리 배열을 만들고, 모든 인자를 0으로 초기화한 후, 입력배열을 순차탐색하면서 해당 입력값을 인덱스로 하는 배열위치에 1을 더한다. 이 과정이 끝났을 때 1이 기록되어 있는 위치를 출력하면 된다. 이 방법의 한계는 입력되는 수의 범위가 더 클 경우 적용할 수 없다는 것이다.
2. std::map 이용
입력되는 수를 std::find()로 찾아서 값이 있으면 std::erase()로 지우고 없으면 추가한다.
최종적으로 남은 요소를 출력하면 된다
std::map은 rbtree로 되어있기 때문에 각 연산이 O(logn)이며 입력의 수만큼 반복하게 되므로 복잡도는 O(nlogn)이 된다.
3. 비트연산(XOR) 이용
(참고 : http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/)
XOR연산으로도 이 문제를 풀 수 있다. 우선 모든 수를 XOR연산으로 누적하면 하나의 수가 나오는데, 이것은 답으로 출력해야 할 두 수의 XOR연산결과이다. 이 결과에서 rightmost set bit(낮은 비트부터 봤을 때 1이 처음으로 나타나는 위치)을 찾는다.
예를 들어 XOR결과가 이진수로 1101000라고 하자. rightmost set bit을 제외한 나머지 비트들을 0으로 하면 0001000이 된다. 이것은 모든 입력값들 중에서 해당 위치에 1이 쓰여진 원소가 홀수 개라는 뜻이 된다. 즉, 구하고자 하는 답 중에서 하나는 해당 위치에 1이 쓰여진 원소들 중에서 나오고, 다른 하나는 해당 위치에 0이 쓰여진 원소들 중에서 나온다는 것이다.
이제 다시 모든 원소들을 위에서 구한 XOR값(위 예시에서는 0001000)과 비트 AND 연산을 하면서, 결과가 1인 경우와, 결과가 0인 경우로 나누어 각각 XOR연산으로 누적한다.
for(int i=0; i<N; ++i) { if(arr[i]&det) { xora ^= arr[i]; } else { xorb ^= arr[i]; } } |
문제의 조건에 따라, 구한 두 값을 크기순서로 출력하면 된다.
구현
이 문제에서 필요한 rightmost set bit의 형태는 위치값이 아니라, 해당 비트만 1로 세팅된 수이기 때문에 아래와 같은 간단한 연산으로 구할 수 있다. (1101000을 예시로 하여 직접 계산해 보면 이해할 수 있다.)
num&(~num+1)
이 연산을 잘 보면, 2의보수를 구하고 있는 형태이기 때문에
num&-num 으로도 쓸 수 있다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1074/1074.c
보로노이 다이어그램을 이용하여 오각형 Type 5 테셀레이션을 그려보았다.
(1) 사잇각이 60도인 기준점들을 찍는다.
(2) 기준점을 중심으로 하여 일정한 각도로 6개의 시드 점을 찍는다.
(3) 시드점을 기준으로 시드점에서 가장 가까운 거리에 있는 픽셀들끼리 묶어서 평면을 분할한다.
(4) 완성된 테셀레이션
소스코드
https://github.com/tibyte/visual/blob/master/tessellation
캔버스의 크기가 작아서 외접원을 구하지 않고 단순 반복문으로 구현...
|
출처
Koreatech OnlineJudge(링크)
문제이해
5000자 이하의 문자가 입력으로 주어지고, 임의의 위치에 문자를 추가하여 펠린드롬으로 만들 때 추가하는 문자의 개수를 최소화하면, 몇 개인지를 구하는 문제이다.
문제접근
동적 프로그래밍 문제이다.
인덱스 a부터 인덱스 b까지의 구역에 대해 펠린드롬을 만들기 위한 최소비용을 D[a][b]라고 하자. D[a][b]를 한 단계 작은 계산결과로 구하기 위해 두 가지 조건을 따져봐야 한다.
1. 구역의 맨 앞과 맨 뒤가 같은 문자인 경우
D[a][b] (구역의 전체)는 D[a+1][b-1] (회색 부분)와 같다.
2. 구역의 맨 앞과 맨 뒤가 다른 문자인 경우
D[a][b] = 1+min(D[a][b-1], D[a+1][b])
a부터 b-1까지의 부분구역과, a+1부터 b까지의 부분구역 중에서 비용이 작은 것을 선택하여 거기에 1을 더한 값을 D[a][b]로 한다.
Top-down 방식으로 점화식을 해결하면 시간복잡도가 지수함수가 되므로, 아래에서부터 누적하여 구해야 한다.
구간의 길이를 1부터 전체까지 늘려 가며 데이터를 얻는 것이다.
전에 포스팅했던 이 문제와 같은 아이디어이다.
구현
다음과 같이 전처리하면 복잡하지 않게 반복문을 짤 수 있다.
- 구간의 길이가 1인 경우 D값은 0으로 한다.
- 구간의 길이가 2인 경우 D값은, 두 문자가 같을 때 0, 다를 때 1로 한다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1060/1060.cpp
