Algorithm

[Python] BOJ 1300. k번째 수

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 예제 해석 A : 3x3 1 2 3 1 1 2 3 2 2 4 6 3 3 6 9 B : len(B) = 9 = 3x3 1 2 2 3 3 4 6 6 9 출력값 : B[7] = 6 - 임의의 숫자 m을 골라서 k번째 숫자인지 판단해보는 문제 - m을 이분 탐색으로 찾아보자 : m은 O(logK) - m보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있는가 - A[i][j]에서..

[Python] 보석쇼핑

https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 투 포인터 알고리즘을 사용! 1. 먼저 배열 인덱스를 저장하는 start 변수와 end 변수를 선언 2. 배열의 start 와 end 구간이 “모든 종류의 보석을 포함하는 구간”이 될 때 까지 end 인덱스를 증가 진열대 번호 : 1 2 3 4 5 6 7 8인덱스 번호 : 0 1 2 3 4 5 6 7보석의 종류 : D R R D D E S D start = 0 end = 0 구간안..

[Python] 수식 최대화

programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 파이썬 코드 # 우선순위가 낮은 기호를 기준으로 split() def calc(priority, n, expression): if n == 2: # 마지막 인덱스일 경우 기호 상관없이 eval()에서 연산 수행하면 됨 return str(eval(expression)) if priority[n] == '*': res = eval('*'.join([calc(priority, ..

[C++] 키패드 누르기

programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr ver 1.0 거리계산 배열 이용하기 github.com/jiminAn/Algorithm/blob/master/etc/Programmers_2020_kakao_Internship1_ver1.0.cpp jiminAn/Algorithm SW Expert Academy 알..

[C++] 점프와 순간이동

programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈� programmers.co.kr c++ 코드 #include using namespace std; int solution(int n){ int tmp, ans; ans = 1;// 순간이동을 하기 위해서는 최초 1칸은 이동 while( n != 1){ tmp = 0; // 입력받은 길이가 홀수 일 경우 teleport후 jump 1번을 더 해줘야 하므로 비용 1 증가 if( n % ..

[C++] BOJ 1051. 숫자 정사각형

www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net #include #include #include #include using namespace std; int n,m; int rec[51][51]; vector square; vector column; vector tmp_square; int check_square(int start_row, int start_column);// 인덱스 별 가장 큰 정사각형 사이즈를 리턴해주는 함수 int main(void)..

[C++] BOJ 4386. 별자리 만들기

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일� www.acmicpc.net 크루스칼 알고리즘 이론 참고 codingsmu.tistory.com/11?category=871718 [Algorithm: 알고리즘] 05 Greedy Algorithm 목차 0. Basics: 그리디 알고리즘 기초 1. Minimum Spanning Trees : 최소 신장 트리 - 신장 트리 - 최소 비용 신장 트리 - Kruskal's Algorithm( Original ver.) : 크루스칼 알고리즘 -..

[C++] BOJ 7576. 토마토

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제 설명 : 예제가 아래와 같이 들어온다면 아래의 토마토 일 수 변화과정으로 6일이 결과값으로 도출됨을 확인할 수 있다 #include #include #include #include using namespace std; int dy[4] = {0,0,1,-1}; int dx[4] = {1,-1,0,0,}; int n,m; int box[1000][1000]; queue start_point..