본문 바로가기

코딩테스트38

그리디 알고리즘 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까? 아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다. 하지만 그리디 알고리즘은 어떻게 갈까? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다. 루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 .. 2023. 10. 22.
코딩테스트 준비 - 파이썬 문법 정리 파이썬의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 정수형 정수를 다루는 자료형 양의 정수, 0, 음의 정수가 포함 실수형 소수점 아래의 데이터를 포함하는 수 자료형 소수부가 0일 때 0 생략 가능 지수 표현 방식 파이썬에서는 e나 E를 이용한 지수 표현 방식 이용 e, E 다음에 오는 수는 10의 지수부를 의미 ex) 1e9 -> 10의 9제곱(1,000,000,000). 1 x 10^9 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대해 최단 거리를 무한(INF)로 설정하곤 함 이때 가능한 최댓값이 10억 미만이라면 무한(1NF)의 값으로 1e9를 이용할 수 있음 # 1,000,000,00의 지수 표현 방식 a = 1e9 print(a)// 1000000000.0 #752.5.. 2023. 10. 22.
코딩테스트 준비 - 알고리즘 성능 평가 복잡도란? 시간 복잡도: 특정 크기의 입력에 대해 알고리즘의 수행 시간 분석 공간 복잡도: 특정 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 시간 복잡도가 높다 -> 알고리즘 실행에 오랜 시간이 걸린다 공간 복잡도가 높다 -> 알고리즘 실행에 많은 메모리가 사용된다 빅오 표기법 가장 빠르게 증가하는 항만 고려하는 표기법 ex) 연산 횟수가 3N^3 + 5N^2 + 1,000,000 이면 시간 복잡도는 O(N^3) 알고리즘 설계 팁 연산 횟수가 5억을 넘어가는 경우: - C언어: 1~3초 가량 시간 소요 - Python: 5~15초 가량 시간 소요 코딩테스트 문제에서 시간제한은 통상 1~5초 가량 수행 시간 측정 소스코드 예제 import time start_time = time.time() # 측정.. 2023. 10. 21.
SWEA - 스도쿠 검증(1974) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다. 같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다. 입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다. [제약 사항] 1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다. 2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다. 접근방식 arr.. 2023. 10. 21.
SWEA - 어디에 단어가 들어갈 수 있을까(1979) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다. 주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라. [예제] N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때 길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다. [제약 사항] 1. N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15) 2. K는 2 이상 N 이하의 정수이다. (2 ≤ K ≤ N) 접근방식 0과 1로 이뤄진 NxN 배열이 주어지면 연속된.. 2023. 10. 21.
SWEA - 지그재그 숫자(1986) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 1부터 N까지의 숫자에서 홀수는 더하고 짝수는 뺐을 때 최종 누적된 값을 구해보자. [예제 풀이] N이 5일 경우, 1 – 2 + 3 – 4 + 5 = 3 N이 6일 경우, 1 – 2 + 3 – 4 + 5 – 6 = -3 [제약사항] N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10) 접근 방식 N이 주어지면 1~N까지의 숫자 중 홀수는 그대로 더해주고 짝수는 그 짝수값에 -를 붙여서 전체를 더하는 문제 N을 입력받으면 arr에 1~N까지의 숫자를 넣어줌 그리고 arr를 돌면서 각 인덱스의 값이 2로 나눠지면(짝수) ans_arr에 (해당 값-2*해.. 2023. 10. 19.

티스토리툴바