분할정복으로 중복 데이터 개수 찾기

문제데이터가 정렬 된 배열에서 특정 값의 개수를 찾는 문제였다. 값은 중복될 수 있다. 접근법선형탐색이분탐색데이터가 정렬되어 있는 형태였기 때문에 선형탐색보다 이분탐색을 하기로 하였다. 그런데 이번 문제의 경우 데이터의 중복이 존재하는 경우였다. 따라서 이분탐색으로 값의 위치를 찾되, 찾은 위치를 기준으로 값이 존재하는 위치 구간을 찾기로 하였다.구현값의 위치 찾기이분탐색을 적용한다.int binarySearch(const vector &arr, int x) { int left = 0; int right = arr.size(); int check = -1; while (left x) { right = mid - 1; } else if (arr[mid..

• format_list_bulleted 기록/기타
• · 2024. 9. 27.

병합정렬 디버깅

디버깅프로그램을 짜는 것보다 중요한 것은 프로그램이 원하는 대로 돌아가는지 확인하는 과정인 것 같다. 코드를 작성하더라도 반드시 내 의도대로 돌아가는 보장이 없다. 그래서 디버깅을 해야한다. 디버깅을 하면 내 논리가 어디서 막히는 지 확인할 수 있기 때문이다.디버깅도 상황에 따라 다르게 쓰고 있다. 변수가 뭔지 해석할 때는 출력코드를 사용하고 반복문이 어떻게 작동하는지 확인할 때는 디버깅툴을 사용한다. 코테도 봐야하는 상황을 고려할 때 출력코드를 사용하는 것에 익숙해져야겠다.병합정렬을 구현하는데 합병 로직이 제대로 작동하지 않았다.void Merge(vector &a, int lo, int mid, int hi) { cout 구간: lo ~ mid, mid+1 ~ hi // c..

• format_list_bulleted 기록/기타
• · 2024. 9. 27.

[ C++ ] 문자열 패딩을 만드는 법

예제문자열 “123” 앞에 “0” 패딩을 3개 붙이기string a("123");string b = string(3, '0');int paddings = 4;a.insert(0, b); // "000123": 첫째 인수는 삽입하고자하는 위치, 두번째는 삽입하려는 문자열!a.insert(a.size(), string(paddings, '0')); // "0001230000"디버깅아래의 함수를 헷갈리면 안된다. 2번째 매개변수는 문자열이 아니라 문자 리터럴을 사용해야한다. string b = string(3, '0'); // 좋은 예안그러면 문자열의 null캐릭터까지 추가가 되어 패딩으로서의 역할을 하지 못한다.string(paddings, "0"); // 널캐릭터까지 추가되어 패딩이 망가진다.

• format_list_bulleted 프로그래밍 언어/C++
• · 2024. 9. 26.

[ 자료구조 ] Stack

#1 스택스택은 데이터를 쌓는 형태로 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last in First Out) 자료구조다.#2 연산push스택에 데이터를 삽입하는 연산으로 스택의 가장 위에 데이터를 저장한다.pop스택에 데이터를 삭제하는 연산으로 가장 마지막에 저장한 데이터를 제거한다.peek스택의 가장 위 데이터를 확인한다.#3 스택의 사용파이썬# 빈 스택 초기화stack = []print("stack:", stack)# 스택에 원소 추가stack = [1, 2, 3]stack.append(4)print("stack:", stack)# 스택 원소 제거stack = [1, 2, 3]stack.pop()print("stack:", stack)# 스택 원소 찾기stack = [1, 2, 3..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 26.

복잡도

시간과 공간프로그램을 실행하기 위해서는 시간과 메모리가 필요하다. 같은 기능을 수행하는 프로그램 둘이 있을 때 시간과 메모리를 덜 소모할수록 효율적인 프로그램이다.복잡도복잡도란 작성한 알고리즘이 효율적인지 시간, 공간적으로 효율적인지를 판단하는 기준이다. 알고리즘의 효율성을 정량화한다. 시간복잡도는 알고리즘의 실행시간을 정량화한 것이다. 공간복잡도는 알고리즘의 실행에 필요한 메모리량을 정량화한 것이다.빅오표기법빅오표기법은 알고리즘의 복잡도를 표기하는 방법 중에 하나로 최악의 경우의 상관관계를 표현한다. 입력 데이터 대비 함수를 실행하는 데에 필요한 비용(시간, 공간)의 상관관계를 수식의 최고차항으로 표현한다.그래프는 시간복잡도를 표현한 것이다. 최고차항이 커질수록 동일 입력 데이터 대비 소요되는 시간이 ..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 26.

[ COMMIT ] 비즈니스 마인드를 가진 개발자가 되는 방법 후기

#1 참석을 하게 된 계기 예전에 정글에서 팀 프로젝트를 할 때 멘토님이 개발자란 기술 그 자체 뿐만 아니라 사용자를 항상 염두해둬야한다고 하셨다. '사용자를 염두해야한다는 것', 나는 그 의미가 궁금해서 멘토님께 질문을 드렸다. 멘토님이 자세히 설명하셨지만 나의 경험 부족으로.... 이해를 못했다. 정글 수료 후 취업 준비를 하면서 메일을 받게 되었다. 구름 COMMIT에서 '비즈니스 마인드를 가진 개발자라 되는 방법'을 주제로 하는 세미나였다. 연사님도 토스에서 프론트 챕터 리드를 맡고 계셨다(참고로, 토스는 사일로라는 서비스 단위의 조직에서 같은 직군들을 묶어 놓은 그룹을 챕터라고 부른다). 마침 프론트엔드로 취업을 고려하고 있었고 '비즈니스 마인드'가 '사용자를 염두한 것'과 연관이 있을 것 같아..

• format_list_bulleted 기록/후기
• · 2024. 9. 26.