[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – N번째 리스트 구하기

Given a singly linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned.

 

Limitations are below:

1] O(n) Time Complexity

2] O(1) space Complexity

 

solve] at first, I tried to travel twice. of course, it is very easy. but there is a better solution.

Just scan once. The main algorithm is very easy. just after kth node, traveling kth_node from head together. when list node reach the tail node, kth_node can reach kth_node.

 

void travel(int k){
 List *list = head;
 List *kth_node = head;
 int count = 0;
 while( list != NULL ){
 printf("(%d)\n", list->value);
 if( count > k ){
 kth_node = kth_node->next;
 }
 list = list->next;
 count++;
 }
 printf("(%d)th node from end is (%d)\n", k, kth_node->value );
 }

 

 

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – BST에서 중복 개수 새기

Write an algorithm to print out how many extra duplicates there are in a binary search tree. and using global value for count and value

 

example]

———– 3

—2—————– 3

– 1 —2 ——————4

———————3 ———4

————————————–5

———————————————–5

output :

2  1

3  2

4  1

5  1

 

solve) Focus on, O(n) time complexity and O(1) space just travel this BST tree using inorder sequence.

 

void _traversePrint(Node *node){
 if( node->left ){
 _traversePrint(node->left);
 }

if( count && (value == node->data) ){
 count++;
 }else{
 if( count > 1 ){
 printf("(%d):(%d)\n", value, count);
 value = node->data;
 count = 1;
 }else{
 count = 1;
 value = node->data;
 }
 }

if( node->right ){
 _traversePrint(node->right);
 }

if( node == root && count > 1 ){
 printf("(%d):(%d)\n", value, count);
 }
 }

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 공통 선조 찾기

Design an algorithm to find the least common ancestor of two nodes in a Binary tree(Note: Its not a binary search Tree)
Node Structure is given as

Class Node{
int data;
Node leftchild;
Node Rightchild;
}

solution) I just think that if one node notice that there are 2 nodes that we want to find. it is the common ancestor of two nodes. so it's solution is really easy to understand.


int find_node2( Node *node, int value1, int value2 ) {
 int ret = 0;
 if( node->data == value1 || node->data == value2 ) {
 ret++;
 }

if( node->left ) {
 ret += find_node2( node->left, value1, value2 );
 }

if( node->right ) {
 ret += find_node2( node->right, value1, value2 );
 }

if( ret == 2 ){
 printf("this node is common parent: %d(%d,%d)\n",
 node->data, value1, value2);
 }

return ret > 0 ? 1 : 0;
}

			

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 꼬여있는 코일

• Given an 4n X 4n Matrix, where n is a positive integer taken as input. Imagine the matrix consisting of two interleaved coils whose centers are at the centre of the matrix. Implement a java program which takes an integer (n) as input and prints the two coils in two seperate lines.

Please have a look at the below examples to get a sense of what the two coils are :
• Example 1:
• Input: 1
• Matrix:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16

• Output the Two Coils as:
– Coil1: 10 06 02 03 04 08 12 16
– Coil2: 07 11 15 14 13 09 05 01

 

Solution.

I can easily guess. there are some rules. the start point are always (2n, 2n+1) and (2n+1, 2n) and there are 4 directions which follow this order: UP, RIGHT, DOWN, LEFT. and  In (2n,2n+1)  case it starts from UP, and (2n+1, 2n), it starts from DOWN. so I can easily calculate next values.

 

#include <stdio.h>
#include <stdlib.h>

#define DIRECTION_NUMBER 4
#define STEP 2
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

void find_direction( int x, int y, int n, int direction ) {
 int end = n * n * 4 * 2;
 int step = STEP;
 int current_direction = direction;
 int pos_x = x;
 int pos_y = y;
 int delta = 0;
 int count = 1;

int seed = (y-1)*4*n+(x);
 printf("%d", seed);
 while( count < end ) {
 for( int i = 0; i < STEP; i++ ) {
 switch( direction ){
 case UP:
 delta = -(4*n);
 break;
 case RIGHT:
 delta = 1;
 break;
 case DOWN:
 delta = 4*n;
 break;
 case LEFT:
 delta = -1;
 break;


 }

for ( int j = 0; j < step && count < end; j++ ) {
 seed += delta;
 printf(" %d", seed, delta );
 count++;
 }

direction++;
 if( DIRECTION_NUMBER == direction ){
 direction = UP;
 }
 }
 step += STEP;
 }
 printf("\n");
}

int main( int argc, char *argv[] ){
 int n = atoi(argv[1]);
 find_direction( 2*n , 2*n+1, n, UP );
 find_direction( 2*n+1, 2*n , n, DOWN );
 return 0;
}

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 중복 글자 없애기

Given a string, you have remove duplicates from it in O(n) time and O(1) space.

 

for example:

abcbaad ==> abcd

 

limitations

1. just use O(n) times

2. just use O(1) space

 

