취준생의 코딩테스트 연습기

※ SW expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. # 문제 링크 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXfRhBl6KTMDFAS5&categoryId=AXfRhBl6KTMDFAS5&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # Soultion 마지막에 답을 출력할 때, test_case와 answer을..

# 다익스트라 알고리즘 (Dijkstra Algorithm) - 그래프에서 정점끼리의 최단 경로를 구하는 문제 -> 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 문제이다. - 음의 간선이 있을 경우 사용할 수 없다. - 2차원 배열에 처음에는 INF 값을 저장한 뒤, min값을 찾아 수정해준다. # Example programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr

# 동적 계획법 (Dynamic Programming) - Recursive + Memorization - 점화식 찾기! -> 작은 문제의 해를 테이블에 저장한 뒤, 나중에 읽어서 사용 - 상향식 (작은 -> 큰) 하향식 (분할 정복) - 대표적인 예로 피보나치 수열이 있다. # Example - 백준 1003 jiwon-coding.tistory.com/28?category=882771 [백준] 1003번 피보나치 함수 / 파이썬(python) # 문제 링크 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net # Soultion(실패) 재귀를 이용하.. j..

# 백트래킹 (퇴각 검색) - 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행 - 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 # EXAMPLE - 백준 15649 jiwon-coding.tistory.com/21?category=882771 [백준] 15649번 N과 M(1) / 파이썬(python) # 문제 링크 www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 jiwon-coding.tistory.com - 백준 15650 jiwon-coding.tistory.c..

# 문제 링크 programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr # Soultion(실패) 34.4%만 성공 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def solution(N, road, K): answer = 0 li = [0]*(N+1) #0도 포함 road.sort() for i in road: max_num = max(i[0],i[1]) mi..

# 문제 링크 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net # Soultion n번째 숫자 = (n-1 숫자 + n-5숫자) 1 2 3 4 5 6 7 8 9 t = int(input()) li = [1,1,1,2,2] for i in range(5, 100): li.append(li[i-1]+li[i-5]) for _ in range(t): n = int(input()) print(li[n-1]) cs 3. (n번째 숫자 = n-1 숫자 + n-5숫자) 이므로..

# 문제 링크 programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr # Soultion 1 2 3 4 5 6 7 8 9 10 def solution(prices): answer = [] for i in range(len(prices)): cnt = 0 for j in range(i+1,len(prices)): cnt+=1 if prices[i] > prices[j]: break answe..

# 문제 링크 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net # Soultion(실패) 메모리 초과문제로 실패하였다. 1 2 3 4 5 6 7 8 # 메모리 초과 n = int(input()) li = [1,2] for i in range(2,n): li.append((li[i-1]+li[i-2])) print(li[n-1]%15746) cs # Soultion(성공) 리스트에 저장할 때, 너무 큰 수를 넣어서 메모리초과문제가 발생하여15746을 나눈 나머지를 ..

# 문제 링크 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net # Soultion(실패) 단순 재귀를 이용하여 시간초과 문제 발생 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def w(a,b,c): if a 20: return w(20, 20, 20) if a

# 문제 링크 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net # 관련 알고리즘 이론 jiwon-coding.tistory.com/35 동적 계획법 (다이나믹 프로그래밍, DP) # 동적 계획법 (Dynamic Programming) - Recursive + Memorization - 점화식 찾기! -> 작은 문제의 해를 테이블에 저장한 뒤, 나중에 읽어서 사용 - 상향식 (작은 -> 큰) 하향식 (분할 정복) - 대표적인.. jiwon-coding.tistory.com # Soultion(실패) 재귀를 이용하여 문제를 풀었으나, 시간이 초과하는 문제 발..