20, 시작, 새로운.

이분 탐색, 매개변수 탐색 정의 이분탐색(Binary Search) 정의 이분 탐색(Binary Search)은 순차 탐색의 시간복잡도 O(N)에서 O(logN)으로 탐색 시간을 줄여 탐색하는 방법으로, 정렬된 배열 안에서만 사용이 가능하다. 단순한 '탐색'은 코딩테스트에 출제되지 않는다. 이를 활용한 문제가 나온다. mid == target이면 탐색을 종료해도 상관없다는 게 매개변수 탐색과 다른 특징이다. 매개변수 탐색(Parametric Search) 정의 조건에 맞는 최대/최소값을 찾을 때 파라미터를 주로 사용하며, 이 파라미터는 이분 탐색을 이용해서 left, right, mid(=parameter) 를 계산하여 구하는 문제이다. 파라미터를 변수로 값을 True/False를 리턴하는 어떠한 함수 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17680 리뷰 자료구조 및 알고리즘 Least Recently Used → 벡터와 같은 자료구조에서 Hit일 경우 remove and push back을 통해 '리뉴얼' 함으로써 삭제를 방지 문제 풀이에서의 핵심 포인트 Hit/Miss에 대한 case 구현하기: 굳이 몇 번 Hit되었는지 count할 필요 없이, Hit일 경우 remove and push back 대/소문자 구별 없이 처리하기: - cpp reference가 사용가능하다면 아래와 같은 함수(ToLower) 제작 - 사용이 안 된다면 #include strcasecmp(a.c_str(), b.c_str()) == 0 을 이용 Ca..

