어떤 양수 n0, c이 존재할 때 f(n)은 O(g(n))입니다. 이때, n0과 c는 다음을 만족해야 합니다.n0 이상의 모든 n에 대해 f(n) <= cg(n)쉽게말해,n은 O(n)다. n0=1, c=1이기만 해도 n <= n이 만족하므로2n 역시 O(n)
'모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘'을 뜻한다.가장 강력하고 확실한 방법이지만 그만큼 시간이 가장 오래 걸리는 탐색기법이다.Brute-force 비트 마스크순열백트래킹DFS, BFS이 페이지에서는 Brute-force에 대해 다룰 예정.'브루트 포스'
개념 >서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다. 거품이 물위로 떠오르는 모습과 흡사하다 하여 거품정렬 구체적인 개념 첫 번째와 두 번째, 두 번째와 세 번째, 세 번째와 네 번째 ... 이런식으로 (마지막-1), 마지막을 비교하...
개념 제자리 정렬 - 추가 메모리 필요없음 최솟값을 찾아서 맨앞과 교체 맨앞 빼고 다시 최솟값 찾아서 반복 구체적인 개념 >선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 ...
개념 >한 장을 뽑아 앞 자료들과 비교하며 제자리를 찾아간다. key 값은 두 번째 자료부터 구체적인 개념 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료...
https://programmers.co.kr/learn/courses/30/lessons/12977주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫
N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시
https://programmers.co.kr/learn/courses/30/lessons/49994게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.U: 위쪽으로 한 칸 가기D: 아래쪽으로 한 칸 가기R: 오른쪽으로 한 칸 가기L
https://programmers.co.kr/learn/courses/30/lessons/49993선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼
N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g
N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼
문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. words에 있는 단어로
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 1, 1, 1, 1, 1로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.\-1+1+1+1+1 = 3\+1-1+1+1+1 = 3\+1+1-1+1+1 = 3
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상
문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수
https://programmers.co.kr/learn/courses/30/lessons/43164주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질
https://programmers.co.kr/learn/courses/30/lessons/43238n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한
https://programmers.co.kr/learn/courses/30/lessons/42884고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.고속도로를 이동하는 차량의 경로 routes가
https://programmers.co.kr/learn/courses/30/lessons/427460 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 6, 10, 2라면 6102, 621
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데
https://programmers.co.kr/learn/courses/30/lessons/17679블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".같은 모양의 카카오프렌즈 블록이 2
https://programmers.co.kr/learn/courses/30/lessons/17683라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다.
문제설명은 너무 길어서 링크 참조바람 https://programmers.co.kr/learn/courses/30/lessons/72412 풀이(효율성 0점) info와 query를 스플릿해서 리스트로 저장하고 set이 5개 묶여있는 리스트를 쿼리수만큼 만든다 쿼리
https://programmers.co.kr/learn/courses/30/lessons/49189n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.예를들면, 문자열 s가 "abcdcba"이면 7을
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다
Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방
문제가 길어서 링크로 대신한다. https://programmers.co.kr/learn/courses/30/lessons/42627 풀이 운영체제 시간에 배운 스케쥴러가 생각났다. 우선 순위 큐를 사용하는 문제인것은 확실하고 우선 jobs를 요청시간 순으로 정렬해
https://programmers.co.kr/learn/courses/30/lessons/64064개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는(1칸, 1칸, 1칸, 1칸)(1칸, 2칸, 1칸)(1칸, 1칸, 2칸)(2칸, 1칸, 1칸)(2칸, 2칸)의 5가지 방법으로 맨 끝 칸에 도
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.타일을 가로로 배치 하는 경우타일을 세로로
https://programmers.co.kr/learn/courses/30/lessons/42885무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.예를 들어, 사람
https://programmers.co.kr/learn/courses/30/lessons/42839한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열
https://programmers.co.kr/learn/courses/30/lessons/42883어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 19, 12, 14, 9
https://programmers.co.kr/learn/courses/30/lessons/42577전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호
https://programmers.co.kr/learn/courses/30/lessons/86053어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b
https://programmers.co.kr/learn/courses/30/lessons/72413본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이
https://www.acmicpc.net/problem/9663N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 N이 주어진다
https://www.acmicpc.net/problem/11000수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다
https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를
https://programmers.co.kr/learn/courses/30/lessons/60057데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에
https://programmers.co.kr/learn/courses/30/lessons/87946XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해
https://programmers.co.kr/learn/courses/30/lessons/84512사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단
https://www.acmicpc.net/problem/11053수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은
https://www.acmicpc.net/problem/2206N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데,