Search

'알고리즘/acmicpc'에 해당되는 글 61건

  1. 2015.07.06 7578
  2. 2015.07.01 1753
  3. 2015.07.01 1795
  4. 2015.06.27 1197
  5. 2015.06.26 2268
  6. 2015.06.25 2357
  7. 2015.06.25 1138
  8. 2015.06.18 4158
  9. 2015.06.18 4883 (1)
  10. 2015.06.18 1890
  11. 2015.03.29 1976
  12. 2015.03.01 1199
  13. 2015.02.28 4256
  14. 2015.02.28 2156
  15. 2015.02.28 10159
  16. 2015.02.26 9489
  17. 2015.02.26 2517
  18. 2015.02.25 2568
  19. 2015.02.22 2109
  20. 2015.02.22 1914
  21. 2015.02.21 9463
  22. 2015.02.21 2776
  23. 2015.02.17 2631
  24. 2015.02.17 1958
  25. 2015.02.17 9252
  26. 2015.02.17 9251
  27. 2015.02.15 2599
  28. 2015.02.15 2436
  29. 2015.02.14 2533
  30. 2015.02.14 2469

7578

알고리즘/acmicpc 2015. 7. 6. 18:15 Posted by 아는 개발자

문제를 푸는것 자체는 별로 어렵지 않았다. 


부분합 문제를 변형한 형태이기 때문에 그 점을 잘 파악해서 풀면 된다. 가장 왼쪽에 있는 기기 부터 전선을 하나씩 이어가며 교차점의 수를 늘려간다.


교차점의 수를 찾는 방법은 가장 오른쪽으로 떨어진 지점까지 현결된 전선의 개수와 현재의 위치에서 기계와 연결된 지점 까지의 전선 개수를 빼면 된다. 


가장 오른쪽으로 떨어진 점 까지의 연결된 전선의 개수는 교차 가능성이 있는 전선들이고 연결된 지점의 왼쪽에 있는 전선의 개수는 교차 가능성이 없는 전선들이기 때문에 둘의 차는 해당 지점에서 전선을 연결 했을 때 교점과 같다.




알고리즘은 쉽게 생각했는데 내가 틀렸던 이유는 교차점의 수가 int의 범위를 넘을 수 있다는 것을 생각하지 못했기 때문이다... 이미 틀려버린 3 문제가 정말 억울하다...


교차점은 0+1+2+...+499999까지 생기는데 이러면 int범위를 거뜬히 넘어버린다

앞으로 결과의 자료형은 왠만하면 long long을 사용해야겠다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2458  (0) 2015.07.15
1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27

1753

알고리즘/acmicpc 2015. 7. 1. 19:41 Posted by 아는 개발자

너무나 당연하게 알고있을 거라 생각했던 다익스트라....

나는 다익스트라 알고리즘이 우선순위을 사용해야 한다는 것을 깜빡하고 있었다.


이 문제는 맨 처음에는 메모리 초과를 어떻게 해결할 것이냐로 속을 썩였었는데

메모리 초과를 해결 한 후에는 나의 다익스트라 알고리즘의 문제때문에 한동안 애를 먹었다..


먼저 메모리 초과를 해결하는 방법부터 설명하면


정점의 개수가 20000개이기 때문에 20000*20000의 배열은 만들 수 없다.

그러므로 간선들만의 집합을 만들어두어야 한다.


이때 특정 정점에서 나오는 간선을 어떻게 indexing하느냐 문제가 있었는데

각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다.

(지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다...)


이제 그에 맞추어서 다익스트라를 적용하면 되는데


나는 너무도 당연하게 다익스트라를 큐를 이용해서 구현하면 될 줄 알았다...

하지만 다익스트라는 우선순위 큐를 이용해서 구현해야 한다.


그 이유는 연결된 노드들 중에서 가장 가까운 점과 연결되어야 하는데 이때 나중에 추가된 점이 먼저 추가된 점보다 더 가까이 있는 경우가 생기기 때문이다.

(설명이 그지같으니 혹시나 이글을 보시는 분은 반드시 책을 참조하시길)


맨날 다익스트라 다익스트라 떠들고다녀서 나 스스로 잘 알고 있을 줄 알았는데

오늘 알고리즘 책을 보고 다시 깨달았다.


