알고리즘

Python으로 ps를 진행하는 사람이 많아짐에 따라 이 기능이 필요하다고 생각되어 포스팅 남깁니다. 예시용 코드 여러분께서는 문제를 풀 때 습관처럼 작성하시는 코드가 있으실까요?? import sys input = sys.stdin.readline 위의 코드는 Python에서 값을 입력받을 때 조금이라도 더 향상된 속도로 받을 수 있도록 세팅해 주는 코드죠. 일반 input() 대신에 sys.stdin.readline()으로 입력받도록 설정합니다. 습관처럼 매번 모든 문제에 저런 코드를 작성하시는 분이라면 기존에 작성하신 코드에서 복사 붙여넣기 하시거나 손으로 하나하나 타이핑하시겠죠. Pycharm에서 파이썬 파일을 하나 생성하면 자동으로 저런 코드가 들어가면 편해지지 않을까요?? Pycharm Tem..

https://www.acmicpc.net/problem/17547 17547번: Floor Plan You are an architect and you have just been appointed to build a new swimming hall. The organisation behind these plans has acquired funding for a swimming pool and surrounding building as large as they want, but unfortunately they could not find anyone wi www.acmicpc.net 영어로 된 문제지만 쫄지마세요. n이 주어졌을때 $$ n = m^2-k^2 $$ 위 수식을 만족하는 m과 k를 구하면 됩니..

programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 2021년 상반기 웹 백엔드 개발 데브 매칭에 출제된 문제입니다. 그때도 푼 기억이 있는 문제인데, 다시 풀려니까 코드를 더럽게 짰다만 기억나고 디테일한 부분은 기억이 안나서 다시 풀어봤습니다. 문제 요약 lottos는 내가 보유한 로또 번호 win_nums는 당첨 로또 번호입니다. lottos 배열의 0은 지워져서 알 수 없는 ..

programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 오늘의 문제입니다. 수식 문자열이 주어지면 (+,-,*)연산의 우선 순위를 능력껏 수정해서 최대값을 계산하라는 문제입니다. 문제 접근 저 같은 경우에는 일단 "100+200"이 있으면 100,+,200 씩 나누도록 분리했습니다. test = expression.replace('-',' - ').replace('+',' + ').replace('*',' * ').split()..

ps 거의 한 달만인가요 허허 토요일에 코딩테스트가 있어서 급하게 벼락치기로 준비해봅니다. 합격하면 좋고 합격을 못하더라도 예전보다만 제발 잘 봤으면 좋겠습니다. 어쨋든 오늘 풀 문제는 2021년 카카오 공채 코딩테스트 1번 문제였던 신규 아이디 추천 문제입니다. programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 접근 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳..

문제 링크 www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 요약 '('와 ')'로 이루어진 문자열로 레이저와 쇠막대기의 배치 정보를 준다면 쇠막대기 조각의 총 개수를 구하라. 문제 풀이 문제 속의 그림에 다른 정보들을 추가해보겠습니다. 쇠막대기에 적혀진 숫자들은 잘려진 조각을 세기 위한 숫자입니다. 그 위쪽 괄호와 근접하게 적힌 숫자들은 무엇일까요?? 괄호가 열린 만큼 쇠막대기들이 겹쳐서 쌓여있게 됩니다. 즉 몇겹이 쌓아 올려져 있는지 적어놨습니다. 레이저를 만나..

https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 문제 요약 입력받은 값으로 만들어낼 수 있는 수가 30의 배수라면 그중 가장 큰 값을, 배수가 아니라면 -1을 출력하라. 접근법 문제 분류를 보면 정수론이라고 되어있습니다. 위키 피디아에 따르면 '정수론(整數論, 영어: number theory) 또는 수론(數論)은 수학의 한 분야로, 각종 수의 성질을 대상으로 한다' 라는 군요. 30의 특성을 파악해봅시다. 30은 일단 뒤에 0이 없으면 안 되..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 문제 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의..

기수 정렬 기수 정렬은 배열 안의 데이터가 모두 n자릿수 이하의 자연수인 경우 사용 가능한 정렬이다. 일의 자릿수로 크기 비교후 정렬하고 다음은 십의 자리, 백의 자리,...해서 n자릿수까지 크기를 비교하는 독특한 정렬이다. 시간 복잡도는 O(dn)으로 빠른 편이다. 다만 테이블이 따로 필요하다는 단점이 있다. 기수 정렬이 어떤 순서로 동작하는지는 아래의 영상에 나와있다. https://youtu.be/nu4gDuFabIM import java.io.*; import java.util.*; class Radix { static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; int i; int count[] = new int[..

퀵정렬은 병합 정렬처럼 분할 정복 알고리즘에 속하지만 병합 정렬과는 달리 불안정 정렬이다. 배열에 있는 값중 아무거나 하나를 pivot으로 정한다. 이를 값을 기준으로 pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬한다.(오름차순 정렬) 이렇게 pivot을 기준으로 왼쪽과 오른쪽으로 분할된 배열로 위의 과정을 반복한다. 퀵 정렬의 시간 복잡도는 O(nlogn)으로 병합 정렬과 동일하다. import java.util.Random; public class Quick { public static void quickSort(int[] a,int p,int r) { int q; if(p