본문 바로가기
728x90

코딩테스트77

<PART2> 스택/큐/재귀함수 탐색: 많은양의 데이터 중에서 원하는 데이터를 찾는 과정 대표 탐색 알고리즘인 DFS/BFS를 이해하려면 기본 자료구조인 스택,큐,재귀 함수에 대한 이해가 전제되어야 합니다. 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됩니다. -삽입(push): 데이터를 삽입한다. -삭제(pop): 데이터를 삭제한다. push를 할 때는 오버플로우, pop을 할 때는 언더플로우를 조심해야합니다. - 스택 (Stack) 선입후출 또는 후입선출의 구조이다. LIFO(Last in First Out)라고도 한다. 파이썬 코드로 표현하면 다음과 같다. append와 pop자체가 서로 맨 뒤쪽 데이터를 push,pop하는 것이기 때문에 스택은 별도.. 2022. 11. 4.
<PART 2> 구현(완전탐색,시뮬레이션) 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 EX) 리그오브레전드에서 정글이라는 포지션으로 이길 수 있는 완벽한 계획이 있다라더라도 피지컬이 안되면 진다. 하지만 구현은 계획만 있어도 된다. 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 예제 4 -1 상하좌우 N x N 크기의 정사각형 공간이 있다. 맨 왼쪽 위가 (1,1)이고 차례대로 좌표가 부여된다. 1. 처음 시작은 (1,1)이며, 다음 행동으로 옮길 때 이동의 규칙이 있다. 2. 상하좌우중에 1개씩 선택해서 할 수 있으며 정사각형 공간을 넘어가는 동작일 경우 횟수를 추가되지만 움직이지 않는다. 3. 최종 좌표를 출력하라 상하좌우:.. 2022. 11. 4.
list1 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVFCzaqeUDFAWg# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 브루트포스 -> 완전탐색 2. 그리디 ex) 1. 0~9숫자 중에서 중복을 허용한 채 6개의 숫자를 뽑는다. 2. 6개의 숫자중에 똑같은수 3개와 연속된 수 3개가 있어야 한다. 이를 해결하기 위해 브루트포스로 전부다 탐색할 수도 있다. 그러나 그리디 방법으로 똑같은 수 3개를 제외하고 나머지 3개의 수를 연속된지 판별할 수도 있다. 디테일하게 보면 정.. 2022. 10. 31.
Programming Intermediate https://swexpertacademy.com/main/learn/course/courseList.do#none SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 싸피를 코딩테스트를 위해 풀어볼 예정입니다. 2022. 10. 31.
<PART 2> 그리디 예제 큰 수의 법칙 n,m,k가 있습니다. n은 배열의 원소 갯수, m은 더하는 횟수, k는 연속한 수가 k번 초과할 수 없음을 의미합니다. 이를 가지고 원소들을 더해서 가장 큰수를 만드는 것이 목적입니다. ex) n=5이면 2,4,5,4,6로 원소 5개를 주고 m=8, k=3이라면 6+6+6+5+6+6+6+5 =46이 됩니다. 입력예시 5 8 6 2 4 5 4 6 출력 예시 46 1 2 3 4 5 6 7 8 9 10 11 12 N, M, K = map(int,input().split()) a = sorted(list(map(int,input().split()))) cnt = 0 a_sum = 0 for i in range(M): if cnt == K: #k초과지만 cnt가 k가 되면 이미 k수만큼.. 2022. 9. 28.
이것이 취업을 위한 코딩테스트다. https://www.youtube.com/watch?v=m-9pAwq1o3w&t=7163s 코딩 테스트를 준비해야 되는 데 많은 사람들이 이 책을 추천해주었습니다. 그래서 배우는 입장으로 개념들을 블로그에 기록하면서 공부할 예정입니다. 개념, 문제, 문제풀이, 배운점 순으로 정리해서 적을 것입니다. 2022. 9. 28.
코딩테스트 유형 코딩테스트에서 유형은 구현 33.0% DFS/BFS 20.9% 그리디 19.8% 정렬 8.2% 다이나믹 프로그래밍 8.2% 이진탐색 3.8% 최단경로 3.3% 기타그래프이론 2.7% 같이 출제되나, 어려운 문제는 복합적으로 나타난다.. 처음이니깐 빈도수가 높은 문제부터 문제를 풀 생각입니다. 2022. 9. 28.
1018 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이 문제는 브루트포스 유형이다. 모든 경우의 수를 구해야 하는 문제인데 어떻게 해야 할지 감이 안 잡히는 문제였다. https://god-gil.tistory.com/62 [백준 알고리즘/python] 백준 1018번 체스판 다시 칠하기, 파이썬 설명 백준 알고리즘의 브루트 포스 단계, 1018번 체스판 다시 칠하기를 파이썬으로 풀어보았다. 문제 출처 https://www.acmicpc.n.. 2022. 8. 30.
1436 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net n = int(input()) six_number='666' number = 0 cnt = 0 while True: number +=1 if six_number in str(number): cnt += 1 if cnt == n: break print(number) 2022. 8. 25.
11722 11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net) 2022. 8. 22.
9095 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2022. 8. 22.
11729 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net n = int(input()) def hanoi(n, a, b, c): if n == 1: print(a, c) else: hanoi(n - 1, a, c, b) print(a, c) hanoi(n - 1, b, a, c) sum = 1 for i in range(n - 1): sum = sum * 2 + 1 print(sum) hanoi(n, 1, 2, 3) 하노이는 코드로 구현하는.. 2022. 8. 18.
1149 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net rows = int(input()) # 원하는 줄의 갯수를 입력 rgb = [] #RGB값을 입력할 빈 리스트 생성 for i in range(rows): rgb.append(list(map(int, input().split()))) for i in range(1, len(rgb)): #RED rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) .. 2022. 8. 18.
2839 https://www.acmicpc.net/problem/2839 a = [] count = 0 n = int(input()) if n%5 == 0: #나눴을 때 나머지가 0이면 5로 나눈 값을 a에 저장 a.append(int(n/5)) count += 1 for n_5_div in range(0, int(n/5)+1): #처음에 5를 0~ 5나누기의 몫까지 차례대로 n을 나눔 c = n-(5*n_5_div) for c_3_div in range(0, int(c/3)+1): # 5로 나눈 값에대가 3을 또 나눈 몫까지 차례대로 c를 나눔 if c%3 == 0: a.append(n_5_div + int(c/3)) count += 1 if count == 0: a.append(-1) print(min(a)) 2022. 8. 17.
2798번 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net from itertools import combinations n, m = map(int,input().split()) number = map(int,input().split()) number_sum = [] for i in combinations(number, 3): number_sum.append(sum(i)) number_sum.sort() for i in n.. 2022. 8. 14.
728x90

티스토리툴바