solution: Just using lookup table, make 256 bytes char map, and insert char which is founded. and check it. if ch is not 0, it already exists. at that time just skip that character.

if you want to reduce memory size, using Bit Vector and then you will use just 32 bytes.

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main( int argc, char *argv[] )
{
 unsigned char bitmap[256];
 memset( bitmap, 0, 256 );

unsigned char *ch = (unsigned char *)argv[1];
 while( *ch != '\0' ) {
 if( bitmap[*ch] == '\0' ){
 bitmap[*ch] = 1;
 printf("%c", *ch );
 }
 ch++;
 }
 printf("\n");

return 0;
}

아주 간단한 띄워쓰기 교정 아이디어와 테스트

자주 참고하는 블로그인 http://freesearch.pe.kr/ 의 고감자님이 띄워쓰기 교정을 간단하게 만드시겠다라는 글을 보고, 간단하게 만들어 볼 수 있지 않을까 라는 생각이 들었다.

 

처음 생각한 것은, 단어 사전을 구축하고, 어미/어간을 분석해서 조사 뒤에서 끊어주면 되지 않게냐라는 생각이 들었는데, 이러면, 형태소 분석기가 필요하다. -_-(덜덜덜, 이게 핵심이 될듯) 그러다가, 빅데이터 시대에, 메모리에 웬만한 데이터를 다 올리면 간단하게 만들 수 있지 않을까?( 어려운 지식은 모두 제외하고 -_-) 라는 생각이 들어서, 간단하게 만들어보았다. 오늘 생각해서 오늘 몇시간 만에 만들었으니, 어려운 건 아님… -_-(어려운건 못만들어요.)

 

일단 생각의 아이디어의 핵심은 trie 자료구조와 띄워쓰기 용례사전이다.  어떤 아이디어인가 하면, 신문의 사설 데이터들을 요새는 쉽게 구할 수 있는데, 이를 메모리에 다 올려놓고, 최장일치로 일치하는 부분을 찾고, 이에 실패하는 부분에서 띄워주면 띄워쓰기가 되지 않을까라는 심플한 아이디어였다. -_-

 

위와 같이 trie로 저장되어 있을때 “한국민은한다” 라고 되어 있으면 한국민은 에서 최장일치로 발견이 되고, “한국민은한” 은 일치하지 않으므로, 여기서 띄워쓰기를 해주면 된다라는 간단한 아이디어이다. 그리고 이를 위한 것들이 다음과 같이 필요했다.

 

1. trie 자료 구조

2. 용례 사전 구축

 

