2016/10 31

2016-10-31 7:37pm 월요일

지금 하고 있는게 맞는건가 하는 생각을 하곤 한다. 어쩌다가 한번씩 이러한 질문을 스스로에게 하는데 깊게 생각해보면 지금 하고있는게 맞다는 믿음을 갖고 있다. 항상 같은 대답이 나오지만 주기적으로 지금 하고 있는게 맞는것인가라는 질문을 하곤 한다. 왜인지는 모르겠다. 나 자신에게 내가 맞는 것을 하고 있다는걸 납득시키기 위함인것 같기도 하다. 종종 다른 선택을 했어도 괜찮았을거라는 생각을 한다. 운동을 시작하길 잘한것 같다. 머리속이 하도 복잡해도 운동하고 오면 다 까먹는다. 근데 그게 생각할 가치가 있는 일이어도 까먹는다는게 문제지만...

2.

put someone on the list.someone을 리스트에 올려라.(결혼식 리스트같은거에 추가하라는뜻) what are you up to?뭐하고지내? 뭐하는거야? etc he had help.그가 도움을 받았다. 도움받다 할때 have 씀. what's got into you? 너왜이래?what's got into her? 쟤(그녀) 왜저래? i like to give you a word of caution. 너한테 경고해주고싶다. antagonize적대감을 불러일으키다 what are the odds ~~~~~~할 가능성이 얼마나 될까? it was just flash.그것은 단지 한순간이었다. to the letter 글자 그대로. 말 그대로. on second thought 다시 생각해 보..

private/English 2016.10.30

배낭(Knapsack) 알고리즘 (DP)

잘 정리된 곳 : http://blog.naver.com/mycho/220725983486 개요. 특정 용량의 배낭이 있고 n가지의 물건을 담을 수 있다. n가지의 물건은 각각 가치와 무게가 있으며 가치가 최대로 되도록 배낭에 담는 형식의 문제. 이 배낭 알고리즘에는 3종류가 있다고 한다. 1. 물건 당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 경우.(0-1 Knapsack problem) 2. 물건 당 물건의 수량이 여러개이고, 쪼갤 수 없는 경우.(Bounded Knapsack problem) 3. 물건의 갯수가 무한개이고, 쪼갤 수 없는 경우(Unbounded Knapsack problem) 1. 0-1 Knapsack problem. 물건 당 물건의 수량이 1개이고, 물건을 쪼갤 수 없..

algorithm/theory 2016.10.30

acmicpc.net 3878(볼록 껍질, 기하), 2254(볼록 껍질, 기하), 2166(기하)

https://www.acmicpc.net/problem/3878 1. n의 점 집합에 대해 볼록 껍질을 만든다.2. m의 점 집합에 대해 볼록 껍질을 만든다.3. 두 볼록 껍질이 교차하는지 검사한다. 교차하면 NO. 교차안하면 YES다.종만북에서 소스를 가져왔다. #include #include #include #include #include #include #include #include using namespace std; const double EPSILON = 1e-8; const double PI = 2.0 * acos(0.0); // 2차원 벡터를 표현한다 struct vector2 { double x, y; explicit vector2(double x_ = 0, double y_ = 0)..

1.

put yourself out : ~를 위해 특별히 애를 쓰다.you put yourself out there for another person. 남을 위해 나섰구나. can't get enough of it : 질리지 않다.이 장소는 너무 예뻐.can't get enought of it. 절대로 질리지 않죠. wild goose chase : 헛된 노력, 부질없는 시도.이 범죄자를 조사해봤자 더 나오는건 없을거야.it's a wild goose chase. 헛된 노력이야. composite sketches : 몽타주(n) gas up : 기름채우다 v blow your cover : 위장이 들통나다, 숨기고있는게 들통나다 uneventful : 특별한 일이 없는.it's uneventful : 특별한 ..

private/English 2016.10.29

acmicpc.net 12781(벡터, 기하), 1708(볼록 껍질, 기하), 9240(볼록 껍질, 기하)

https://www.acmicpc.net/problem/12781 종만북에서 소스를 가져왔다. 벡터로 선분이 평행한지 조사해서 평행하면 0, 아니면 4조각으로 자를 수 있다는 뜻이므로 1을 리턴했다. #include #include #include using namespace std; const double PI = 2.0 * acos(0.0); struct vector2 { double x, y; vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_) {} // 두 벡터가 같은 경우 bool operator == (const vector2& rhs) const { return x == rhs.x && y == rhs.y; } // 벡터의 덧셈과 뺄셈, 단항 연산..

acmicpc.net 9934(트리, BFS), 5639(이진 트리), 6597(트리)