역시나 잘 알고 있다고 방심하는 순간 틀리는 것 같다.


겸손해야지


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26

1795

알고리즘/acmicpc 2015. 7. 1. 16:13 Posted by 아는 개발자

이 문제는 딱 보면 어떻게 해결해야 할지 감이 안잡히는데

그래프를 사용하라 하면 어느정도 문제푸는 방법을 깨닫는다


이 문제에서 힌트는 암호들이 정렬되어 있다는 것이다.

사용하는 문자들의 알파벳 정렬을 그래프의 간선으로 설정해서 표현하고

DFS를 통해서 풀면 된다.


기존 DFS랑 다른 점은 한 번 방문한 점을 또 방문 할 수 있다는 점인데

그 노드에서 빠져 나올 때 방문하지 않은 걸로 바꾸면 풀 수 있다.




728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25

1197

알고리즘/acmicpc 2015. 6. 27. 10:53 Posted by 아는 개발자

반성해야하는 문제다

너무 문제에 성급하게 접근했다.


최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다.

나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다.


이것은 union find라는 자료구조를 이용해서 해결해야하는데


나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다.

(아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..)


프림알고리즘을 사용했으면 틀리지 않았을 것 같다...



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25

2268

알고리즘/acmicpc 2015. 6. 26. 11:54 Posted by 아는 개발자

집가기 전에 하나 풀고 가겠다고 성급하게 덤볐다가 쓸데없이 두 번 틀린 문제다.


펜윅트리를 다시 정의해서 풀면 된다.


update를 이전 값에서 차이값을 갱신해주면 된다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18

2357

알고리즘/acmicpc 2015. 6. 25. 16:10 Posted by 아는 개발자

각 구간별로 최소값과 최대값을 구하는 문제


가장 쉽게 생각하면 매번 구간이 주어질 때마다 최대값과 최소값을 구하는 방법이 있겠으나

그렇게 쉽게 문제를 냈을 리가 없다.


방법은 Min Max Tree를 만드는 것이다


옛날 자료구조 시간에 Tree의 존재를 배우기는 했으나 직접 구현하지는 않아봐서

이번에 구현하는데 시간이 좀 걸렸고,,,


구간 부분을 지정해주는 것도 꽤 힘들었다.

(이거 진짜 귀찮은 작업이다...)


하지만 한번에 맞춰서 기분이 좋다


나의 미천한 코딩실력도 조금씩 상승하는 것 같은 느낌이다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18

1138

알고리즘/acmicpc 2015. 6. 25. 14:03 Posted by 아는 개발자

이 문제는 줄을 모두 비운 다음 입력에 따라서 하나씩 채워가면 된다.


예제로 나온 것을 보자


2 1 1 0


-1을 비어있는 것으로 보고 줄을 만들어보면


-1, -1, -1, -1


먼저 1의 크기를 가진 참가자는 자신의 앞에 두명이 있어야 한다.

그런데 다음으로 검사할 참가자들은 모두 1보다 키가 클 것이므로

앞에 두명을 비운 다음에 자신의 위치를 잡아 줄 수 있다.


-1, -1, 1, -1


다음 2의 크기를 가진 참가자는 자신 앞에 한명이 있어야 한다.

앞의 경우와 마찬가지로 다음으로 검사할 참가자들은 모두 2보다 키가 크기 때문에

3이 올지 4가 올지 생각하지 않고 그냥 앞에 한 칸을 비우면 된다


-1, 2, 1, -1


핵심은 키의 순서대로 적용하고 있다는 것이고 

그 숫자만큼 빈칸을 만들어 두면 된다는 것이다.


처음에는 이 문제를 풀 때 무식하게 접근했는데

잘 생각해보니 쉽게 풀렸던 것 같다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18

4158

알고리즘/acmicpc 2015. 6. 18. 16:41 Posted by 아는 개발자

속도를 어떻게 높일 것인가에 대한 문제인데


문제에서 힌트로 주어지는 CD 넘버가 오름차순을 띤다고 했다.


가장 일반적으로 생각할 수 있는 방법은 트리 구조임을 이용해 O(nlogn)시간 내에 푸는 방법이 있을 수 있지만


상근이와 선영이의 CD로 주어지는 넘버 모두 오름차순을 띈다는 점을 이용해

O(N)시간에 해결 할 수 있다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29

4883

