'Coding Test' 카테고리의 글 목록 (2 Page)
본문 바로가기

Coding Test

 (17)
[코딩 테스트 합격자 되기] 시간 복잡도 코딩 테스트 스터디기간 : 2024-07-08 ~ 2024-08-25 스터디 참가 이유 및 목표알고리즘 기초 개념 복기평소 쓰는 언어인 파이썬 대신 C++를 사용해보면서 코드의 동작 원리를 깊이있게 이해 스터디 방식[인프런] 코딩 테스트 합격자 되기 - C++ 강의를 보고 금요일까지 블로그에 내용 정리일요일 14:00에 디스코드를 통해 공부한 내용에 대해 소통학습 날짜 : 2024-07-08학습 주제 : 시간 복잡도 [목차]알고리즘이란?알고리즘 성능측정법 및 시간 복잡도 개념시간 복잡도를 빅오 표기법으로 표기하기코딩 테스트에서 꼭 알아둬야 할 시간 복잡도실전 예시알고리즘 성능은 구현된 코드가 동작하는 절대 시간이나 연산 횟수를 파악하여 측정할 수 있다코딩테스트에서 알고리즘의 성능은 연산 횟수로 측정 / ..
[강의] 코딩테스트 시간복잡도 날짜 : 2024-06-13시간 : 20:00~22:00 (2h)강의 자료 : https://www.notion.so/240613-9839cae0980d4ffc916bbec2860eb90e시간 복잡도 측정하는 이유 : 미리 실행시간을 측정해서, 최대 입력일 때 버틸 수 있는지를 보는 것 시간 복잡도 : 실행시간과 입력값 n의 함수 관계n은 문제의 크기, 입력 데이터의 크기, 반복 횟수 등 문맥에 따라 다를 수 있음어떤 수치가 반복 횟수에 영향을 주는지 알면 된다!시간 복잡도를 통해서 실행시간을 정확히 알 순 없음. 경항성만 파악하는 것이 목표같은 O(n*2)이더라도 앞에 계수가 뭐냐에 따라 시간 복잡도 통과할수도 실패할수도 있음코딩테스트에서는 빅오는 같은데 함수가 시간이 많이 걸려서 통과 안되는 경우는 ..
[알고리즘] Dynamic Programming (DP) 알고리즘 문제를 풀 떄 항상 어려웠던 유형인 다이나믹 프로그래밍에 대해 깊이 다뤄보려고 한다.개념다이나믹 프로그래밍은 완전 탐색, DFS, BFS와 같이 수많은 경우의 수를 전부 따져봐야 하는데 그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자 만들어진 알고리즘 특정 위치까지 올 수 있는 최적의 조합을 저장한다. 각 위치까지 올 수 있는 최적의 값만 남겨 놓고 나머지 조합은 미리미리 버리기기억하기 알고리즘. 기억하며 풀기.장점다음 단계를 계산할 때 최적이 아닌 다른 경우의 수는 고려하지 않기 때문에 연산 수가 줄어든다.메모리를 사용해서 (=배열 혹은 자료구조 만듦) 중복 연산을 줄이고 (=연산한 결과를 배열에 담아서 같은 연산을 또 하지 않는다)중복 연산을 줄여서 수행 속도를 개선한다.판단 ..
[백준] 2110번 공유기 설치 이분 탐색 2024-05-16 내 기준 어려운 문제 풀이 정리 문제 링크 : https://www.acmicpc.net/problem/2110 집의 좌표들이 주어지면 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 문제이다.n과 x의 범위가 매우 큰 경우에는 (n은 20만, x는 10억) 이진 탐색 문제가 아닐까 고민해보는 것이 좋다고 한다.가장 인접한 두 공유기 사이의 최대 거리를 이진 탐색으로 찾으면 𝑂(𝑛∗𝑙𝑜𝑔𝑥)O(n∗logx)만에 문제를 해결할 수 있다.이분 탐색으로 풀 시, start와 end point를 어떻게 정의할지, 또 이를 어떻게 업데이트할지 고민했다. 처음에는 집의 index를 start, end point로 잡고 / 거리를 비교하며 start, end update / C값(설치할 공유기..
[SQL] 쿼리문 작성 코테 대비 문제 : 프로그래머스 SQL 고득점 Kit주제별 내용 간략 정리SELECT문법 순서SELECTFROMWHEREGROUP BYHAVINGORDER BYWITH절 : 반복되는 SubQuery문을 효율적으로 작성하기 (Reference)/* 1개의 임시테이블 */WITH 임시테이블명 AS ( SUB QUERY문 (SELECT절))SELECT 컬럼, [컬럼, ...] FROM 임시테이블명 /* 2개 이상의 임시테이블 */WITH 임시테이블명1 AS ( SUB QUERY문 (SELECT절)),임시테이블명2 AS ( SUB QUERY문 (SELECT절))SELECT 컬럼, [컬럼, ...] FROM 임시테이블명1, 임시테이블명2 SUM, MAX, MIN GROUP BYGROUP BY : 그룹별 분류HAVING..
2차원 리스트 생성 후 요소 변경 visited = [[False]*3]*3 print(visited) visited[0][1]=True print(visited) 결과: [[False, False, False], [False, False, False], [False, False, False]] [[True, False, False], [True, False, False], [True, False, False]] 한 값만 바껴야 하는데 해당하는 열의 모든 값이 바뀜 -> 원인: *연산자가 참조를 복사했기 때문 파이썬은 *연산자로 초기화 할 때 값을 각각 할당하는게 아니고 하나의 객체를 생성해 놓고 모두가 이를 가리키는 '얕은 복사'를 진행한다. 하나의 정수형 객체 0을 생성하고, 배열의 각 요소들이 이를 가리킨다. 0이 4개가 아닌 1개..
[백준] 런타임에러 런타임에러 원인 배열 인덱스 범위를 벗어났을 경우 0으로 나눌 때 사용하는 라이브러리에서 예외를 발생시켰을 때 재귀 호출이 너무 길어질 때 2798 블랙잭 / Python 추측 에러 원인: 1) 인덱스 에러 더보기 from itertools import combinations N, M = map(int, input().split()) lst = list(map(int, input().split())) c = list(combinations(lst, 3)) sum_c = list(map(sum, c)) diff = list(map(lambda x:x-M, sum_c)) # 음수 중 가장 큰 수 m = -9999 for i in diff: if im: m = i if m != -9999: print(sum_..
[백준] 시간초과 2805 나무자르기 / Python N이 백만이기 때문에 N크기의 리스트를 끝에서부터 돌면서 확인하는 것은 시간복잡도가 n^2 -> 이분 탐색으로 mid값을 잡으면서 계산 더보기 import sys input = sys.stdin.readline N, M = map(int, input().split()) tree = list(map(int, input().split())) cut = max(tree) - (M//len(tree)+1) get = 0 while get 0]) cut -= 1 print(cut+1) 이전 코드: 나무 최대 길이부터 M값이 될때까지 1씩 빼면서 나무 모음 import sys input = sys.stdin.readline N, M = map(int, input().split()..

티스토리툴바