REVIEW/CODING TEST5 BFS/DFS 개념 정리 안녕하세요 진자이입니다 :) 이번 포스팅에서는 자료구조의 기초 내용을 훑고, BFS, DFS에 대한 개념을 정리하고자 합니다. 실습 문제는 따로 올리겠습니다. 자료구조 기초 탐색은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 그리고 DFS, BFS를 이해하기에 앞서, 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조로, 스택과 큐는 자료구조의 기초 개념으로 다음 두 핵심 함수로 구성된다. 물론, 실제로 스택과 큐를 사용할 때는 오버플로와 언더플로를 고민해야 한다.오버플로는 특정한 자료구조가 수용할 수 있는 크기를 가득찬 상태에서 삽입 연산을.. 2023. 6. 30. 구현(implementation) 총 정리 안녕하세요 진자이입니다 :) 이번 포스팅에서는 이코테 내용 중 구현에 대해서 공부한 내용을 기록하려고 합니다. 아이디어를 코드로 바꾸는 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 문제 해결 분야에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 의미한다. “프로그래밍의 언어의 문법에 능숙하고, 코드 작성 속도(타자)가 빠른 사람이 구현 능력이 좋은게 일반적이다. 예를 들면, 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등 사소한 조건 설정이 많은 문제이다. 이 책에서는 완전 탐색, 시뮬레이션 유형을 .. 2023. 6. 29. 그리디(Greedy) 개념 정리 당장 좋은 것만 선택하는 그리디 현재 상황에서 지금 당장 좋은 것만 고르는 방법 → 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 그리디 알고리즘 유형 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 알고리즘은 모든 알고리즘에 적용할 수 있는 것이 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없는 가능성이 다분하다. 하지만, 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다. 따라서, 그리디 알고리즘으로 해법을 찾았을 때는 항상 ‘검토’를 하자. 예제 3-1 거스름돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 .. 2023. 6. 23. 복잡도(Complexity) 개념 총 정리 복잡도란? 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 복잡도의 측정은 다음 2가지를 통해 진행한다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 효율적인 알고리즘을 사용한다는 가정 하에, 시간 복잡도와 공간 복잡도는 Trade-off가 성립한다. 메모리를 조금 더 많이 사용하면 .. 2023. 6. 23. 이코테 시작, 코테 개요 안녕하세요 :) 진자이입니다. CODING TEST 카테고리에서는 코딩테스트를 준비하며, 공부했던 내용을 하나씩 기록해보려고 해요. 그 시작으로, 이코테 파이썬을 공부했던 내용을 남겨볼게요 :) 코딩 테스트 개념과 배경 코딩 테스트 ‘기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 일종의 문제 풀이 시험’ 백준 : ‘https://www.acmicpc.net’ 코드업 http://codeup.kr 프로그래머스 https://programmers.co.kr 온라인 코딩 테스트 보통 기업에서는 온라인 저지 시스템을 별도로 구축하여 제공하거나, 백준 온라인 저지 혹은 프로그래머스 같은 온라인 저지 서비스에 문제를 출제한 뒤 응시자가 해당 시스템에서 응시하도록 한다. 정해진 시간에 응시자가 접속.. 2023. 6. 23. 이전 1 다음