알고리즘/acmicpc 2015. 6. 18. 16:10 Posted by 아는 개발자

삼각그래프


알고리즘 문제를 풀 때 가장 기본적인 태도는


1. 먼저 문제를 잘 읽는다


2. 문제를 의심한다


여기선 문제를 잘 읽기는 했는데 문제를 의심하는 단계가 부족했다.


입력으로 비용의 제곱은 1000000보다 작다고 했는데 그렇다면 비용은 음수가 들어올 수도 있다는 이야기...


하지만 나는 그걸 몰랐고 쓸데 없이 틀렸다.


그런데 이런건 좀 친절히 설명해줘야 하는거 아닌가 ㅡㅡ



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
  1. 류현준 2016.12.15 15:29  댓글주소  수정/삭제  댓글쓰기

    좀 하시네요 ㅋㅋ

1890

알고리즘/acmicpc 2015. 6. 18. 11:21 Posted by 아는 개발자

도착 할 경로가 몇개나 있는지 묻는 문제이다.


도착 할 좌표의 경로를 찾는데 집중 하기 보다는


각 좌표까지 이동 할 수 있는 경우의 수들을 모두 계산 한 후


마지막에 도착 지점의 경우의 수를 구해주면 풀기 쉽다.




여기서 도착할 경로의 범위가 2^63 까지 된다고 했는데

unsinged long long을 위 범위를 표현할 수 있다

printf로 표현하는 방법은 "%llu%이다.

방학도 끝났으니 분발해야겠다.


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
4256  (0) 2015.02.28

1976

알고리즘/acmicpc 2015. 3. 29. 16:16 Posted by 아는 개발자

딱 보면 알고리즘에 배운 Floyd Warshall로 해결 할 수 있을 것 같지만

Floyd Warshall 알고리즘은 나중에 한 값이 이전에 한 값에 영향을 줄 수 있는 문제점이 있다.


즉 나중에 연결 한 선이 이전에 연결한 선까지 변경 할 수 있다는 말이다(말이 좀 어렵다. 그림으로 표현하면 쉬울것 같은데 그림 그리자니 그건 귀찮고)


그래서 내가 10달전에 제출해보았던 코드들은 대부분 Floyd 알고리즘을 썼더니 모두 틀렸다.


새롭게 생각해낸 방법은 다익스트라 알고리즘을 이용한 방식이다.


한 점을 루트 로 잡고 그 점으로 부터 bfs 탐색을 한다

여기서 bfs로 거쳐가는 노드들은 모두 루트로부터 연결이 가능한 노드들이다.


난 좀 무식하게 해서 모든 점을 루트로 잡아서 연결을 했다.


그러면 이건 나중에 연결한 선이 이전의 결과에 영향을 주지 않느냐고 반문 할 수 도 있다


하지만 아무리 새롭게 루트를 잡아도 이전에 연결된 트리구조에서 더이상 확장 되지 않기 때문에 새로운 노드를 발생할 가능성은 없다.


알고리즘은 역시 말로 설명할 수 없다. 그림 설명이 최고다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
4256  (0) 2015.02.28
2156  (0) 2015.02.28

1199

알고리즘/acmicpc 2015. 3. 1. 17:50 Posted by 아는 개발자

문제가 좀 불친절 한 것 같다. 


여기서 입력이 핵심인데 두 정점 사이에 간선이 여러개 있을 수 있다고 한다. 그런데 간선이 여러개 있는 것을 어떻게 표현할 것인가에 대한 설명은 없다. 


그래서 나는 주어진 간선 이차원 배열에서 입력받는 정수가 두 정점 사이의 간선의 개수라 생각하고 문제를 풀었다.


나머지는 오일러 회로 문제라 생각하면 된다. 오일러 회로의 성립 요건은


모든 정점의 인접한 간선의 수가 짝수여야 한다는것 이걸로 오일러 회로가 성립 하지 않는 경우에 대해서 -1을 출력했고


성립하는 경우 정점 출력 순서는 주위의 간선이 존재하지 않는 것으로 stack을 이용했다.


여기서 속도 문제가 있었는데

그거는 각 노드마다 자신과 인접한 노드를 queue로 저장해서 관리하는 방법으로 해결했다.

