ClOr

닫는 괄호가 올바른 여는 괄호를 만나는 조건 닫는 괄호의 왼쪽에 있어야 함 아직 짝이 맞지 않아야 함 1,2를 만족하며 가장 오른쪽에 있는 괄호여야 함 시간 복잡도 시간 복잡도 : O($n^2$) 여는 괄호는 그냥 넘어가기에 : O($1$) 닫는 괄호를 찾을 경우에는 운 좋으면 한 번에 할수도 있지만 왼쪽에 있는 모든 괄호를 살펴봐야 함 : O($n$) 총 괄호의 문자열의 길이는 n이기 때문에 지금 이 방법은 O($n^2$)이 된다. 스택을 이용한 풀이 여는 괄호는 스택에 push 하고 닫는 괄호가 나오면 스택에 있는 여는 괄호 하나를 pop한다. 입력 : ( ( ) ) ( ) ) 일 경우 입력 끝 : ( ( ) ) ( ) ) 닫는 괄호가 마지막에 입력되었지만 스택이 비어있으므로 올바르지 않은 괄호가 된다.

[Silver IV] 참외밭 - 2477 문제 링크 성능 요약 메모리: 12864 KB, 시간: 108 ms 분류 애드 혹(ad_hoc), 기하학(geometry), 구현(implementation) 문제 설명 시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다. 1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양..

[Bronze I] 부녀회장이 될테야 - 2775 문제 링크 성능 요약 메모리: 13092 KB, 시간: 132 ms 분류 구현(implementation), 수학(math) 문제 설명 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는..

[Silver V] 좌표 정렬하기 - 11650 문제 링크 성능 요약 메모리: 74576 KB, 시간: 788 ms 분류 정렬(sorting) 문제 설명 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 알고리즘 과정 문제를 설명하기에 앞서...이 문제를 풀기에는 나는 너무 무력하고 아는 것이 ..

[Silver V] 수 정렬하기 2 - 2751 문제 링크 성능 요약 메모리: 324776 KB, 시간: 2580 ms 분류 정렬(sorting) 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 알고리즘 과정 이 문제는 단순하게 Arrays.sort()를 사용하면 시간복잡도가 $O(n^2)$가 걸리게 되는 저격 데이터가 있다고 다른 블로그에서 보았다. 그래서 이번에는 Collect..

[Bronze I] 수 정렬하기 - 2750 문제 링크 성능 요약 메모리: 18568 KB, 시간: 228 ms 분류 구현(implementation), 정렬(sorting) 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 알고리즘 과정 이번 문제의 배열을 정렬할 때 Arrays.sort()를 사용했다. Arrays.sort()의 시간복잡도는 평균 : $O(nlog(n))$을 가지고 최악의 경우 ..

[Bronze III] 택시 기하학 - 3053 문제 링크 성능 요약 메모리: 14516 KB, 시간: 124 ms 분류 기하학(geometry), 수학(math) 문제 설명 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |y1-y2| 두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다. 따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다. 원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합 반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓..

[Silver IV] 터렛 - 1002 문제 링크 성능 요약 메모리: 14384 KB, 시간: 160 ms 분류 기하학(geometry), 수학(math) 문제 설명 조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오. 입력 첫째 ..