전체 글 검색 결과

해당 글 904건
c++ set이나 map을 전체 순회하는 데 시간 복잡도는 얼마일까요?

질문이 하나 들어왔습니다. 아래에 있는 foo 함수의 시간 복잡도는 어떻게 되나요? 쉽지 않은 질문입니다. c++에서 map이나 set은 self balanced binary Tree로 되어 있습니다. 흔히 '균형 트리' 라고 이야기를 합니다. 중요한 것은 어느 기준 점을 기준으로 왼쪽은 작은 것이, 오른쪽은 큰 것이 저장이 되어 있다는 것입니다. set이나 map이 Binary Tree의 속성을 가진다는 것은 시간 복잡도를 계산하는 데 굉장히 중요한 정보입니다. 즉, root를 기준으로 작은 것은 L, 큰 것은 R 부분에 있습니다. 그렇다면, iterator를, s.begin()부터, s.end()에 도달할 때 까지, 순회한다고 생각해 봅시다. 즉, 작은 것부터 큰 순서대로 순회를 한다고 하면 어떻게 ..
자료알고/자료구조 2020. 1. 31. 01:11
코테에서 답을 미리 저장하는 방법도 쓸만한가요? 네

메일로 질문이 왔습니다. 코딩 테스트를 준비할 때, 하드 코딩을 하는 것은 별로 안 좋나요? 사실, 그에 대한 답은 제가 쉽게 답할 수 없었습니다. 하드 코딩을 하거나, 답을 미리 저장을 해 놓는 방법으로, 백준 내에 있는 문제를 푼 것이 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
java public private : 전체에서 다 보이는가 vs 내부에서만 보이는가

오늘은 Java의 접근 제어자 중에서, private와 public에 대해서만 알아보도록 하겠습니다. 나머지 2개는 상속이랑, 패키지에 대해서 배우고 언급하도록 하겠습니다. 사실 저 혼자서 개발할 때에는 그냥 Class를 구조체 쓰듯이 다 public으로 선언해 버리고, 다른 클래스에서 접근 가능하게 할 수 있습니다. 그냥 내 마음대로 짜면 되니까요. 그랬으면 좋겠어요. A 클래스는 위와 같습니다. packA에 선언이 되어 있습니다. public으로 선언된 a가 있고, private로 선언된 b가 있습니다. 프로젝트의 구조는 다음과 같습니다. packA에 있는 A 클래스가 있고요. main 함수는, Main 패키지의 Main 클래스 안에 있습니다. 메인 함수에서 A 객체를 하나 생성하였습니다. A의 필드..
코딩/Java 2020. 1. 25. 14:50