그러면 매번 각 노드와 인접한지 아닌지 찾을 필요가 없다.


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
4256  (0) 2015.02.28
2156  (0) 2015.02.28
10159  (0) 2015.02.28

4256

알고리즘/acmicpc 2015. 2. 28. 19:40 Posted by 아는 개발자

전위탐색에서의 값을 중위탐색에서 찾으면 그것의 왼쪽에 있는 것들은 left child, 오른쪽에 있는 것들은 right child이다. 이 성질을 이용해서 풀면 쉽게 풀수있다.


재귀함수를 이용해 좀 더 깔끔히 푸는 방식이 있으나 나는 규칙성과 stack을 같이 응용해 풀었다.




728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1976  (0) 2015.03.29
1199  (0) 2015.03.01
4256  (0) 2015.02.28
2156  (0) 2015.02.28
10159  (0) 2015.02.28
9489  (0) 2015.02.26

2156

알고리즘/acmicpc 2015. 2. 28. 18:23 Posted by 아는 개발자

바로 전 문제 dp를 쉽게 풀어서 이 문제 만만히 봤는데 4번맞에 맞았다;;

너무 내가 성급히 접근한것 같다. 경우의 수를 좀 철저히 따져봐야 했는데.


문제의 핵심은 연속 3잔은 마실 수 없다는 것이다.

그러면 경우의 수로 나눌 수 있는데


1 2 3 4 5 6 이렇게 포도주가 있으면


12 3 45 6 하나를 공백으로 두고 마시는 경우와

12 3 4 56 두개를 공백으로 두는 경우 그리고

1 2 3 4 5 6 하나씩 공백으로 두는 경우로 나눌 수 있다.


이 문제를 풀기위한 자료구조로 이차원 배열을 생각해냈다

d[][2] -> d[][0]는 현 위치에서 연속이 끝나는, d[][1]는 현 위치에서 연속이 시작하는


위의 모든 경우와 자료구조를 정의했으니 다음과 같은 점화식을 낼 수 있다.


d[here][0] -> w[here]+d[here-1][1] 

현위치에서 연속이 끝날때는 바로 전 위치에서 연속이 시작할 때의 값과 더하면 된다.


d[here][1] -> w[here] + max(d[here-2][1], d[here-3][0], d[here-2][0])


현 위치에서 연속이 시작하려면 세 가지 값과 비교해야하는데 바로 전전 위치에서 시작하는 경우와 끝나는 경우 바로 전전전 위치에서 끝나는 경우와 비교한다.


그러면 모든 경우를 포함하게된다.


dp문제는 내가 푸는 알고리즘이 모든 경우를 포함하는지와 중복되지 않는지를 확인하는것이 관건이다. 오늘은 모든 경우를 포함하지 못해서 자꾸 틀렸다;



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1199  (0) 2015.03.01
4256  (0) 2015.02.28
2156  (0) 2015.02.28
10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26

10159

알고리즘/acmicpc 2015. 2. 28. 13:54 Posted by 아는 개발자

처음에 이 문제를 읽을때 위상정렬을 써야하나 깊이 고민했는데

올림피아드 문제에서 대학생들이 공부하는 위상정렬을 여기서 쓰겟나 싶어서 간단히 접근한결과 무식하게 풀기를 생각해냈다.


이차원 배열을 선언하고 다음과 같이 정의한다.

judge[from][to] from과 to의 값을 비교 결과를 저장하는 배열이다. 

from< to이면 -1, from > to 이면 1, 알수 없으면 0으로 저장한다.


여기서 너무도 당연한 사실을 생각 할 수 있는데


from < to 이면


from과 from보다 작은 값들과, to와 to보다 높은 값들과 비교를 할 수 있다는 사실


그래서 난 from과 from보다 작은 값들을 loser라는 벡터에 두고

to와 to보다 높은 것들을 winner라는 벡터에 두어서

(judge[][]함수를 찾아다녔다)


각각 벡터 값으로 judge[][]를 재정의 해주는 방법을 택했다.


알고리즘의 시간 복잡도는 O(N*N)으로 좋지 않지만

문제에서 크기를 100으로 제한했기 때문에 시간내에는 충분히 풀 수 있는 문제.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

4256  (0) 2015.02.28
2156  (0) 2015.02.28
10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25

9489

알고리즘/acmicpc 2015. 2. 26. 23:35 Posted by 아는 개발자

