본문 바로가기

Programming

 (110)
[백준 1717번] 집합의 표현 link : https://www.acmicpc.net/problem/1717 집합의 표현 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB116123722246730.487%문제초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친..
[백준 2003번] 수들의 합 2 link : https://www.acmicpc.net/problem/2003 수들의 합 2 성공시간 제한메모리 제한제출정답맞은 사람정답 비율0.5 초128 MB63532972221251.586%문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.출력첫째 줄에 경우의 수를 출력한다.예제 입력 1 복사4 2 1 1 1 1 예제 ..
[백준 1893번] 시저 암호 https://www.acmicpc.net/problem/1893 시저 암호 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB116513740.217%문제암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리우스 시저의 이름을 딴 것이다. 시저 암호는 대치 암호의 한 종류로써, 원문의 각 글자가 어떤 일정한 수만큼의 뒷 순서의 알파벳으로 대체되는 방식이다. (단, Z의 다음 알파벳은 A로 한다) 예를 들어, 대문자 알파벳의 일반적인 순서를 따르면서 3만큼 시프트(이동) 시키면, A는 D로 대체되고, B는 E로, C는 F로... 그런 식으로 변환되..
라빈 카프 알고리즘(Rabin-Karp Algorithm) 1. 개념 해싱을 사용해 일대일 매칭을 하는 알고리즘이다. 어떠한 S에서 W를 찾을때 S의 길이를 N, W의 길이를 M으로 가정하자. 제일 무식한 방법으로 W를 찾을 때에는 O(N*M)의 시간복잡도를 가지고 찾아야한다. (KMP 글 참고) 라빈 카프 알고리즘은 문자열을 모든 위치에서 비교해보는데, 먼저 해당 위치의 해시값을 비교하고 같다면 그 후에 단순 비교를 시작한다. 해당 위치의 부분 문자열과 찾으려는 단어가 다르면서 해시값이 같을 수는 있지만, 같은데 해시값이 다른 경우는 불가능한 점을 이용한 것이다. 여기서 중요한 점은 문자열을 해싱하려면 적어도 문자열 길이만큼 O(M)의 소요시간이 들어간다. 매번 해시값을 계산하다보면 시간 복잡도가 O(N*M)이 되어서 알고리즘이 쓸모가 없어진다. 그렇기 때문에..
문자열 검색 알고리즘(KMP) 1. 개념 KMP 알고리즘은 문자열 검색 알고리즘으로 알고리즘을 만든 사람의 이름 Knuth, Morris, Prett의 글자를 와서 이름이 붙었다. 우선 이 알고리즘을 왜 사용하는지를 보기 위해 단순한 문자열 검색의 예를 들어보겠다. 문자열 abcdefghijklmnop 이 있을때 ghi 문자열을 찾아보자. 단순하게 검색한다면 다음과 같이 검색할 것이다. abcdefghijklmnop (1) ghi(2) ghi(3) ghi... 이런 식으로 한 자리씩 이동하면서 비교하는 방법이 있다. 만약 이러한 방법으로 검색을 한다면 문자열의 길이만큼 비교횟수가 증가해서 시간 복잡도가 굉장히 커진다. ( O(N*M), N : 텍스트의 길이, M : 비교 문자열의 길이) 하지만 KMP 알고리즘을 사용하면 O(N+M)의..
[백준 15829번] Hashing link : https://www.acmicpc.net/problem/15829 Hashing 서브태스크시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB2331939393.939%문제APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므..
Hash Table(해시 테이블) 해시 테이블(Hash Table) Key값에 Value를 저장하는 데이터 구조로 key값을 통해 데이터에 접근한다. 그렇기에 데이터 접근 시간 복잡도가 O(1)이 되어 탐색이 빠르다는 장점을 갖는다. 이때 해시 테이블의 문제가 발생할 수 있는데 충돌에 관한 문제이다. 만약 다수의 Value 중 Key값이 겹치는 Value들이 존재하면 충돌이 발생한다. 이를 해결할 수 있는 방법은 다양하다. 첫째로 Chaining 방식은 Linked List를 이용하는 방법으로 저장하려는 해시 테이블에 같은 키 값의 데이터가 존재할 경우, 노드를 추가해 다음 노드를 가리키는 방식으로 체인을 이어서 해시 테이블을 구성하는 방식이다. 둘째로 Open addressing 방식은 index에 대한 충돌 처리에 대해서 Linked..
[백준 2152번] 여행 계획 세우기 link : https://www.acmicpc.net/problem/2152 여행 계획 세우기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB153228715114.632%문제평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1≤N≤10,000)개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다.태희는 다시 비행로에 대해 조사를 하였고, 총 M(1≤M≤100,000)개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1≤S≤N)번 도시에서 시작해서 T(1≤T≤N)번 ..

티스토리툴바