전체 글

[BOJ/C++] 6198번 옥상 정원 꾸미기

문제 설명 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12 2 -> 빌딩의 높이 [1][2][3][4][5][6] -> 빌딩의 번호 1번 관리인은 2, 3, 4번 ..

[BOJ/C++] 2493번 탑

문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면,..

[바킹독 알고리즘] 0x05강:Stack

Stack : Last In First Out 원소의 추가, 제거 O(1) 제일 상단 원소 확인 O(1) 제일 상단이 아닌 나머지 원소 확인/변경 원칙적으로 불가능 배열로 스택 구현 #include using namespace std; const int MX=10000005; int dat[MX]; int pos = 0; //삽입해야할 index void push(int x){ dat[pos++]=x; } void pop() { pos--; } int top(){ return data[pos-1]; } STL 스택 문제 현황 연습 문제 ✔ 10828 스택 정답 코드 기본 문제 ✔ 10773 제로 정답 코드 응용 문제 1874 스택 수열 정답 코드 응용 문제 ✔ 2493 탑 정답 코드 응용 문제 ✔ 619..

[BOJ/C++] 5397번 키로거

문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000)..

[바킹독 알고리즘] 0x04강:Linked List

연결리스트 성질 k 번째 원소 확인/변경 위해 O(k) 필요 임의의 위치에 원소 추가, 제거가 O(1) (추가/제거하는 위치를 알고있는 경우) Cache rate hit은 낮지만 할당이 좋다. → 임의의 위치에 원소 추가하거나 제거하는 연산이 많을경우 연결리스트 사용 좋다. 연결리스트 종류: 단일 연결리스트/이중연결 리스트/환형 연결리스트 배열 vs 연결리스트 연결리스트 구현 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num){ dat[unused] = num; pre[unused] = addr; nxt[unused] = ..

[BOJ/C++] 3273번 두 수의 합

문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 풀이 아이디어 - 입력된 숫자들을 배열에 담는다 - 합으로 나올 수 있는 최대 값 크기만큼 bool array를 만든다. - O(N)에 문제를 풀고, ai+aj=x가 있는지..

[BOJ/C++] 1406번 에디터

문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. LDBP $ 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 ..

[바킹독 알고리즘] 0x03강:Array

연습문제: O(1)에 배열 안 원소 중 2개의 합이 100인게 존재하는지 확인하기 int func2(int arr[], int len) { int occur[101] = {}; for (int i = 0; i < len; i++) { if (occur[100 - arr[i]] == 1) { return 1; } occur[arr[i]] = 1; } return 0; } 0~100까지 인덱스가 있는 배열을 만듬 내가 입력한 배열을 돌면서 원소에 해당하는 값을 occur 배열 인덱스 값으로 1을 추가함. 만약에 100-해당 원소 가 occur 배열에서 1 값을 가지고 있으면 합 100이 가능한 원소가 존재한다는 뜻 따라서 존재여부로 O(1)에 값을 구할 수 있다. 문제 풀이 현황 연습 문제✔ 10808 알파..

[BOJ/C++] 1475번 방번호

#include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string N; vector vec(10); int max = vec[1]; fill(vec.begin(), vec.end(), 0); cin >> N; for (int i = 0; i vec[9] + 1) { vec[6]--; vec[9]++; } else if (vec[9] > vec[6] + 1) { vec[9]--; vec[6]++; } } for (int i = 0; i < 10; i++) { if (max < vec[i]) {..

[바킹독 알고리즘] 0x02강:STL

STL과 함수 인자 stl 벡터를 함수 인자로 넘길때 이를 복사하는 과정이 필요하기 때문에 O(N) 걸림 하지만 레퍼런스 사용시 그 과정이 생략되어 우리가 생각하는 것처럼 O(1)이 걸린다. 표준 입출력 공백포함된 함수를 입력 받을땐 scanf/ cin 안됨 → 둘다 공백 앞까지만 입력으로 받기 때문 → 따라서 getline을 사용하자! c에 printf나 scanf 안쓸꺼면 ios::sync_with_stdio(0) 사용하기 (sync를 끊는다는 뜻) cin.tie(0) : cin 사용 시 cout 버퍼를 비울 필요가 없기 때문에 이를 사용. endl : 사용하지 말기.. 개행하고 버퍼 비우는 명령어이므로 할 필요가 없다.

[UMC/Android] 9주차 - Open API 활용

9주차 - Open API 활용 🧙‍♀️ Retrofit2 를 이용해 OpenAPI 연동 - 주간 박스오피스 API로 Recyclerview 구현 retrofit을 build 하는 부분을 전역적으로 사용할 수 없을까? 에 대한 궁금증 발생 싱글톤 패턴을 이용하면 activity마다 build 할 필요없이 전역적으로 사용 가능하다! object RetrofitService { private const val BASE_URL = "" //받아올 URL 을 넣어주면 된다. val retrofit:Retrofit = Retrofit.Builder() .baseUrl(BASE_URL) .addConverterFactory(GsonConverterFactory.create()) .build() } // 다음과 같이..

[Android] Retrofit2 싱글톤패턴 적용하기

Retrofit2 싱글톤패턴 적용하기 UMC 안드로이드 세미나에서 retrofit2 를 사용하는 방법을 배웠다. 당시 세미나에서 retrofit를 사용할 Activity에다가 build를 하셨다. 그렇다면 retrofit을 통해 서버와 데이터를 주고받을 activity전부에 저렇게 build를 다 해야하는건가 의문이 생겼고, 관련 질문을 하니 싱글톤패턴에 대해서 알려주셨다! 이를 기억하기위해 블로그에 작성해보고자 한다. 싱글톤 패턴이란? 객체의 인스턴스가 오직 1개만 생성되는 패턴을 의미한다. 싱글톤패턴을 사용하면 1번의 정의만으로 전역적으로 사용할 수 있다. 그러므로 NetworkService, DatabaseService등 하나의 객체만 필요 할 경우 사용된다! 사용이유 싱글톤패턴으로 인스턴스를 생성..