위의 두 가지를 어떻게 해결해야 할까? 1번의 경우 직접 코딩을 하는 방법도 있었지만, 그러면 실제로 시간을 너무 많이 쓸 거 같아서, 일단은 패스를 하고 trie 라이브러리를 찾아보았다. 인터넷 서핑중에 rein 님 블로그에서 좋은 trie 라이브러리를 찾을 수 있었다.( http://rein.kr/blog/archives/1443 )

 

DASTrie 라는 것인데, http://www.chokkan.org/software/dastrie/ 들어가는 사전은 사전순으로 정렬되어야 한다.(이거 몰라서 잠시 삽질을…)

 

이제 용례 사전의 구축의 경우, 신문 사설이 생각이 났다. 신문 사설의 경우, 논술등에서도 많이 참고하므로, 띄워쓰기가 잘 되어 있을 것이고, 신문사 등에 쉽게 크롤링이 되지 않을까 싶어서였다. 그리고 샘플을 조금 띄어 고치기 시작했는데, 이제부터 삽질이 시작되었다. 머리 속으로 명확한 알고리즘을 만든것이 아니었고, 또한 DAStrie의 특성이 내가 생각한 것들과 달라서( 정확히는 내가 trie를 잘못 이해해서) 좀 삽질을 하게되었다.

 

아이디어가 동작하는가를 검증하는게 주 목표여서 코드를 그냥 대충 짜고 정리도 안되어있다. (알고리즘은 좀 고민할걸 T.T)

#include <fstream>
#include <iostream>
#include <string>
#include <dastrie.h>

typedef dastrie::builder<char*, int> builder_type;
typedef dastrie::trie<int> trie_type;
typedef builder_type::record_type record_type;
#include "record.h"

int get_code_size( char data )
{
 unsigned char bit_mask = 0x80;
 int shift_count = 0;

if( (data & bit_mask) == bit_mask )
 {
 for( ; shift_count < 8; shift_count++ )
 {
 if( 0 == ( data & ( bit_mask >> shift_count ) ) )
 {
 break;
 }
 }
 }
 else
 {
 return 1;
 }

return shift_count;
}

&nbsp;

int main(int argc, char *argv[])
{
 try {
 // Build a double-array trie from the records.
 builder_type builder;
 builder.build(records, records + sizeof(records)/sizeof(records[0]));

// Store the double-array trie to a file.
 std::ofstream ofs("sample.db", std::ios::binary);
 builder.write(ofs);
 ofs.close();

} catch (const builder_type::exception& e) {
 // Abort if something went wrong...
 std::cerr << "ERROR: " << e.what() << std::endl;
 return 1;
 }

// Open the trie file.
 std::ifstream ifs("sample.db", std::ios::binary);
 if (ifs.fail()) {
 std::cerr << "ERROR: Failed to open a trie file." << std::endl;
 return 1;
 }

// Read the trie.
 trie_type trie;
 if (trie.read(ifs) == 0) {
 std::cerr << "ERROR: Failed to read a trie file." << std::endl;
 return 1;
 }

&nbsp;

char buffer[256];
 char showbuffer[256];
 char blankbuffer[256];
 char *start_ptr = buffer;
 char *code_ptr = buffer;
 char *copy_ptr = showbuffer;

memset( showbuffer, 0, 256 );
 memset( blankbuffer, 0, 256 );

std::cin.getline( buffer, sizeof(buffer)-1 );
 int size = strlen( buffer );
 int count = 0;
 bool flag = false;
 bool pass_flag = false;

for( int i = 0; i < size; )
 {
 int code_size = get_code_size( *(start_ptr+count) );
 if( code_size == 1 && *(start_ptr+count) == ' ' )
 {
 memset( blankbuffer, 0, 256 );
 memcpy( copy_ptr, start_ptr + count, code_size );
 copy_ptr += code_size;
 i += code_size;
 start_ptr += count;
 start_ptr += code_size;
 count = 0;
 flag = false;
 continue;
 }

else
 {
 memcpy( blankbuffer, start_ptr, count+code_size );
 int ret = trie.in( blankbuffer );
 std::cout << blankbuffer << ": " << ret << "," << code_size << "," << count << "," << i << "," << size << std::endl;
 if( ret == 0 && flag )
 {
 *copy_ptr++ = ' ';
 memset( blankbuffer, 0, 256 );
 start_ptr += count;
 count = 0;
 flag = false;
 }
 else if( ret == 1 )
 {
 flag = true;
 }
 }

memcpy( copy_ptr, start_ptr + count, code_size );
 count += code_size;
 std::cout << copy_ptr << std::endl;
 copy_ptr += code_size;
 i += code_size;
 }

std::cout << "Result: " << showbuffer << std::endl;

return 0;
}

 

용례는 웹페이지를 다운 받아서, 사전 부분만 추출해서 이를 가공했다.

record_type records[] = {
 { "16조원이",1 },
 { "17조원이",2 },
 { "1만4525명",3 },
 { "1만6242명으로",4 },
 { "1만8170명",5 },
 { "2011년판",6 },
 { "2457만명이다",7 },
 { "25%로",8 },
 { "25만원씩",9 },
 { "2만2250명",10 },
 { "2배",11 },
 { "30만원씩",12 },
 { "3배다",13 },

...

...

{ "할당제를",458 },
 { "합쳐",459 },
 { "해도",460 },
 { "해보려면",461 },
 { "해에",462 },
 { "허약한",463 },
 { "현대",464 },
 { "현재",465 },

};

 

이제 간단하게 테스트를 해보면

입력문장: “국민이 정치에둘리지않으려면 지금이 어느 때이고 여기가 어느세상인지를 정확하게알아야한다”

결과: “국민이 정치에 둘리지 않으려면 지금이 어느 때이고 여기가 어느 세상인지를 정확하게 알아야 한다”

 

잘나오는 것 같이 보이지만, 아직 문제가 많이 있다.

1. 용례에 없는 부분은 그냥 하나로 나온다. -_-, 사실 이부분은 용례가 많아지면, 어느정도 충분히 커버가 가능할 듯 하다.

2. “아버지가방에들어가신다”의 경우 “아버지가 방에 들어가신다” 와 “아버지 가방에 들어가신다” 어느것이 옳은 것일까?

-> 여기서는 최장일치이므로 “아버지가 방에 들어가신다” 가 된다.

3. 특수문자나 이런 부분도 아직 처리가 미흡하다.(버그가 많다)

 

그냥 갑자기 든 생각을 구현해 본것이라서 완전 엉터리지만, 수많은 인터넷 데이터를 용례 사전으로 만들고 속도를 빠르게 하면, 상당히 뛰어난 성능이 나오지 않을까 하는 혼자만의 생각을 해본다. 클라우드랑 연동하고 용례 사전이 특정 영역에 맞춰지면, 과학분야와 문학분야에 서로 다른 띄워쓰기를 해줄수도… 그리고 단순 트라이 매칭이므로, 용례 사전만 바뀌면, 외국어도 가능할 듯 하다.

 

그리고 trie 자료구조가 딱 내가 원하는 형태가 아니라 코드가 복잡해지고 거의 그냥 맵처럼 되어버렸는데, 이쪽 코드를 새로 짜서, 실시간 추가 가능하고 띄워쓰기에 맞게 코드를 만들 필요가 있을듯하다.