🔊 본 포스팅의 내용은 나동빈님의 [이것이 취업을 위한 코딩테스트다] 유튜브 강의를 수강 후 정리한 내용을 기록한 글로, 모든 사진과 자료의 출처는 해당 영상에 있습니다. 훌륭한 강의로 지식을 전달해 주신 나동빈님께 감사의 말씀을 전합니다. 목차 정렬 알고리즘 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 정렬 알고리즘 비교하기 정렬 알고리즘 예제 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 선택 정렬 동작 예시 선택 정렬은 반복시마다 탐색 범위가 줄어듭니다. 선택 정렬 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 ..

문제 설명 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬해 출력한 뒤, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. # 입력 조건 첫째 줄에 하나의 문자열 S가 주어진다. ( 1

문제 설명 8x8 좌표평면의 특정 한 칸에 나이트가 서 있다. 나이트는 특정위치에서 다음과 같은 2가지 경우로 이동 할 수 있다. - 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 - 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 나이트의 위치가 주어졌을 때 나이트가 이동 할 수 있는 경우의 수를 출력! 행 위치는 1~8, 열 위치는 a~h로 표현 # 입력 조건 첫째 줄에 나이트의 위치가 주어진다. # 출력 조건 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력한다. 입력 예시 출력 예시 a1 2 문제 해결 아이디어 나이트의 8가지 경로를 하나씩 확인하여 각 위치로 이동이 가능한지 확인 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의 풀이 : input_data = input()..

문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. # 입력 조건 첫째 줄에 정수 N이 주어진다. ( 0=6: continue if (i%10)==3 : cnt+=1 continue elif (i//10)%10==3 : cnt+=1 continue elif (i//100)%10==3 : cnt+=1 continue elif (i//1000) %10==3 : cnt+=1 continue elif (i//10000) %10==3 : cnt+=1 continue print(cnt)

구현 ( implementation ) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠 만큼 어려운 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용된다. 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 백터가 자주 활용된다. ( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) ( 1 , 4 ) ( ..

문제 설명 모험가 길드에서 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 위기 대처능력이 떨어집니다. 공포도가 X인 모험간는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다. N 명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램을 작성하세요. # N = 5이고, 각 모험가의 공포도가 [ 2 3 1 2 2 ] 라면 그룹 1에 공포도가 1,2,3인 모험가를 넣고, 그룹 2에 공포도가 2, 2 인 모험가를 넣게 되면 2개의 그룹을 만들 수 있다. 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 입력 예시 출력 예시 5 2 3 1 2 2 2 문제 해결 아이디어 오름 차순 정렬 후 공포도가 낮은 모험가 부터 확..

문제 설명 각 자리 숫자(0~9)로만 이뤄진 문자열 s가 주어졌을때, 왼쪽부터 오른쪽까지 하나씩 모든 숫자를 확인하며 숫자사이에 'X' 혹은 '+' 연산자를 넣어 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 단 모든 연산은 왼쪽부터 순서대로 이루어진다. 문제 해결 아이디어 두 수 중에 하나라도 0 or 1이면 더하기를 수행, 예외 경우는 곱하기수행 풀이 : O(N)의 시간 복잡도 data = input() result= int(data[0]) for i in range(1,len(data)): num=int(data[i]) if num

문제 설명 어떠한 수 N이 1이 될 때 까지 다음 두 과정 중 하나를 반복 선택 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 이때의 최소 수행 횟수를 구하기 풀이 1 : 긴시간이 걸림. O(N)의 시간 복잡도 count=0 def solution(k,n): global count while(n>=2): if n%k==0: n/=k else : n-=1 count+=1 print(count) solution(17,4) 풀이 2: 짧은 시간이 걸림 . O(logN)의 시간 복잡도 count=0 def solution(k,n): global count while True: # N이 K로 나누어 떨어지는 수가 될 때 까지..

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 보르는 방법, 닫순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 꼭 필요! 거스름돈 문제 카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, N은 10의 배수 해결 방법 - 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다. >> N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러주고 이후 단위도 똑같이 반복 - 최적의 해가 보장되는 이유 : 큰 단위가 항상 작은 단위의 배수이기 때문! >> 800원을 ..

문자열 연산 문자열 변수에 덧셈을 이용하면 문자열이 더해져서 연결된다. 문자열 변수를 양의 정수와 곱하는 경우, 그 값만큼 여러번 더해진다. 인덱싱과 슬라이싱이 가능하지만 수정은 불가하다. 튜플 자료형 : 리스트와 유사하지만 아래와 같은 차이가 있다. 한 번 선언된 값을 변경 할 수 없다. 리스트는 [] , 튜플은 () 리스트에 비해 공간 효율적이다. 자주 사용되는 표준 입력 방법 input() 함수는 한 줄의 문자열을 입력받는다. map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용 arr = list(map(int,input().split())) #공백을 기준으로 정수를 입력받아 리스트에 저장 a,b,c = map(int,input().split()) # 데이터의 개수가 많지 않..