문자열 입력 받기 getline 입력 문자열이 스페이스 바 혹은 '\n' 이 있는 문자열일 경우, cin >> string 으로는 처리하기 힘들다. getline으로 처리할 경우 손쉽게 처리할 수 있다. cin의 getline 이 있고, string의 getline이 있다. 나는 string 의 getline 이 편했다. 입력받는 문자열에 대해 deliminator 전까지를 하나의 string으로 처리해준다. getline(istream& is, string str); getline(istream& is, string str, char dlim); 보통 istream으로는 cin 을 쓰고, 저장하고자 하는 변수 str를 지정해주면 된다. 주의사항 이전 입력에서 '\n'이 처리되지 않았을 경우(buffer..

투포인터 알고리즘 개념 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작한다. 이때문에 투포인터 알고리즘이라 부른다. 알고리즘 설명 및 특징 완전탐색으로 해결하면 시간 초과가 나는 문제를 투포인터 알고리즘으로 시간복잡도를 줄여 문제를 해결할 수 있다. (완전탐색의 경우 for 문을 중첩해서 2개 이상 형성해야하는 반면, 투포인터는 반복문 1개로도 가능하게 된다) 1차원 배열의 완전탐색에서 n제곱 꼴의 시간복잡도를 n 의 1제곱 으로 줄일 수 있다. 알고리즘 대표 유형문제 - 2003 수들의 합 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구..

Vision AI for Skin - 이훈재 AI Lead(ART Lab) - 이미지의 배경이 정말 쓸만한가를 테스트하는 AI(얼굴 사진을 찍었을 때 너무 밝거나 어둡거나 등을 제거) 모두가 원하는 AI Trouble Detection AI AI Application을 개발하기 위한 Process 가능성 탐색(개발 착수 과정) 트러블 탐색을 할 수 있는 AI만들수 있을까? → 최소한의 리소스로 우리가 만들수 있는지 체크(빠른 PoC) → 만들면 사람들이 쓸까? → 내부, 외부 고객에게 테스트해보자(MVP) → 빠른 PoC Raw data, Labeling(어떤게 잡티고 여드름이고.. 를 구분하기 힘들었다~), Modeling(모델링에 들어가는 노력은 최소화. 될지 안될지 모르니까 일단 힘빼고.) → 해보..

문제 설명 https://www.acmicpc.net/problem/11066 동적계획법을 사용해서 푸는 문제. 가능한 조합을 전수조사해서 그 중 minimum 값을 구해 dp 배열을 채워나가면 된다. 점화식을 세우는 과정에서 많은 어려움이 있는 문제이다. 점화식 조건이 어려울 뿐 아니라, 단순히 dp의 이전 인덱스들과의 단순 연산보다 조금 더 심화되었다. 나의 문제 풀이 시도 및 발생한 문제점 가능한 모든 조합을 찾아야 한다는 점을 빠르게 캐치하지 못했음(dp 점화식 설계 실패) 문제를 쪼개서 해결해야한다는 점은 이해하고 있었지만, 점화식 설계가 틀렸다. 나의 접근은, 2차원 dp 배열에서 i 인덱스는 '어디까지 보았는가', j 인덱스는 '몇 개를 더했는가' 였고, dp 배열을 업데이트 할 때, 이전의..

Assignment 1 실행 순서 1. 환경 세팅 # firstly, install ROS Melodic (This assignment does not work on M1, M2 macbooks.) # Second, install opencv # 내 경우엔 """ $ python2 >>> import cv2 >>> cv2.__version__ '4.2.0' """ $ echo "export ROS_MASTER_URI=http://localhost:11311 " >> ~/.bashrc """ 만약 ping 연결이 안된다면, bashrc 의 ROS_HOST ip를 ifconfig 후 나오는 것으로 교체. """ $ sudo apt update && sudo apt upgrade -y $ sudo apt in..

동적 계획법 정의 동적계획법(Dynamic Programming) 개념 동적계획법이란, 큰 문제에 대한 해답을 얻기 위해 해당 문제를 크기가 더 작은 문제들로 쪼개어, 작은 문제들을 먼저 해결한 뒤 그 결과들을 이용해서 원래의 큰 문제를 해결하는 기법을 의미한다. 정리하면, Dynamic Programming에서의 핵심은 문제를 잘개 쪼개 조그마한 단위에서의 해결 방법을 구해(점화식) 그것이 최종적인 솔루션과 같은 형태로 구성될 수 있도록 설계하는 것이다. 동적계획법 문제풀이의 예시 - 점화식 동적계획법은 점화식만 구하면 된다. 아주 간단한 피보나치 수열의 경우로 예를 들어보자. n-1번째 수와 n-2번째 수의 합이 n번째 수가 되므로, 재귀를 이용하거나 배열에 저장하는 형태로(즉 초기에 답을 구해놓은 ..

그래프 탐색 개념 및 유형 그래프 탐색 문제 기본 해결 방법 문제가 NxM 형태의 격자 형태를 띄거나, 노드 & 간선의 형태로 그래프 및 트리의 형태를 갖게 되는 경우 그래프 탐색 및 최단경로 탐색 알고리즘을 문제 해결 알고리즘으로 염두에 두어야 한다. 관련 유형 문제로는 아래와 같은 예시를 들 수 있다. 프로그래머스 코딩테스트 페이지를 참고하자. 알고리즘 Breadth First Search를 통해서는 노드를 탐색할 때 같은 깊이의 노드들을 같이 탐색하므로(큐를 이용하기 때문), answer을 탐색할 때 최소깊이/최소간선 수 를 보장하지만, 그래프의 깊이가 깊고 큰 그래프의 경우 공간복잡도가 커질 우려가 있다. 코딩테스트 선에서는 크게 고려할 필요는 없다. 격자 형태를 띄는 문제에, 시작 지점으로부터 ..

문제 설명 https://www.acmicpc.net/problem/1325 A->B 라는 방향이 주어지는 그래프이며, 이 관계에서는 B가 A를 신뢰한다, B 입장에서 A를 해킹할 수 있다, 즉 B가 기준이 되는 문제이다. B 기준에서 연결된 노드의 개수가 몇 개인가, 노드별로 구분해서 카운트하고 정렬하는 문제이다. 방향 그래프 + 탐색 + 정렬 의 간단한 응용문제이나, 기계적으로 문제들을 풀었다면 사소한 부분들에서 헷갈리기 쉬운 문제이다. 문제풀이 시도 1 도착지점의 노드가 중요한 문제이므로, A B 라는 인풋이 주어졌을 때, A를 기준으로 graph를 그리지 않고, B를 기준으로 그래프를 그렸음(push_back을 거꾸로 했다는 의미) B 기준에서 연결된 노드의 개수를 세는 문제와 동일하다. B 기준..

문제 설명 https://www.acmicpc.net/problem/2294 Dynamic Programming의 정석과도 같은 문제 유형 중 하나이다. 주어진 동전의 가치로 목표 가치를 달성하기 위해 필요한 최소의 동전 개수를 계산하기 위해 다이나믹프로그래밍으로 접근해야 한다. 문제에 따라서 완전탐색 등의 다른 방식으로도 접근이 가능하나, 해당문제는 조건에 의해 시간복잡도를 계산해서 제한 시간 안에 계산이 가능한지 확인한 후, 완전탐색으로는 불가능하다는 점을 인식해야 한다. 문제 풀이 시도 및 문제점 고찰 첫 번째 아이디어: 목표 가치(ex. 15)까지의 크기를 갖는 배열을 생성한 후, 0부터 해당 목표 index까지의 최소 동전 개수를 하나씩 계산해서 배열을 채워나가는 방식을 구상하였으나, 주어진 동..

나는 지금 매우 느리게 움직이고 있다. 무엇을 목표로 하고 공부할 지 고민하기로 한 지 몇 주가 지났는지 모르겠다. 7월은 약간의 휴식과 코딩테스트를 위한 기초 문제풀이를 진행했고, 8월은 본격적으로 근로장학을 시작했고 조금은 맹목적으로 코딩테스트 대비 문제풀이를 진행했다. 그 전부터 조금씩 고민을 계속해왔지만, 집중하지 못했다. 8월말이 되어서야 나의 어떤 능력으로 경제활동을 할 수 있을지 고민했지만, 여전히 주의가 흐트러졌었다. 쉽게 다른 곳으로 눈을 돌리게 되었다. 그러고는 벌써 9월의 절반이 지나갔다. 고민하기 싫었다. 대학원으로 진학하며 이런 고민들을 유예하고 싶었다. 나는 지금까지 진행해본 프로젝트를 내 손으로 제대로 완성시켜본 적이 없었다. 두렵다. 허황된 자신감만 있는건 아닌지. 결국 아직..