본문 바로가기

알고리즘

Prime Gap 문제 요약 : 어떤 수가 입력으로 들어옵니다. 이 수의 양옆에 있는 가장 가까운 소수 사이의 길이를 구하는 문제입니다. 입력된 수가 소수라면 0을 출력하면 됩니다. 예를 들어, 4가 입력되면 4보다 작은 소수는 3이고, 4보다 큰 소수는 5입니다. 따라서 답은 2가 됩니다. 문제링크 해결 방법 : 에라토스테네스의 체를 이용해서 소수를 미리 구해두고, 문제를 풀면 정말 쉬운 문제입니다. 결과 : Accepted 소스코드 #include #include using namespace std; const unsigned int MAX_NUM = 1299709; unsigned int n; unsigned int prime[MAX_NUM + 1]; unsigned int sqrtMaxNum = sqrt((doub.. 더보기
Palindrome Numbers 문제 요약 : 좌우가 대칭이 palindrome 수가 있습니다. 1, 2, 3, 4, ... 9, 11, 22, 33, ... 으로 순서가 있으며, 각 palindrome 숫자마다 차례대로 인덱스가 부여됩니다. 이러한 상황에서 인덱스를 주면 해당 인덱스의 palindrome 숫자를 구하는 문제입니다. 문제 링크 해결 방법 : 일단 palindrome은 좌우가 대칭이므로 숫자의 반만 생각하면 됩니다. 저는 자리수별로 생각을 했는데, 1자리 수 = 1, 2, ... , 9까지 모두 9개가 있습니다. 2자리 수 = 11, 22, .. , 99까지 모두 9개가 있습니다. 3자리 수 = 101, 111, 121, ..., 191, 202, 212, ...292, .... , 999 까지 9 * 10개(90)가 있.. 더보기
The Tourist Guide 문제 요약 : 출발 지점과 도착지점이 정해진 상태. 버스기사가 승객을 데리고 출발점에서 도착점까지 이동해야 합니다. 하지만 승객 수가 많고, 각 도시간의 길에는 제한 인원이 있기 때문에 1번 이상의 trip이 필요합니다. 최소한의 trip수로 모든 승객을 다 도착지로 보내는 문제입니다. 문제 링크 해결 방법 : 다익스트라 알고리즘을 활용했습니다. 결과 : Accepted 소스 코드 #include using namespace std; int N, R; int c1, c2, p; int start, dest, numOfTourists; int line[101][101]; int value[101]; bool check[101]; int cur; void init() { for(int i = 1; i > N.. 더보기
Word Index 문제 요약 : 어떤 string이 숫자 값을 갖게 됩니다. string의 길이는 1~5이고, 뒤에 나오는 문자가 앞의 문자보다 커야만 합니다. 그렇지 않을 경우에는 invalid하다고 하여 0을 출력합니다. 예를 들면, a = 1 b = 2 c = 3 ... z = 26 ab = 27 aa는 invalid이므로 0 ... vwxyz = 83681 입력으로 스트링이 들어오면, 그 스트링에 해당하는 숫자를 반환하면 됩니다. 문제 링크 해결 방법 : 경우의 수를 따져가며 대표 string의 테이블을 구성했습니다. 대표 string은 1자리 문자열일 경우 a, b, c, ,.... , z까지 모두 되고, 2자리 문자열일 경우 ab, bc, cd, de, .... , yz 가 됩니다. 3자리 문자열일 경우 abc.. 더보기
Knights Move 문제 요약 : 체스 판의 크기와 출발점, 도착점이 주어지는데, 프로그래머는 출발점에서 시작하여 도착점으로 몇번 만에 도착하는가를 출력해야 합니다. 문제 링크 알고리즘 : BFS 자료구조 : 원형 큐(배열로 구현) 느낀 점 : STL의 deque... 엄청나게 느리다는 것. Accept된 소스 코드 #include using namespace std; typedef struct { int x, y; }Point; const int qSize = 90000; Point q[qSize]; int pop = 0, push = 0; int N, boardSize; Point first, end, cur; int board[300][300]; int curValue, childValue; int left1, lef.. 더보기

티스토리툴바