본문 바로가기
[C++] 백준 10989번: 수 정렬하기3 이번 문제를 algoritm을 include하여 qsort 내장 함수를 이용하고자 하면 시간초과, 메모리초과가 발생한다. 입력되는 값의 개수가 무려 10,000,000개가 될 수 있기 때문이다. 어떻게 해야할지 감도 안 잡히다가, 질문 검색 탭에서 힌트를 얻었다. 카운팅 정렬을 이용하면 메모리 초과를 해결할 수 있다고 한다. 문제를 다시보니, 값의 최대값이 10,000으로 제한돼 있다. 카운팅 정렬에서는 각 값이 몇 번씩 등장했는지 세어준 다음에 값 * 카운트를 새로운 배열에 저장하여 인덱스로 활용한다. 하지만 여기서는 새로운 배열에 저장하려고 하다가는 메모리 초과가 뜨기 떄문에, 카운트만을 활용했다. 처음에 크기가 10,000인 int 배열을 선언한 후 각 값이 입력되면 바로바로 카운트했다. 이후, 카..
[C++] 백준 2798번: 블랙잭 이 문제의 제목을 봤을 때, 뭔가 어렵겠구나 라고 느꼈지만 생각보다 어렵지 않다. 풀이는 간단하다. 모든 경우를 싹 조사하면 된다. 경우의 수도 얼마 안 된다. N이 최대 100인 것을 고려했을 때 입력된 카드들 중 3장을 뽑아서 합을 구하는 모든 수는 조합에서 배웠다시피 100 * 99 * 98 = 970,200밖에 되지 않는다. 1GHz의 CPU에서 연산하는데 9ms밖에 걸리지 않는다. 각 합을 담을 배열도 용량이 크지 않다. 970,200 * 4(byte) = 3,880,800 byte ≒ 3.7 MB 밖에 되지 않는다. 그래서 마음놓고 for문을 3번 중첩하여 모든 경우를 계산하고 int count = 0; for (int i = 0; i < N - 2; i++) { for (int j = i +..
[C++] 백준 10250번: ACM 호텔 #include int main() { int T, H, W, N; scanf("%d", &T); while (T--) { scanf("%d %d %d", &H, &W, &N); for (int w = 1; w
[C++] 백준 1929번: 소수 구하기 이번 문제는 입력이 최대 1,000,000까지다. 연산량이 적지 않은 만큼 입력에서도 신경을 써야 한다. iostream을 이용할 경우 다음을 main 함수 아래에 추가하면 출력이 빨라진다. ios_base::sync_with_stdio(false) 하지만 나는 printf/scanf를 사용하는 것을 선호한다. 이 문제를 풀고자할 때 제일 먼저 떠올리는 해결 방법이 아래 1번 방법이다. 1. M부터 N까지의 각 수에 대해 검사 #include int main() { int M, N; scanf("%d %d", &M, &N); for (int i = M; i
[C++] 백준 9012번: 괄호 이번 문제에서는 주어진 문자열에서 괄호의 세트가 잘 맞춰져 있는가를 검증해야 한다. 즉, 닫힌 괄호로 시작하거나 열린 괄호로 끝나면 "NO"를 출력해야 한다. 그 외에도 닫힌 괄호가 충분하지 않거나 그 반대의 경우도 있겠다. 이런 경우를 하나하나 생각하기엔 복잡하니, 다음과 같이 생각을 간소화 할 있다. 열린괄호는 +1, 닫힌괄호는 -1로 생각하는거다. 처음에는 0으로 시작하여 문자열을 처음부터 스캔해 나간다. 만약 그 과정에서 음수가 되면 명백하게 "NO"다. 왜냐하면 닫힌 괄호가 앞에서 더 많이 나왔기 때문이다. "(()))"이런 경우다. 스캔이 다 끝나면 다시 0으로 돌아와야 한다. +1과 -1의 쌍이 하나씩 매칭되기 떄문이다. 만약 0이 아니면 "NO", 0이면 "YES"다. #include us..
[C++] 백준 2839번 : 설탕배달 입력의 첫 줄에서 배달해야 되는 설탕의 양 N 킬로그램이 주어진다. 설탕을 나눠 담을 수 있는 단위는 5 킬로그램과 3킬로그램으로 제한돼 있다. 여기서 더 적은 갯수의 봉지로 나눠 담아 가려면, 5 킬로그램 봉지의 비중을 최대한 많게 해야한다. #include using namespace std; int main() { int N; scanf("%d", &N); int A = 0; for (int i = 0; 5 * i
[C++] 백준 1654번: 탈출 조건에 대하여 #include using namespace std; int main() { int K, N; scanf("%d %d", &K, &N); int* LANs = new int[K]; long long MAX = 1; for (int i = 0; i MAX) MAX = LANs[i]; } long long MIN = 1; long long MID; while (MAX >= MIN) { MID = (MIN + MAX) / 2; long long P = 0; for (int i = 0; i < K; i++) { P += LANs[i] / MID; } if (P < N) { MAX = MID - 1; } else { MIN =..
[C++] 삼항연산자를 중첩해서 쓸 때 주의할 점 가령, 정수형 변수 A, B, C, D 중 최솟값을 출력하려는 경우 코드를 다음과 같이 작성할 수 있다. #include using namespace std; int main() { int A, B, C, D; scanf("%d %d %d %d", &A, &B, &C, &D); int min = A < B ? A : B; min = C < min ? C : (D < min ? D : min); printf("%d", min); return 0; } 얼핏보면 문제가 없어 보인다. 하지만 문제는 다음 코드에 있다. min = C < min ? C : (D < min ? D : min); D < C < min인 경우 위 코드의 결과는 아이러니하게도 C가 된다. 왜냐하면 C와 D의 비교가 이루어지지 않기 때문이..
[C++] HEAP_CORRUPTION_DETECTED HEAP_CORRUPTION_DETECTED: after Normal block (#78) at 0x00DE52F8. CRT detected that the application wrote to memory after end of heap buffer. 흔히 문자열을 다룰 때 종종 마주치는 에러다. 허용되지 않은 메모리 영역에 접근해서 나타나는 에러다. 위 에러는 다음과 같은 코드에서 발생할 수 있다. #include using namespace std; int main() { char* text = new char[10]; scanf("%s", text); delete[] text; return 0; } 위 코드에서 길이가 10 이상인 문자열이 입력되면 문제가 된다. 문자열의 끝에는 '\0'이라는 널문..
파이썬 공부 2주차 오늘은 주로 분기, 반복에 대해서 다뤘다. 분기는 if문, 반복은 while문. 또한 함수를 정의하고, 호출하는 방법에 대해 익혔다. 키보드의 입력을 받아 변수에 값으로 저장하는 방법을 배웠고, 다양한 변수의 타입이 있다는 것도 배웠다. Type(~)을 통해 특정 요소의 데이터 타입을 알아낼 수 있었다. 특히, 신기한 점은 Type(Type))을 통해 Type의 데이터 타입은 Type이라는 것을 알 수 있다는 것이다. 인터렉티브 모드에서 Alt+P를 통해 Previous의 입력을 불러올 수 있고, Alt+N을 통해 Next의 입력을 불러올 수 있다. 마지막으로는 흔한 예제! 삼각형 그리기! # -*- coding: euc-kr -*- def tri_width(): width = int(raw_input(..
파이썬 공부 1주차 소입설 수업 때 파이썬을 배우는데, 여기에 기록을 남기려고 한다. 첫 주차 수업에서는 파이썬을 설치하고, IDLE(IDE, 통합개발환경)을 실행시켰다. (파이썬 버전은 2.7을 사용한다.) 한 줄씩 입력하고 바로 출력 되는 CMD 방식을 Interactive mode라고 부른다. 또 출력해주는 애를 Interpreter라고 부른다. 명령어처럼 입력하는 한 줄을 statement라고 부른다. Ctrl+N을 누르면 새 창이 뜨며 문서편집과 같은 모드로 진입한다. 파이썬에서 한글을 출력하려면 다음을 코드 상단에 추가해야 한다. # -*- coding: euc-kr -*- 반복문 등에서 하위 코드를 묶기 위해 들여쓰기를 하는데, 그 때는 원하는 부분을 드래그(선택)한 상태로 Ctrl+[ 또는 ] 를 누르면 정렬..
[JAVA]로또 역대 당첨번호 통계 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127package imperfect; import java.net.HttpURLConnection;import java.net.URL;import java.util.regex.Matcher;import java.util.rege..

티스토리툴바