Algorithm
-
[Algorithm] - Bit연산자 부분 집합Algorithm/Algorithm 2022. 9. 7. 16:44
Bit 연산자 Bit연산자로 표현하는 방법을 나타보도록 하겠습니다. 프로그래머스 - 후보키 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N이 어떤 집합의 원소 갯수라고 합니다. 특정 부분 집합에 대해 특정 원소가 들어간다 or 들어가지 않는다로 나누어집니다. 이를 원소 갯수만큼 반복하여 생각하면 됩니다. 만약 4가지를 경우의 수로 나타나고 싶다면 각 Index가 표현된 방법을 의미하여, 0001 - 1111로 나타날 수 있다. 그렇기 ..
-
[프로그래머스] - 등굣길Algorithm/프로그래머스 2022. 9. 7. 15:42
문제 [프로그래머스] - 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 ..
-
[프로그래머스] - 이중우선순위큐Algorithm/프로그래머스 2022. 9. 5. 16:09
문제 [프로그래머스] - 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어..
-
[프로그래머스] - 네트워크Algorithm/프로그래머스 2022. 9. 5. 16:04
문제 [프로그래머스] - 네트워크 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 ..
-
[Algorithm] - 문자열 알고리즘 (KMP 알고리즘)Algorithm/Algorithm 2022. 9. 5. 14:07
문자열 탐색 문자열을 검색하는 상황은 많은 상황에서 쓰입니다. 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 Ctrl+F 를 눌러서 검색 시 사용될 수 있습니다. 본문에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니다. 문자열 검색이라고 생각하면 됩니다. 1. 일반적인 생각 ( Brute-Force ) 본문 문자열의 길이를 M, 패턴의 길이를 N이라 가정 시간 복잡도 : O(NM) 2. KMP 알고리즘(Knuth Morris Partt Algorithm) 접두사와 접미사가 같은 부분부터 다시 매칭하면 된다라는 아이디어 시간 복잡도 : O( N+M ) 1) 접두사( Prefix ) banana -> b / ba / ban / bana ..
-
[Algorithm] - LIS(최장 증가 부분 수열)Algorithm/Algorithm 2022. 9. 5. 13:57
LIS 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열 E.g) [3, 5, 7, 9, 2, 1, 4, 8] 부분 수열 -> [3, 7, 9, 1, 4, 8] / [3, 5, 7, 8] / [1, 4, 8] 길이가 길면서 원소가 증가하는 최장 부분 수열-> [3,5,7,8] 알고리즘 1. DP 각 원소를 돌면서 현재 원소보다 작은 값들(DP) 중 가장 큰 값에다가 연결 각 원소를 돌때마다 하위 원소들에 대해서 완전 탐색이 필요하여 O(N^2) 시간 복잡도 #Init dp = [0]*(n+1); for i in range(n) : for j in range(i) : dp[i] = max(d..
-
[Algorithm] - 정렬Algorithm/Algorithm 2022. 9. 2. 14:06
알고리즘이란? 가정 : 정렬할 데이터가 담긴 배열(리스트)의 각 원소를 O(1) 시간에 접근 가능한가? 결과 : C , Python과 같은 배열인 경우 가능 하지만, 그렇지 않은 경우가 있다. 데이터가 HDD 에 있다면 ? 메인 메모리에 올라와 있어야만 이 가정이 통한다. 정렬 1. 버블 정렬 시간 복잡도 : O(N^2) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환 이 과정을 다시 나머지 n-1개 수에 대해서 반복 2. 삽입 정렬 시간 복잡도 최악의 경우 : O(N^2) , 최상 O(N) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 정렬 대상이 될 원소를 두 부분으로 나눔 앞은 '이미 정..
-
[프로그래머스] - 순위Algorithm/프로그래머스 2022. 9. 2. 13:19
문제 [프로그래머스] - 순위 https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다..