구현 검색 결과

해당 글 26건
배열 원소 삽입 삭제 패턴만 익혀봅시다.

사실, 이런 류의 기능을 하는 함수는 구현을 해야 할 일이 있을 겁니다. 여기에서는 optimize 생각 안 하고, 어떻게 빠르게 구현을 할 지, 패턴 정도만 이야기 해 보도록 하겠습니다. 3 종류의 쿼리가, Q개 들어온다고 생각해 보겠습니다. 이 때, insert 하는 위치와, delete 하는 위치 모두는 vaild 하다고 생각해 봅시다. 먼저, 구조체를 하나 정의하기 전에, 어떤 구조가 적합한지 먼저 생각해 봅시다. 사실, 적절한 자료구조가 있습니다. i번째 위치를 빠르게 찾는다. [s, e]번째 위치에 있는 원소 item들을 모두 delete 하는 것 또한, s번째 item을 찾고, e번째 item을 찾기만 하면 됩니다. 그러면 kth를 빠르게 찾을 수 있는 구조면 좋은데요. 그 중 하나는, sk..
구현 2020. 2. 16. 02:04
코테에서 답을 미리 저장하는 방법도 쓸만한가요? 네

메일로 질문이 왔습니다. 코딩 테스트를 준비할 때, 하드 코딩을 하는 것은 별로 안 좋나요? 사실, 그에 대한 답은 제가 쉽게 답할 수 없었습니다. 하드 코딩을 하거나, 답을 미리 저장을 해 놓는 방법으로, 백준 내에 있는 문제를 푼 것이 10개에서 15개 내외밖에 되지 않기 때문입니다. 중요도가 떨어져 보일 수 있어요. 이 기법을 쓰는 이유는 단 하나입니다. 정말 안 풀릴 때 최후의 수단으로 써 보라고. 제가 이 기법을 쓰지 않았다면, 10개에서 15개 정도 되는 문제를 풀지 못했을 겁니다. 오늘은 '답을 미리 저장해 놓는 기법' 을 구현 문제에 어떻게 쓰일 수 있는지 보도록 하겠습니다. 백준 17825번 문제인 주사위 윷놀이를 보도록 하겠습니다. 문제가 상당히 길기 때문에, 제가 링크를 걸어 놓겠습니..
자료알고/알고리즘 2020. 1. 29. 19:33
코딩테스트에 나올 만한 백트래킹 쉽게 정복해 봅시다.

구현, 백트래킹은 코딩 테스트에서 많이 나오는 단골 주제 중 하나입니다. 물론 tree dp나, segment tree하고 조합론을 아름답게 섞어놓은 dp도 나오기는 하지만. 중요도가 상대적으로 높지 않습니다. 그 말인 즉슨, 포기할 건 포기하더라도, 다른 사람들이 다 풀 수 있는 기본부터 챙겨 가자는 의미입니다. 그 기본 중 하나는 백트래킹입니다. 새로 추가된 문제인 18290번과 18292번 문제 NM과 K 시리즈를 보겠습니다. 개인적으로 적당히 난이도가 있으니, 입문 문제로는 좋은 듯 싶습니다. 문제는 아래와 같습니다. 조건을 잘 읽어보시고, 어떻게 풀어야 할 지 잘 생각해 보세요. 18292는 K 조건이 다른데요. K가 구간 [1, min(50,NM)]에 속하는 정수이다. 라는 것만 다릅니다. 그..
구현 2020. 1. 28. 17:03
백준 16768 : 뿌요뿌요 게임을 구현해 봅시다.

왠지 오늘은 뿌요뿌요 게임을 구현해 보고 싶어졌습니다. 구현 문제로, 고전 게임들을 구현하라는 문제가 생각보다 많이 나오는데요. 뿌요뿌요 역시 구현력을 보기 위한 좋은 문제 중 하나입니다. 문제는 아래와 같습니다. 16768번 문제를 단순화 시키면 위와 같습니다. 일단, 이 문제가 구현력으로 cover가 되는지, 아니면 optimize를 해야 하는지, 아니면, 특수한 알고리즘을 써서 시간 복잡도 자체를 낮춰야 하는지부터 보도록 하겠습니다. 먼저 문제를 간단하게 분석해 보도록 하겠습니다. 먼저 칸의 수는 최대 1000개입니다. 그러면 각 칸이 하나씩 연쇄적으로 없어진다고 했을 때, 1000 연쇄까지 일어날 수 있을 거에요. 정말 극단적으로 생각했을 때요. 그러면, 1연쇄가 일어날 때 어떤 일이 일어날까요?..
구현 2020. 1. 27. 01:15
2048 퍼즐 게임 1턴 구현 : 읽는 방향과 flag만 잘 고려하면 어렵지 않아요.

안녕하세요. chogahui05입니다. 저번 시간에 소코반을 구현해 보았습니다. 다소 어려웠어요. 오늘은 그것보다 다소 쉬운 2048 퍼즐의 1턴을 구현해 보도록 하겠습니다. 사실 뿌요뿌요 게임도 구현해 보면 재밌긴 합니다. 그런데 그건 BFS, DFS를 알아야 하는 전제가 깔리니 쉽지 않긴 하지만요. 하튼, 구현해 봅시다. 2048은 어떠한 것을 합칠 수 있는 방향이, 위, 아래, 왼쪽, 오른쪽이 있습니다. 이 중, 퍼즐이 요렇게 있고, 우측으로 합친다고 해 봅시다. 그러면, 먼저 2와 2가 merge 될 거에요. 다음에 노란색 4와 파란색 4는 merge 되지 않아요. 단지, 파란색 4끼리만 merge가 됩니다. 이렇게 합쳐질 겁니다. 다음에 8과 4를 합치려니, 되지 않습니다. right 명령을 내..
구현 2019. 12. 18. 17:22