분류 전체보기
[C++ STL] map 사용법
[C++ STL] map 사용법
2020.07.27[C++ STL] map 기본적인 사용법[C++ STL]에서 연관 컨테이너 중 하나인 map에 대해서 기본적인 사용법을 알아보도록 하겠습니다. map의 자료구조는 트리로 구성되어 있습니다. 정확히 말하면 레드 블랙 트리입니다. 레드 블랙 트리는 자가 균형 이진 탐색 트리로써 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하는 이진 탐색 트리입니다. 높이를 작게 유지하는 이유는 연산 과정에서 트리의 높이가 한쪽으로 치우치는 것을 막기 위함입니다. 이는 시간복잡도와 관련이 있습니다. 트리에 n개의 원소가 있을 때 O**(log n**)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다.*(문자열의 경우 예외 문자열의 길이를 고려해줘야 함) 1. 기본적인 형태 : mapmap의 기본적인 형태는 위..
[탐색 알고리즘] lower_bound, upper_bound
[탐색 알고리즘] lower_bound, upper_bound
2020.07.18[탐색 알고리즘] lower_bound, upper_bound lower_bound, upper_bound는 기본적으로 이진 탐색을 기반으로 하기 때문에 탐색하고자 하는 수열(원소들)이 오름차순으로 정렬되어 있어야 합니다. 이렇게 정렬된 리스트에서 특정 값 위치를 찾을 때 사용합니다. 그렇다면 특정 값이 무엇인지 밑에 설명을 보시면 알 수 있습니다. 1. lower_bound : 크거나 같은 수 중에서 첫 번째 수 (특정값) 2에 대한 lower_bound 즉 , 2와 같거나 큰 수중 가장 작은 인덱스를 찾고자 한다면 그림에서 보이는 바와 같이 1번 째입니다. [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using n..
[프로그래머스] 단어변환
[프로그래머스] 단어변환
2020.06.17문제 : 단어 변환 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/43163 [문제 풀이] 이 문제의 경우 주어진 문제를 그래프로 표현할 수 있어야 한다 즉 "그래프 모델링"을 해주어야 한다 어떤 것을 그래프의 정점으로 사용할 것이고 정점과 정점을 잇는 간선의 연결은 어떻게 정할 것인지 등이 있다 이 문제의 그래프 모델링 과정을 살펴보자! 정점은 어떤 것으로 사용해야 할 까? words에 있는 단어로 하면 좋지 않을까? 정점과 정점을 잇는 간선은 어떻게 연결시켜야 할까? 알파벳을 단 한 개만 바꾸어 해당 단어로 표현할 수 있다면 이는 연결 되었다고 볼 수 있다 즉 "hot" --> "hit" , "hot" --> "dot" 알파벳 차이가 단 ..
[SWEA 5653] 줄기세포배양
[SWEA 5653] 줄기세포배양
2020.06.17문제 : 5653. [모의 SW 역량테스트] 줄기세포배양 [문제 출처] : SW Expert Academy [모의 SW 역량테스트] - 줄기세포배양 이번 문제를 구현하는 데에는 생각 없이 그냥 단순하게 구현할 수 있었다 다만 변수의 명명을 명확하게 하지 않아 실수해 시간을 조금 많이 썼다 대충 변수 이름을 지어버려 의도치 않게 다른 큐를 사용해 디버깅 하느라 아까운 시간을 날렸다.. 이번 문제 같은 경우는 차량 정비소 문제와 미생물 격리를 풀기 위해서 썼던 자료구조와 시간의 흐름을 코드로 구현하는 방법이 매우 비슷하다고 느꼈다 [문제 풀이] 이번 문제를 풀 때 격자 (board)에 대한 언급이 없고 "시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다." 라는 조건 때문에 격자를 쓰지 않고 풀어야 하나..
Codeforces Round #650 (Div. 3)
Codeforces Round #650 (Div. 3)
2020.06.17[Contests] : Codeforces Round #650 (Div. 3) 아주 오랜만에 코드포스 콘테스트를 치러봤다 역시나 초보.. 답게 2문제를 풀었다 11: 45분쯤에 들어가 10분 안되게 늦게 풀기 시작했다 1~2번은 항상 빠르게 풀린다 나만 그런 것이 아니고 나와 비슷한 레이팅에 있으신 분들은 모두 그러할 것이라 생각한다 언제쯤 실력이 늘것인지.. 또 어떻게 해야 실력이 느는지 답답하고 한심하다.. [A Short Substrings ] 이 문제는 단순한 문자열 관련 구현 문제이다. 다음 예시는 문제에서 주어진 예시이다 A = " abac " 라고 하자 첫 번째 인덱스부터 2개씩 끊어서 써보자 "ab", "ba", "ac" 이것을 이어 쓰게 되면 새로운 문자열 B = "abbaac" 로 쓸 ..
[프로그래머스] [1차] 프렌즈4블록
[프로그래머스] [1차] 프렌즈4블록
2020.06.10문제 : Level2 [1차] 프렌즈4블록 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/17679 [문제 출처] 이 문제는 단순하게 보드를 순회하면서 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다 이 2가지를 구현하면 되는 문제이다 밑에 그림과 같이 단순한 4개의 블록은 그냥 지우고 4점을 획득 하면 된다. 하지만 다음 그림은 조금은 아주 조금은 복잡하다고 생각 할 수 있지만 전혀 아니다 1번을 바로 지워 버리게 되면 2번에서는 4개를 인식 하지 못하게 되므로 2번에서는 지울 수 가 없다 즉 4점밖에 획득 하지 못하게 된다 지울 경우 단..