예전에는 왜 이렇게 많이 틀렸을까 보니...


입력이 1 2로 시작하는 경우를 생각 안해서 그런것 같다

이런 경우는 트리가 두개 생길 수 있는데 나는 그냥 하나의 트리로 놓고 문제를 풀었으니

틀릴수밖에...


조금은 불친절한 문제인것 같다, 이런 경우도 있다는걸 알려줘도 무방 할 것 같은데


뭐 이런것도 실력이니까;

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2156  (0) 2015.02.28
10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22

2517

알고리즘/acmicpc 2015. 2. 26. 21:54 Posted by 아는 개발자

처음에 바로 BIT로 풀어야지 했다가 

정수의 범위가 1000000000까지인걸 단순히 BIT로 접근해선 안되겠음을 깨달았다.


이전까지 탐색한 정보들을 Heap에 넣어둘까 하다가 최악의 경우가 O(n*n)이라 별 소용이 없음을 생각하고 다른 방법을 강구...


그러다가 어차피 선수의 수가 500000이하니까 1~1000000000을 1~500000로 좁히는 방법을 생각했다.


방법은 1~1000000000의 data들을 정렬해서 그 data의 index값을 BIT에 쓰는 방법이다.

해당 index 값을 찾는 과정은 이진 탐색이니까 O(log(500000))으로 확 준다.


그러면 BIT에 index값까지의 합을 확인하고 현재까지 탐색한 선수의 수를 빼주고

그 index에 1만큼 update한다. 이 과정은 O(logN)


시간복잡도를 O(NlogN)으로 줄일 수 있었다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22

2568

알고리즘/acmicpc 2015. 2. 25. 13:33 Posted by 아는 개발자

초등부의 전깃줄 문제에서 한발 나아간 문제.

기본적으로 LIS를 이용해서 풀 수 있는 것은 똑같지만 Input의 개수가 1000배이상 증가해서

O(N*N) 기본탐색 알고리즘을 사용하면 시간초과가 날게 틀림없으므로

좀 더 효율적인 자료구조를 활용해 속도를 높일 필요가 있었다.


나는 priority queue를 이용해서 풀었는데

priority queue는 이전 까지 탐색했던 line중에서 LIS값이 높은 순위로 저장되어있다.

priority queue는 pair<int, int>로 이루어져 있는데 pq가 pair.first를 통해서 정렬한다는 점을 알면 구현하기 편리하다


d값, value값, idx값 총 세가지 값이 필요한데 나는 pair.second로 idx값을 넣어서 value값은 넣지 않고 idx값을 통해서 참조 할 수 있게 만들었다.




728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21

2109

알고리즘/acmicpc 2015. 2. 22. 16:09 Posted by 아는 개발자

처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡ

QnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다.


이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다


그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면

정답으로 20을 출력해야한다.


어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다.


기간내에 강연 할 수 있는 빈 시간이 있다면

강연을 하고


이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음

하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다.


생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.

최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)을 사용하면 

시간초과가 뜬다.


1. 그래서 나는 먼저 강연들을 기간으로 오름차순 정렬한 다음


2. 그 기간내에 강연이 몇개 있는 지는 BIT를 이용해서 구했고(사실 이거는 안해도 되는디)


3. 그 기간내의 강연 중 돈을 가장 조금 주는 강연은 priority queue를 통해서 구현했다.


오름차순으로 정렬했기 때문에 기본적으로 dp로 차근차근 증가시켜 나가면 된다.


#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>


using namespace std;


const int SUM_MAX = 100000001;

int size_tree[11111];


struct Node{

int d, p;

};


bool compare(Node a, Node b)

{

return a.d < b.d;

}


int read(int idx)

{

int sum = 0;

while(idx > 0)

{

sum += size_tree[idx];

idx -= idx&-idx;

}

return sum;

}


void update(int idx, int val)

{

while(idx <= 11111)

{

size_tree[idx] += val;

idx += idx&-idx;

}

}


Node coll[11111];

int d[11111];


int main()

