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

Coding Test

 (19)
[코딩 테스트 합격자 되기] 해시 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=KsfmSyIYX3g&t=3s 배열의 경우 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함 O(n)contents 자체를 가지고 위치 (index)를 알 수 있는 것이 해시 해시 함수를 사용해서 변환한 값을 인덱스(해시값)로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 O(1) 해시함수 : 임의의 키를 해시테이블의 인덱스로 변경해주는 함수해시 테이블의 크기가 N이라면 해시함수는 0 ~ (N-1) 사이 값을 내야 함충돌을 최소화 할수록 좋은 해시함수* 충돌 : 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환하는 것 [해시함수 종류]나눗셈법 : h(..
[코딩 테스트 합격자 되기] 스택/큐 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=-TGCT74wFeg&t=2s FILO (First In Last Out)사용 예시 : 함수 호출 관리, 페이지 탐색, 괄호 짝 맞추기- 가장 최근 원소를 봐야하는 경우 사용- 추후 DFS, 백트래킹에서 사용 FIFO (First In First Out)사용 예시 : 줄 서기, 요세푸스 문제 - 들어온 순서대로 나갈 때 사용- 추후 BFS에서 사용[풀이할 문제] (스택/큐 관련문제, 필수풀이) 괄호 회전하기(문제 10)=> https://school.programmers.co.kr/learn/courses/30/lessons/76502주식 가격(문제 12)=> https://school.pro..
[코딩 테스트 합격자 되기] 시간 복잡도 코딩 테스트 스터디기간 : 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개..

티스토리툴바