https://www.acmicpc.net/problem/9934 풀긴했는데 그닥 만족스럽지 못한 코드다. 이렇게 하는게 맞는건지... # -*- encoding: cp949 -*- import Queue def bfs(k): q = Queue.Queue() q.put([k,k/2]) while not q.empty(): p = q.get() temp = [] flag = False for e in p[:-1]: temp.append(e-p[-1]-1) temp.append(e+p[-1]+1) if e+p[-1]-1len(n)-1: flag = True print n[e], print if flag: return temp.append(p[-1]/2) q.put(temp) k=input() n = map(..

acmicpc.net 1967,1167(트리,DFS), 11725(트리,DFS), 1068(트리,DFS)

https://www.acmicpc.net/problem/1967 알면 간단하다. 어떤 한 점에서던지 가장 먼 노드의 거리를 구하면 그 노드는 가장 먼 두 점중 한 점이다. 그러니까 아무 점에서 시작해서 가장 먼 노드를 구한다. 그리고 그 노드에서 가장 먼 점의 거리를 구하면 그게 답이다. 아래 dfs함수에서 확인할수 있다. # -*- encoding: cp949 -*- def dfs(y): visited = [0 for i in xrange(10002)] s = [[y,0]] visited[y] = 1 max_weight,node = 0,1 while s: p = s.pop() if max_weight < p[1]: max_weight = p[1] node = p[0] for i in xrange(le..