{

int n, piv= 0;

scanf("%d", &n);


priority_queue<int> pq;


for(int i = 1; i <= n; i++)

{

scanf("%d %d", &coll[i].p, &coll[i].d);

}

sort(coll+1, coll+n+1, compare);


for(int i=1;i<=n;i++)

{

if(read(coll[i].d) < coll[i].d)

{

piv++;

update(piv, 1);

d[piv] += coll[i].p + d[piv-1];

pq.push(-coll[i].p);

}

else

{

if(abs(pq.top()) < coll[i].p)

{

d[piv] -= abs(pq.top());

d[piv] += coll[i].p;

pq.pop();

pq.push(-coll[i].p);

}

}

}


printf("%d\n", d[piv]);


return 0;

}


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21

1914

알고리즘/acmicpc 2015. 2. 22. 14:03 Posted by 아는 개발자

옛날에 못풀었던걸 풀면 기분이 상쾌한데 이번꺼는 뭔가 찜찜하다... 왜 예전에는 못풀었지?


내 예전 코드들은 스택을 통해서 위치를 찾아가는 방법이었다.

재귀함수를 쓴 현재 코드 보다는 훨씬 속도가 빠를 것 같은데

시간초과가 난 원인은 역시 printf와 cout의 차이인듯 하다..


또 2^100을 해결하는 문제가 있었는데

이거는 long long 두개를 써서 해결할수 있었다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17

9463

알고리즘/acmicpc 2015. 2. 21. 23:39 Posted by 아는 개발자

자력으로 해결하지 못했다. 다른사람이 푼 해설지 보고 어찌어찌 풀었는데

음... 시간 문제는 BIT를 이용해서 해결하는 거로 하고 여기서 명심해야할 거는

간선의 개수를 구하는 방법인데... 놀라웠다.


지금까지 나는 기를 쓰고 어케 풀어볼려고 생각했는데

간단히 현재까지의 간선의 개수 - 연결된 간선의 위치 까지의 간선수로 한번에 해결


음 그니까


read(N) - read(v[i].second)라는 코드로 한번에 해결했다.


왜 나는 이런게 떠오르지 않을까


지금 생각해보면 정말 간단한 원리인데 원래 N*N에 얽매여서 자력으로 해결하지 못하고ㅠ


또 신기한거는 시간차인데


출력형식이 시간에 영향을 많이 준다.

그런데 int보다는 long long이 출력할 때 빠르다.


printf("%d") 로 출력하면 시간초과가 뜨는데

printf("%lld")로 출력하면 시간 내에 들어온다.

출력 형식이 중요하긴 하나 보다. 다른 사람들도 모두 이렇게 출력하고 있다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17

2776

알고리즘/acmicpc 2015. 2. 21. 21:45 Posted by 아는 개발자

암기왕 문제..

예상외로 쉽게 풀릴수 있는 문제인데 괜히 어렵게 풀었다.

속도도 내 알고리즘이 더 빠를 줄 알았는데 오히려 더 느렸고 메모리도 더 많이 잡아먹고..

모두 한꺼번에 모아서 sort함수 때리고 앞의꺼랑 뒤에꺼가 같으면 ok라 놓고 풀었는데

계속 오답이 나왔다..


오답의 원인을 찾으니까 내 알고리즘은 검사를 두 번 실시하면 안에있는 거로 간주하는 문제가 있었다.. 아 진짜 이런 찐따가 따로없다..


binary_search라는 stl이 있어서 빠르게 해결 할 수 있었다... 이런거는 빨리 알아야 하는데

아 그리고 왠만하면 cin, cout을 쓰지 말고 #include<cstdio>에서 printf, scanf를 사용하는 습관을 들여야 겠다. cin, cout이 5배나 더 느리다니... 이것도 cin, cout 썼으면 분명 시간초과 떴을꺼다 ㄷㄷ


이 글 거의 읽는 사람은 내가 무슨 말 하는지 모를거다. 나도 다시 읽으면 모르겠다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17

2631

알고리즘/acmicpc 2015. 2. 17. 19:13 Posted by 아는 개발자

알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면

문제풀기가 편하다.

줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지

사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.

옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.

아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17

1958

알고리즘/acmicpc 2015. 2. 17. 18:38 Posted by 아는 개발자

세개의 문자에 대해서 LCS를 찾는것

d[][][] 3차원배열을 만들고 점화식은 같다

사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다

하지만 LCS 문제를 푸는데 착안해서 풀었다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15

9252

알고리즘/acmicpc 2015. 2. 17. 18:09 Posted by 아는 개발자

LCS 살짝 변형한 문제다

