결국 빛나리라

성능 시간복잡도 시간복잡도란? 프로그래밍을 할 때는 언제나 비용을 신경써야한다. 그 비용 중 하나가 코드가 돌아가는데 필요한 실행시간일 것이다. 그리고 이러한 실행시간을 시간복잡도라고도 부른다. 시간복잡도를 정확히 예측할 필요는 없지만 그 시간을 개략적으로 예측하는 것은 필요하다. 시간복잡도를 표현할 때는 Big-O기법을 사용하는데, 이는 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 즉, 가장 영향력이 큰 부분에 대해서만 시간 복잡도를 고려하는 것이다. 시간 복잡도는 대표적으로 다음 일곱가지 종류로 나눠볼 수 있다. 시간복잡도(증가함수) 종류 종류(빅오표기법) 명칭 설명 대표사례 문제크기가 100배 커질 때 예상 소요시간 O(1) 상수시간 고정된 수의 문장을 실행하므로 문제의 크기에 따라 시간이 변..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net > 문제 풀이 아이디어 DP로 풀 수 있는 문제이다. 해당 문제에서 dp에는 최대 병사 인원 수가 들어간다. 푸는 논리는 다음과 같다. - 우선 dp를 병사 수만큼 1로 초기화한다. - 1 번째 병사는 0 번째 병사보다 전투력이 작으므로 연산을 수행한다. (0 번째 병사의 인원수 +1) 과 (1번째 병사의 인원 수) 중 큰 값을 dp[1]에 넣어준다. - 2 번째 병사는 0 번째 병사보..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net > 문제 풀이 아이디어 - 스택의 마지막 값이 입력의 첫번째 값보다 작으면 스택에 1씩 증가시킨 수를 추가한다. - 스택의 마지막 요소 값과 입력의 첫번째 값이 일치하면 스택의 마지막 값과 입력의 첫번째 값을 뺀다. - 위 과정을 입력리스트가 빈 리스트가 될 때까지 반복한다. - 만일 스택의 마지막 요소 값이 입력의..

https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 먼저 배열 요소의 이진수를 구한 후 n자리 수를 맞추는 작업을 했다. 두 이진수의 각 자릿수 별 숫자 중 하나라도 1이 있다면 #을 결과 문자열에 추가하도록 했다. * 두 이진수 배열을 bin함수를 활용해 합쳐서 도출할 수 있다. 이진수의 수들 중 둘 중 하나라도 1이면 1을 도출하면 되기 때문에 bin(a1|a2)로 수정 가능하다. * line6-9부분..

https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr left부터 right 수 까지의 모든 수에 대한 약수를 리스트에 추가한 후 리스트 요소의 개수가 짝수이면 answer에 더하고 홀수면 빼는 로직을 구현해야 한다. 이렇게 문제에 나온 논리 그대로 코드를 구현하면 다음과 같다. 구현 자체는 굉장히 쉽지만 다른 사람의 풀이에서 좋은 아이디어를 얻었기에 이를 기억하..

https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr > 정렬 딕셔너리를 선언해서 key값엔 stage 단계, value값엔 실패율을 담은 후, sorted로 정렬했다. 그런데 문제는 sorted에서 dict.items()로 정렬하는 과정에서 딕셔너리가 리스트+튜플 형태로 변하기 때문에, 리스트 내의 튜플에서 stage값만 추출하기 위해 다시 반복문을 돌렸다. * 마지막 스테이지까지 도달한 사람이 없을 경우(마지막..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net > 브루트포스 만약 입력된 사각형이 9*9라면 우리는 다음과 같은 방식으로 총 네가지 경우에서 바꿔 칠해야하는 사각형의 개수를 구해야한다. 반복해야 할 수는 각각 n-7, m-7번이라는 것을 알 수 있다. 4가지 경우에서 W로 시작하는 패턴, B로 시작하는 패턴, 이 두가지 경우의 패턴에 대해 모두 테스트해야한다. 나 같은 경우엔 그냥 반복해야하는 문자열 패턴을 pat1, pat2로 설정해..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net > 그리디 괄호를 추가하여 식의 결과를 '최소'로 만드는 알고리즘을 구현해야한다. '-' 이전의 수들은 모두 더해주고 '-' 이후의 수들을 모두 빼주면 최소 값을 구할 수 있다. 예를 들어, 1+2-3+4-5 에서 '-' 는 두번 나온다. 우선 이 두개를 기준으로 괄호를 넣어주면 다음과 같이 표현된다. 1+2-(3+4)-(5) 그런데 위의 식은 사실상 아래의 식과 같다. (1+2)-(3+4+..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net > 덱 선입, 후입이 모두 가능한 deque 함수로 구현가능하다. 앞으로 넣을 땐 appendleft(), 뒤로 넣을 땐 append() 메서드를 사용한다. * 리스트를 활용한 풀이도 가능하다. 리스트에서 push front 기능을 작성할 때 insert(넣는 위치, 넣을 수) 메소드를 활용할 수 있다.

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net > 정렬 sort 메서드를 활용해 정렬한다. 정렬 조건으로 첫 번째는 단어의 길이, 두 번째는 단어 사전 순으로 설정했다. 같은 단어는 한번만 출력되기 때문에 8 line 이후의 출력 코드에서 if 문을 통해 이전의 단어와 같은 단어이면 출력되지 않도록 작성했다. * 정답으로 통과는 했으나 비효율적인 코드이다. ▶ 배운점 그렇다면 본 코드에서 비효율을 어떻게 개선할 수 있을까? 첫 번째..