acmicpc.net 1509,2079(DP, 팰린드롬), 13275(Manacher's Algorithm, 팰린드롬), 1990(소수,팰린드롬)

https://www.acmicpc.net/problem/1509, https://www.acmicpc.net/problem/2079 1. 글자들을 팰린드롬 이 가능한지 나눠준다. [x,y]범위에서 팰린드롬이 가능한지 설정해준다. 이것을 dp리스트에 저장해둔다. 2. 나눠진 팰린드롬을 나눈다. 이게 dp2리스트의 일이다. # -*- encoding: cp949 -*- import sys sys.setrecursionlimit(1000000) dp = [[0 for i in xrange(2502)] for j in xrange(2502)] dp2 = [0 for i in xrange(2502)] def divide(p): if p

2016-10-23 일요일 11:08 pm

오랜만에 중학교 친구들과 밥먹고 볼링을 치고 왔다. 코딩시험준비하랴 중간고사치르랴 할게 많아서잘 놀지를 않았는데... 사실 오늘도 밥만 먹고 가려고 했는데 볼링을 치자고 해서 치고 왔다.볼링을 치고나서도.. 역시 마음이 편하지가 않다. 취업을 하고나서야 진짜 마음편하게 놀수 있을것 같다.볼링을 칠땐 진짜 재밌게 쳤는데 끝나고나선 재밌었다. 내일부터 힘내자! 가 라기보다는 재밌긴 했지만 오늘오후를 날렸네.. 라는 생각이 든다. 역시 마음의 짐처럼 뭔가 있으면 마음편히 못노는 스타일인것같다. 지금은 누군가 공짜 비행기 티켓을 주고 여행을 가라고 해도 못 갈것 같다. 근데 또 이런생각을 하면서 인간관계도 중요한데.. 그리고 집에 있었어도 많이 하지 못했다는 생각을 하는걸 보면 나가서 놀았던게 괜찮았던것같기도하..

Manacher's Algorithm

참조 1 : http://blog.naver.com/jyuno426/220794422838 참조 2 : https://algospot.com/wiki/read/Manacher's_algorithm 회문에 관한 알고리즘이라고 한다. 각 문자를 중심으로 하는 팰린드롬을 알아내는 알고리즘이라고 함. 각 문자를 중심으로하기때문에 짝수 길이의 팰린드롬은 찾을수 없다고 한다. 찾으려면 더미 문자를 끼워넣어서 a#b#c#d#d#c#b#a 꼴로 만들면 된다고 한다. ex) aaa의 중심은 중간의 a이고, 팰린드롬은 a와 aaa두개가 있다. aabaa의 중심은 b이고 팰린드롬은 b, aba, aabaa가 있다고 한다. 알고리즘 부분은 알고스팟에서 그대로 가져왔다.알고리즘은 다음과 같다:i는 0부터 n−1(n=|S|)까지..

algorithm/theory 2016.10.23

2016-10-21 금요일 4:21pm

전에 어딘가에 적었는지 모르겠는데 난 한가지에 빠지면 그것에만 집중한다. 취미뿐만이 아니라지금 해야될것이라고 생각되면 그것에만 몰두하는데... 지금 몰두하는것은 당연하게도 취준이다. 원래 뭔가를 미리미리 빨리빨리준비하거나 끝내버리는 편이라 학교를 졸업하지도 않았는데 벌써 마음이불안하다. 어쩌다 친구이외에 사람들을 만나서 이야기를 하면 졸업도 안했으니 그래도 괜찮다, 등의위로를 하는데 위로받고 안심되는 마음을 갖는건 왠지 현재 가지고 있는 취준에 대한 강한 의지를 약화시키게 될까봐 귀담아 듣지는 않는다. 만약 상황이 악화되어도 위로받아서 마음이 약해지는건 그 상황에 대한 변명이 될것같아서 위로라는걸잘 귀담아 듣는 편은 아니다. 위로받을것을 알면서 취준에 대해 이야기하는건 어떻게 보면 내 자신에 대한의지를 ..

acmicpc.net 11057(DP), 1937(DP), 10942(DP,팰린드롬)

https://www.acmicpc.net/problem/11057 기초 dp # -*- encoding: cp949 -*- n=input() dp = [[0 for i in xrange(10)] for i in xrange(1020)] for i in xrange(10): dp[0][i] = 1 for i in xrange(1,n+1): for j in xrange(10): for k in xrange(j,10): dp[i][j] += (dp[i-1][k]%10007) dp[i][j] %= 10007 print dp[n][0]https://www.acmicpc.net/problem/1937 bfs같이 보였었는데 bfs를 쓰면 시간초과난다. 첫 코드는 대나무의 크기 순서대로 정렬한 후 크기 순서대로 방문..

acmicpc.net 2573(BFS), 11967(BFS), 9328(BFS)

https://www.acmicpc.net/problem/2573 파이썬으로 코딩하니 시간초과가 나서 C++로 바꿨더니 됬다. 망할. #include #include using namespace std; int n,m; int _count; int _y[] = {1,0,-1,0}; int _x[] = {0,-1,0,1}; int temp_arr[301][301]; void bfs(int y, int x) { int visited[301][301]={0,}; queue q; q.push(make_pair(y,x)); while(!q.empty()) { int p0 = q.front().first; int p1 = q.front().second; q.pop(); for(int i=0;in-1 || tx>m-..

acmicpc.net 10868(세그먼트 트리), 2357(세그먼트 트리), 2268(세그먼트 트리)

https://www.acmicpc.net/problem/10868 http://qkqhxla1.tistory.com/734 의 세그먼트트리를 조금 변경한다. #include #include #include #include using namespace std; long long init(vector &a, vector &tree, int node, int start, int end) { if (start == end) { return tree[node] = a[start]; } else { return tree[node] = min(init(a, tree, node*2, start, (start+end)/2), init(a, tree, node*2+1, (start+end)/2+1, end)); } } ..

세그먼트 트리.

https://www.acmicpc.net/blog/view/9 의 내용을 정리해왔습니다. 예로 길이 N의 배열 A가 있고 여기서 L~R구간의 합을 M번 구해서 출력해야한다고 가정합시다. 수행해야 하는 연산의 시간복잡도는 O(M(R-L)) 번입니다. 그런데 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀어서 시간복잡도를 줄일수 있습니다. S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지 합은 S[j] - S[i-1]라고 할수 있습니다. 만약 A배열의 중간에 어떤 값이 하나 바뀐다고 하면 S[i]값은 A배열의 처음부터 다시 세서 만들어줘야 합니다. 따라서 M과 중간의 값이 변경되는 양이 너무 크게 되면 시간이 너무 오래걸리게 됩니다. (O(M*변경되는양)의 시간복잡도가 걸리겠죠...

algorithm/theory 2016.10.11

acmicpc.net 10827, 11060(DP), 1699(DP)

https://www.acmicpc.net/problem/10827 a^b를 어떻게 정확하게 구현할수 있을까? 소숫점을 없애고 큰 수 상태로 곱셈을 한다. 그 이후에 문자열로 만들어서 소수점 처리를 해주면 된다. # -*- encoding: cp949 -*- a,b=raw_input().split() p = len(a[a.index('.')+1:]) a = a.replace('.','') result = str(int(a)**int(b)) p=str((10**p)**int(b)) index = len(result)-len(p)+1 if index >=0: print result[:index]+'.'+result[index:] else: print '0.'+'0'*(-index)+resulthttps://..

최소 비용 최대 유량(MCMF)

http://kks227.blog.me/220810623254 에서 가져와서 핵심만 정리했습니다. 어떤 그래프에서 유량을 흘리는데 최대 유량을 흘리고자 합니다. 그런데 최소한의 비용을 들여서 흘리는게 목적입니다. 비용은 간선마다 다르며, 어떤 간선의 비용이 d이고, 유량이 f만큼 흐른다고 하면 비용은 d*f입니다.(d*k라고 나와있는데 오타인 듯..) 예로 위에서 빨간색으로 유량이 흐른다고 할때 비용은 17입니다. 방법론 : 포드 폴커슨, 에드몬드 카프 알고리즘과 비슷한데 매번 찾는 경로가 최단 경로입니다. 매번 최단 경로를 찾고, 이 경로로 흐를수 있는 최대 유량을 흘려보내면서 경로값*유량을 더해주면 된다네요.(위의 d*f를 말하는듯) 주의점 : 음의 가중치가 있는 그래프에서도 잘 작동해야 함. 역방향..

algorithm/theory 2016.10.08

Minimum cut

http://kks227.blog.me/220796029558 에서 핵심만 가져와 정리해왔습니다. 이 그래프에서 a와 e를 분리시키고 싶다고 합시다. 자르는 방법은 여러가지가 될 수 있지만 아래처럼 자를수 있습니다.이처럼 자르면 A,B,C와 D,E로 분리됩니다. 이렇게 그래프를 자르는걸 컷이라고 한답니다. 컷에는 비용이 있는데 위처럼 자르면 선이 3개가 잘리므로 비용이 3입니다. A바로 오른쪽에서 자르면 비용이 2로 A와 E를 분리시킬수 있겠네요. 이렇게 임의의 두 정점을 정하고, 두 정점을 다른 컴포넌트로 분리시키는 비용을 최소화하는걸 미니멈 컷이라고 한답니다. 이처럼 가중치가 있는 그래프라면 단순히 선을 조금 자르는것보다 비용을 생각해서 자르는게 효율적입니다. 이렇게 자르면 비용이 9로 A와 E를 자..

algorithm/theory 2016.10.07

acmicpc.net 피보나치 관련.

문제 카테고리 : https://www.acmicpc.net/problemset/?search=%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98 읽어볼것 : https://www.acmicpc.net/blog/view/28 몰랐던 코드. https://www.acmicpc.net/problem/2749 , https://www.acmicpc.net/problem/11444 를 풀기위한 코드. 행렬을 사용해서 하는거라함. n번째 피보나치 수를 구하는 코드. mod = 1000000 def gob(a,b): c = [[0,0],[0,0]] for i in xrange(2): for j in xrange(2): for k in xrange(2): c[i][j] += a[i][k] * b[k][..

2016-10-04 화요일 11:15 pm

감기가 걸렸다. 코딩할게 너무 많은데 집중력이 떨어진다. 다행히도 여태까지 진짜 부지런히 한게 다행이다. 8,9월동안 백준 알고리즘 600문제를 풀었다. 650문제를 풀었는데 700문제 좀더 넘게 풀어서 랭킹 100위 안에 들면 속도좀 늦추고 다른거 해야겠다. 미드 덱스터를 보는데 갑자기 뭔가 소름이 돋았다. 덱스터는 연쇄살인마이다. 결혼했는데 아내도 자식들도 다 그가 연쇄살인마인걸 모른다. 덱스터는 감정이 없어서 결혼했음에도 가족들을 그렇게 막 챙기는것 같지 않다. 처음에 아내인 리타를 만난것도 진짜 좋아해서가 아니라 일반사람처럼 위장하기 위해서였다. 지금 시즌쯤 와서는 좋아하는것 같지만 아직 본인의 일이 더 중요하다.(또다른 연쇄살인마를 살인하는것.) 시즌 3이 끝났는데 이번 시즌에서 결국 가족을 잘..

acmicpc.net 9151,9252(LCS), 11758(CCW), 11437(LCA)

https://www.acmicpc.net/problem/9251, https://www.acmicpc.net/problem/9252 LCS 란 어떤 두 문자열의 '모든 부분 수열' 중에서 가장 긴 길이를 말한다. 앞에서 했던 suffix automaton과 비슷한거 같지만 suffix automaton은 접미사가 같은 것들중 가장 긴것을 구하는거고 (즉 연속해서 나와야 한다.) 이건 연속해서 나오지 않아도 된다. http://blog.naver.com/power2845/220677085876 참고. 아래는 9252번 소스. 9151은 r[0]만 출력. def LCS(a,b): ret = [] LCS_length = 0 s1='0'+a s2='0'+b table = [[0 for i in xrange(l..

next_permutations, prev_permutation, k permutations

https://www.huangwenchao.com.cn/2015/05/python-permutation.html 쓸일이 많을것같아서 저장. 파이썬의 itertools모듈에 permutations가 있지만 다음거 구하는게 없이 전부 다 구하는거다. 종종 다음 permutations가 필요할 때가 있는데 그때를 위해 저장. # -*- encoding: cp949 -*- def next_permutation(a): if len(a) = 0 and a[i] >= a[i+1]: i -= 1 if i = a[k]: k -= 1 (a[i], a[k..