문자열에대한 dp[][]배열을 만들어주면 된다.


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15

9251

알고리즘/acmicpc 2015. 2. 17. 17:18 Posted by 아는 개발자

LCS문제

모두의 부부수열이 되는 수열중 가장긴것을 찾는문제

전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요

점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.

현재 위치의 dp값을 지정해주려면


if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

else dp[i][j] = max(dp[i][j-1], dp[i-1][j])


요렇게

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14

2599

알고리즘/acmicpc 2015. 2. 15. 23:35 Posted by 아는 개발자

이런문제는 틀리면 안된다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14

2436

알고리즘/acmicpc 2015. 2. 15. 23:27 Posted by 아는 개발자

공약수문제...

너무 소수를 구하는데 얽매여서 

에나로스의 체를 구해서 소수 만들고 하다보니 메모리 초과 뜨고 ㄷㄷㄷ

너무 소인수분해 하는데에 얽매여서 문제를 풀었던 것 같다.

좀 더 단순히 생각했어야 하는데 다른 사람이 푼 코드를 보니 아 이렇구나....


6, 180이 주어져있으면

180/6 = 30이 남는다

결국 30을 어떻게 쪼개느냐가 중요한건데

나는 30을 소인수 분해해서 2 3 5 를 어떻게 분해할 것인가로 문제를 풀었는데

다른사람은 아예 1~30까지 탐사해서 

각각의 경우에 최대 공약수가 원래의 값과 일치하는지를 보았다 ㄷㄷ


바보같이 쓸데 없느데 얽매이다보니 푸는게 너무 늦어졌다;;

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2533

알고리즘/acmicpc 2015. 2. 14. 17:05 Posted by 아는 개발자

다른 블로그 글을 읽고 도움을 받아서 풀긴했다.. 그런데..

dp로 문제를 푸는 전략 자체는 블로그 글과 나의 알고리즘은 같았는데

나는 왜 오답이고 블로그의 코드는 정답인건지.... 

아직 나의 코딩 스타일에 문제가 있는 것 같다. 재귀 함수를 이용해서 만드니까

지저분하고 속도도 오래 걸리고 블로그 글 처럼 최대한 간결하게 만들면 더 좋았을 텐데

dp문제는 기본적으로 배열을 이용해야 깔끔한 것 같다

int d[100001][2] 이런 식으로? 이중 배열이 속성을 의미하는 걸로 이해하자.


이 문제의 알고리즘은 다음과 같다

자신의 early adapter가 되는 경우는 자식이 early adapter인 경우나 자식이 early adapter가 아닌 경우 중 최소값이고

자신이 early adapter가 되지 않는 경우는 자식이 early adapter인 경우이다.


코드로 쓰면

d[v[now][i]][0] += d[now][1];

d[v[now][i]][1] += min(d[now][0], d[now][1]);

v[now][i]는 현재 위치에서 부모를 나타낸다.

(지금와서 다시생각해보니 부모만 찾아다니면 되는거였네;;)


블로그 코드에서 소름돋았던거는 degree를 이용해서 다음 큐에 들어갈 노드를 찾았던 거다

자료구조시간에 degree 공부했는데 이렇게 쓰일줄일야... 기본 개념이 중요한걸 다시 한 번 느꼈다..


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2469

알고리즘/acmicpc 2015. 2. 14. 13:48 Posted by 아는 개발자

사다리 문제는 간단하다

가로획이 있으면 둘의 위치가 바뀌는 성질만 이용하면 된다.

????가 나타나기 전까지는 ABCD에서 쭉 내려오고

그 이후로는 목표로 한 문자열을 가지고 아래에서 위로 올라간 후

서로 비교하면 된다.

현재 문자열과 목표 문자열의 위치 차이가 2 이상으로 나면 사다리로 만들 수 없으므로

xxxx를 출력하면된다.


문제만 생각하지 말고 사다리의 원리에 대해서 생각해보자

내가 어떻게 가로획을 긋더라도 사다리는 항상 일대일 대응을 이루는데

방금 위에서 설명한 사다리 가로획의 원리를 생각하면 이해하기 쉽다.

두 세로획의 자리를 바꾸는 것이기 때문에 내가 어떻게 자리를 바꾸더라도

1:1대응의 성질은 유지될 수 밖에 없다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14