본문 바로가기

분류 전체보기

(62)
[백준/C++] 알고리즘 1715번 - 카드 정렬하기 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1715번 - 카드 정렬하기 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1715  [문제 접근]- 최소한의 비교를 하기 위해서는 매번 최소의 선택을 해야 합니다. 여기서 그리디 문제일 수도 있다는 것을 느꼈습니다.- 시간제한이 2초이고 N이 10만이하이기 때문에, O(N^2)풀이는 불가능 합니다. 최소를 구하는 문제여서 자료구조 중 이진검색트리, 우선순위 큐가 떠올랐습니다.- 리스트에서 가장 작은 두 데이터를 선택하고 다시 이 두 데이터의 합을 리스트에 넣고 다시 가장 작은 두 데이터를 선택하고의 반복.. [풀이 전략]- 매순간 리스트에서 최솟값을 가져오기 유리한 자료구조인 우선순위 큐를  이용하여 구현하였습니..
[백준/C++] 알고리즘 1806번 - 부분 합 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1806번 - 부분 합 을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1806  [문제 접근]- 제한 시간이 0.5초이고 n이 10만이하이기 때문에 O(N^2)풀이는 불가능합니다.-  1차원 배열에서 O(N^2)이 아닌 풀이를 원하기 때문에 이분탐색 혹은 투포인터가 떠올랐습니다.   [풀이 전략]- 투포인터를 이용하여 풀이하였습니다. [코드]#include #include #include using namespace std;int n , s ;int arr[100'001] ; int main() { ios::sync_with_stdio(0); cin.tie(0); int res = 1'000'000'..
[백준/C++] 알고리즘 1620번 - 나는야 포켓몬 마스터 이다솜 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1620번 - 나는야 포켓몬 마스터 이다솜 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1620  [문제 접근]-  이름에 대응되는 숫자를, 숫자에 대응되는 이름을 출력하는 문제입니다.- n과 m이 10만이하이고, 시간제한이 2초이기 때문에 시간복잡도 O(N)이나 O(NlogN)이 통과할 거 같습니다. [풀이 전략]- 해시맵 두 개를 이용하여 풀었습니다.- 문자열이 숫자인지 아닌지 판별하는 함수를 작성했습니다. [코드]#include #include #include #include using namespace std;bool isNumber(string str) { for(auto c: str) { ..
[백준/C++] 알고리즘 7785번 - 회사에 있는 사람 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 7785번 회사에 있는 사람 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/7785[문제 접근]- 각 사람마다 최종적인 값이 enter인지 파악이 관건이라고 생각했습니다. 또한 enter의 개수가 leave개수보다 많아도 동일하다고 생각했습니다. - 시간 제한은 1초이고, n이 백만입니다. 1억번 연산하는데 c++은 대략 1초가 걸리니 시간복잡도가 N^2 풀이는 이 문제를 통과할 수 없습니다. 해시, 이진 검색 트리, 이분 탐색, 투포인터가 떠올랐습니다. [풀이 전략]- unordered_map과 map 중 고민하다가 최종 출력이 이름 역순이어서 이미 순서가 정해진 ordered_map이 더 간단하다고 판단이 ..
[iOS] 의존성 주입(Dependency Injection) 1.  의존성 주입Dependency Injection) 이란?Giving an object its instance variables, instead of creating them in the object.이 말은 즉슨, 인스턴스 변수를 객체 안에서 생성하는 것이 아니라 외부에서 객체에게 주는 것2.  왜 의존성 주입이 필요한가?결론은 유지보수를 쉽게 하려고 하는 게 목적이다. 즉 노가다를 하지 않기 위해서이다.조금 더 풀어쓰면 대표적으로 4가지의 이유가 있다.Transparency(투명성)객체에게 요구되는 책임과 필요조건이 보다 명확하고 투명성있게 볼 수 있다.예를 들어 ViewController에 DataManager를 주입시킴으로써 ViewController가 DataManger에게 의존을 하고 있..
[C++] 이분 탐색 안녕하세요! 테크지니어22입니다.오늘은 이분 탐색에 대해서 알아보도록 하겠습니다. 1. 이분탐색이란?정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색법입니다.일반적으로 선형탐색 시간초과가 발생하면 이분탐색을 떠올리게 됩니다.하지만 이분 탐색이 가장 많이 사용하는 상황은 최적화문제를 결정 문제로 변환이 필요할 때입니다.'한쪽 구간은 뭔가가 되고, 한쪽 구간은 안 된다. 따라서 어떤 한 값의 가능 여부를 알면 그 값을 기준으로 어떤 구간을 탐색할지 결정할 수 있다' 가 핵심입니다. 2. 탐색구간- 어떤 탐색구간을 사용하건 구현상의 선택의 문제이기 때문에 자신에게 편한 것을 선택하면 됩니다. [lo,hi] 구간조건: while (lo ≤ hi)경계 업데이트 : if(co..
[프로그래머스/C++] 알고리즘 - 오픈 채팅방 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 오픈 채팅방을  풀어보도록 하겠습니다.  https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr[문제 접근]이 문제는 문자열을 활용한 구현문제입니다. 유저아이디값이 있고, 이에 매칭되는 닉네임이 변경되는 문제이기 때문에 unorded_map을 활용하여 풀었습니다. [풀이 전략]1. c++은 split함수가 없기 때문에 직접 구현합니다.2. for문을 돌면서- Enter와 Change에 해당되면 ..
[프로그래머스/C++] 알고리즘 - 문자열 압축 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 문자열 압축을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  [문제 접근]문자열을 활용한 단순 구현문제입니다. [풀이 전략]중복이 되지 않는 경우는 중복개수 1을 추가할 필요가 없다는 부분에 유의하여 구현을 하면 됩니다.주의할 점은 문자열이 한 개 인경우에는 answer초기값이 출력되기 때문에 이에 대한 예외처리가 필요합니다. [코드]#include #inclu..
[프로그래머스/C++] 알고리즘 - 괄호 변환 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 괄호 변환을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  [문제 접근]문제가 길어서 읽으면서 머릿 속에 막 들어오지 않아서 최대한 적으면서 조건들을 분기화하면서 읽었습니다.이해가 안되는 부분들은 예제들을 보면서 최대한 이해하려고 했습니다. 문제는 재귀함수가 가미된 단순 구현문제였습니다.아래처럼 적으면서 읽었습니다. [풀이 전략]위에 작성한 문제 접근방법을 ..
[프로그래머스/C++] 알고리즘 - 메뉴 리뉴얼 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 메뉴 리뉴얼 을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근]orders의 최대크기 20, orders각 원소의 크기를 10, course =[2,3,4,5,6,7,8,9,10]라 가정하면연산 개수는 약 20*(10C2+10C3+10C4+ ... 10C10) 으로 시간복잡도가 크지 않음을 알 수 있습니다.그래서 완전탐색으로 접근했고, 조합을 이용하여..