개발개굴🐸

정렬이란? 컴퓨터 과학에서 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다. 오름차순 정렬 : 1, 2, 3, ..., n-1, n 내림차순 정렬 : n, n-1 ... 3, 2, 1 알고리즘 복잡도 계산 정렬 알고리즘은 매우 다양하기 때문에 각각의 효율성을 비교하기 위해 알고리즘 복잡도를 계산합니다. 시간 복잡도 : 알고리즘 실행 속도 (시간 효율성) 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 (메모리 공간 효율성) 이러한 시간/공간 복잡도를 나타내는 방법으로 빅오(Big-O), 빅오메가(Big-Ω), 빅세타(Big-Θ) 표기법이 있습니다. 빅오 표기법(big-O notation)이란? 빅오 표기법은 알고리즘의 효율성을 표기해주는 기법으로 상한선 기..

[문제] https://www.acmicpc.net/problem/14943 14943번: 벼룩 시장 벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이 www.acmicpc.net [풀이] +값은 판매 배열(sale[]), -값은 구매 배열(buy[])에 각각 저장한 후 투포인터를 활용하여 문제를 해결하였습니다. 1. info[]에 담겨있는 벼룩 시장 정보들을 sale과 buy에 [금액, index] 형태로 저장합니다. 2. 판매 정보와 구매 정보로 투포인터를 진행합니다. buy의 위치를 저장한 left 변수와, sale의 위치를 저장한 right 변수를 각각 0으로..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/17682 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제의 핵심은 정규식을 활용해 S,D,T,*,#와 같은 연산자와, 숫자를 분리하는 것입니다. 예시 1번 1S2D*3T를 예를 들면 다음과 같이 분리할 수 있습니다. 숫자를 [1, 2, 3]으로 분리(num[]) => dartResult.split(/[S|D|T|*|#]/).filter((e) => e !== '').map(Number) 연산자를 [S, D*, T]으로 분리(opt..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/42894 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 초기 세팅 1. 각 블록으로 만들 수 있는 직사각형의 좌표와 블록번호를 저장합니다. block 배열에 [블록번호, x1, y1, x2, y2]형태로 저장합니다. 이때 해당 블록은 다음과 같습니다. (x1, y1) (x1, y2) (x2, y1) (x2, y2) block 배열의 어느 index에 블록번호가 저장되어 있는지 확인하기 위해 Map을 활용해 (key = 블록번호, va..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제의 핵심은 이분탐색을 통해 회전판이 몇번째 돌았을 때 k+1초가 되는지 찾아야 합니다. 예를 들어 회전판이 [3, 1, 2]이고 k가 5라면 k+1인 6초에 어떤 그릇을 먹는지 찾아야 합니다. 1회전 : [2, 0, 1] -> 3초 지남 2회전 : [1, 0, 0] -> 5초 지남 3회전 : [0, 0, 0] -> 6초 지남 따라서 3회전에 6초가 포함되어 있으므로 3회전을 ..

[문제] https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net [풀이] BFS를 통해 바이러스를 퍼트립니다. 초기 세팅 village : 마을 정보 저장 virus: [x좌표, y좌표, 바이러스 타입] 형태로 바이러스 정보 저장 checkOut(x, y) : 마을을 벗어난 위치면 true, 마을 안에 있다면 false를 반환 풀이 과정 bfs를 통해 갱신되는 바이러스 정보를 virus에 저장하며 모두 검사합니다. 이때 주의할 점은 동시간대..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 1. level 배열에 현재 스테이지(레벨)에 도달한 플레이어 수를 저장합니다. 2. clear 변수에 마지막 레벨까지 클리어한 플레이어 수를 저장합니다. 마지막 레벨까지 클리어한 플레이어 수 = level[N+1] 3. fail 배열에 [스테이지, 스테이지 실패율] 형태로 모든 스테이지의 실패율을 저장합니다. 만약 현재 스테이지가 i라면, 실패율 = (현재 스테이지에 있는 플레..

[문제] https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net [풀이] 단순히 DFS를 통해 선수 배치가 가능한 모든 조합을 완전 탐색하는 문제였습니다. 1. position 배열에 각 선수들의 가능한 포지션과 능력을 저장합니다. position의 i번째 배열에 [가능한 포지션, 능력] 형태로 push합니다. 따라서 예제의 position 정보를 모두 저장하면 다음과 같습니다. [ [ [ 0, 100 ] ], [ [ 1, 80 ], [ 2, 70 ], [ 3, 70 ], [ 4..