전체 글

문제 설명 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()) # 데이터의 개수가 많지 않..

지수 표현 방식 파이썬에서는 e나 E를 이용해 지수 표현 방식을 이용 가능하다. 유효숫자e^지수 = 유효수자 x 10^지수 e나 E 다음에 오는 수는 10의 지수부를 의미한다. 예를 들어 2e9라고 입력한다면, 2*10^9를 의미한다. 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단거리를 무한(INF)로 설정하곤 한다. 지수표현 방식은 실수형 데이터로써 처리된다. 실수형 주의점 10진수 체계에서는 0.3과 0.5를 더한 값이 0.8로 딱 떨어지지만, 2진수 체계에서는 정확히 표현할 수가 없다. (미세한 오차 발생) python에서의 나누기 결과는 실수형으로 반환된다. num = 0.3 + 0.5 print(num) # 0.79999999999999 출력 따라서 round() 함수를 이용해 반..

복잡도 : 알고리즘의 성능을 나타내는 척도, 일반적으로 낮을수록 좋은 알고리즘 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 빅오 표기법 : 가장 빠르게 증가하는 항(함수의 상한)만을 표기 O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^n) num = [1,2,3,4] sum = 0 for i in sum: sum+=i print(sum) # 수행 시간은 데이터의 개수 N에 비례하므로 시간 복잡도는 O(N) arr = [1,2,3,4] for i in arr: for j in arr: sum += i+j print(sum) # 시간 복잡도: O(N^2) ..