문제 https://school.programmers.co.kr/learn/courses/30/lessons/181893 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 인덱스가 헷갈려서 노트에 적어가며 풀었다. 접근 방법 1 매 query 작업마다 배열을 갱신한다. 한 작업마다 O(N)의 시간이 소요된다. 시간이 오래 걸리고 코드가 복잡해진다. 접근 방법 2 단순하게 매 작업마다 시작점 포인터(start)와 끝점 포인터(end)를 갱신 한다. 한 작업마다 O(1)의 시간 이 소요된다. 시간 소요가 적고 코드도 간단하다. 이후 포인터를 이용해 필..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 "하노이의 탑"은 규칙이 존재하는 대표적인 재귀 문제다. 점화식을 세워서 설계하면 쉽게 구현할 수 있다. (출발지, 경유지, 도착지) 3개의 위치를 선언한다. "N개, 출발지 -> 도착지"의 경우 "N-1개, 출발지 -> 경유지" + "1개, 출발지 -> 도착지" + "N-1개, 경유지 -> 도착지"의 규칙을 가진다. 이를 점화식으로 표현하고 코드로 구현한다. 풀이 이동 정보를 저..
문제 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 접근 방법 무작정 구현을 시작했는데 해결하지 못했다. 이후 검색을 해보며 힌트를 얻었다. 비트마스킹을 이용한 풀이방법밖에 찾지 못했다. 나는 비트마스킹을 잘 모르기에 비트마스킹을 사용하지 않고 그냥 빡세게 구현했다. 원리는 이렇다. 같은 스위치를 여러 번 누르지 않는다. 같은 행위를 반복하면 최적의 해를 구할 수 없다. 완전 탐색으로 100개의 전구를 켜고 끄는 경우를 찾으면 O(..
문제 https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 접근 방법 비슷한 유형의 문제를 풀었던 기억이 있다. 처음에는 무지성으로 구현을 시도했고 실패했다. 이후 나름의 규칙으로 구현을 시도했으나 실패했다. 마지막으로, 이전에 정규식을 이용했던 것이 생각나 적용했더니 너무 간단하게 풀렸다. 풀이 문자열.matches() 내장 함수를 사용한다. matches의 인자로 정규식을 넣는다. "(100+1+|01)+"를 사용했다. A+ "반복"을 표현하며 ..
암호화 알고리즘 암호를 만드는 알고리즘이다. 용어 평문(Plaintext) : 해독 가능한 형태의 메시지(암호화 전 메시지) 암호문(Cipertext) : 해독 불가능한 형태의 메시지(암호화된 메시지) 암호화(Encryption) : 평문을 암호문으로 변환하는 과정 복호화(Decryption) : 암호문을 평문으로 변환하는 과정 전자서명 송신자의 Private Key로 메시지를 서명하여 전달 수신자측에서는 송신자의 Public Key를 이용하여 서명값을 검증 양방향 암호화 암호화와 복호화과정을 통해 송,수신간 주고받는 메시지를 안전하게 암,복호화하는 과정 단방향 암호화 해싱(Hashing)을 이용한 암호화 방식으로 양방향과는 다른 개념이다. 평문을 암호문으로 암호화는 가능하지만 암호문을 평문으로 복호화 ..
MST(Minimum Spanning Tree 최소 신장 트리) 신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다. n개의 점을 (n-1) 개의 간선으로 연결한다. 최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다. Prim(프림) 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다. 수행 과정 임의의 정점을 시작 지점으로 선택 연결된 모든 간선의 가중치를 비교 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록) 모든 정점이 연결될 때까지 2~3번 과정 반복 시간복잡도 V : 정점의 개수 E : 간선의 개수 우선순위 큐로 구현 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV) 각 노드에서..
재귀함수(Recursion) Stack 개념을 이용해 자기 자신을 다시 호출하며 반복하는 함수이다. 구성 탈출 조건, 연산, 재귀 호출로 이루어진다. 탈출 조건을 잘못 설정하면 Stack Overflow가 발생한다. public static int rSum(int n){ // 탈출 조건 if(n == 0) return 0; // 재귀 호출 return n += rSum(n-1); } 장점 가독성을 높일 수 있다.(재귀적인 표현이 자연스러운 경우) 단점 호출이 많아질수록 Stack에 쌓여 메모리 사용량이 계속 증가한다. Stack Overflow가 발생할 수 있다. 재귀함수 사용 예시 피보나치 수열, 팩토리얼 구하기 분할 정복 알고리즘 이진 탐색 하노이의 탑 백트래킹 알고리즘 Tail Recursion(꼬..
그리디 알고리즘(Greedy Algorithm) 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않음 최적 부분 구조(Optimal Substructure) 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다 특징 전체 상황에서의 최적의 결과를 보장하지 못한다. 속도가 매우 빠르다 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등 동적 계획법(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 조건 겹치는 부분 문제(Overlapping Subproblems)..
Binary Search(이진탐색) 정렬된 배열, 이진 트리에서 특정한 값을 찾아내는 알고리즘이다. 정렬이 전제되어 있어야 한다. 한번 비교를 거칠 때 탐색 범위가 1/2로 줄어든다. 범위의 중앙 값과 비교한다. 찾는 값이 중앙 값보다 작다면 왼쪽(그림 : 내림차순 정렬이므로 오른쪽) 1/2의 범위에서 탐색한다. 찾는 값이 중앙 값보다 크다면 오른쪽(그림 : 내림차순 정렬이므로 왼쪽) 1/2의 범위에서 탐색한다. 1번/2번 해당하는 작업을 반복한다. 찾는 값이 중앙 값이면 탐색을 종료한다. 기본 형태의 Java 코드 int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // high가 low보..
등장 배경 코드의 성능, 효율성을 판단할 기준이 필요했다. 실제 실행시간과 메모리 사용량을 측정한다면? 하드웨어의 성능, 소프트웨어(운영체제)의 성능, 호환성 등 외부 요인이 작용하여 동일한 기준으로 비교할 수 없다. 미완성 코드는 실행이 불가능하므로 측정이 불가능하다. → 다른 요인과 무관하게 입력 크기에만 영향을 받는 이론적 시간 측정 방법을 만들었다. 시간복잡도 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 점근 표기법을 이용하여 나타낸다. 💡 점근 표기법이란, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법을 말한다. 단위 연산의 횟수를 기준으로 계산한다. 💡 단위 연산(primitive operation)이란, 정의, 단순 계산, 비교, 출력 등의 가장 간..
