Google DSC Sookmyung

C++에서 문자열 다루기 string 클래스의 특징 - 문자의 끝에 null 문자 등이 포함되지 않음 - 배열처럼 한 문자씩 다룰 수 있음 - string 클래스끼리는 + 연산자로 문자열 합치기 가능 - 문자열 사전순 정렬 가능 - 다양한 멤버함수 존재 멤버 함수 - str.front(): 맨 앞 문자 반환 - str.back(): 맨 끝 문자 반환 - str.size() or str.length(): 문자열 길이 반환 - to_string(): 숫자>문자열 - str.capacity(): capacity 값 확인 - str.reverve(n): 미리 n byte 할당 - str.empty(): 빈 문자열인지 확인 - str.clear(): 문자열을 없앰 (capacity 값은 유지) - str1.app..

동적계획법(DP) 동적계획법(dynamic programming)은 자주 볼 수 있는 디자인 패러다임 중에 하나입니다. 동적 계획법에서는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 뒤, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다. 동적계획법을 왜 사용하는 걸까요? 일반적인 재귀 방식 또한 DP와 유사하다고 볼 수 있습니다. 그러나 재귀를 단순히 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적으로 계산됩니다. 가장 많이 쓰이는 예시는 피보나치 수열입니다. 피보나치 수열을 재귀로 구현할 시 return f(n) = f(n-1) + f(n-2)이라는 단순한 식이 나옵니다. 이렇게 구현할 시, 위의 트리와 같은 호출이 일어납니다. 같은 값을 구하는 과정이 반복되서 일어나는 것을 확인..

이진탐색 이진탐색은 배열 내부의 데이터가 정렬되어 있을 때, 원하는 값을 매우 빠르게 찾을 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있으며, 위치를 나타내는 변수를 총 3개 사용한다. 탐색하고자 하는 범위의 시작(start), 끝(end), 중간(mid)의 값이 필요하다. 찾으려는 데이터(target)와 중간점 위치에 있는 데이터를 비교하며 원하는 데이터를 찾아나간다. 한 번 탐색할 때마다 확인하는 데이터의 갯수가 절반씩 줄어든다는 점에서 O(logN)의 시간복잡도를 갖는다. 배열 전체의 중간값을 target값과 비교한다. 중간값이 target보다 작으면, 오른쪽 부분만 다시 탐색한다. 중간 인덱스 이전의 값은 확인하지 않고, start값을 mid 한칸 뒤로 이동시킨다..

목차 개념 정렬 알고리즘 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 그 외 정렬 알고리즘 병합 정렬 버블 정렬 힙 정렬 정렬 알고리즘의 시간 복잡도 비교 파이썬의 정렬 라이브러리 문제 10825 국영수 10814 나이순 정렬 11652 카드 18870 좌표 압축 2108 통계학 23881 알고리즘 수업 - 선택 정렬 1 스터디 저장소 개념 다음은 이것이 취업을 위한 코딩테스트다 with 파이썬에서 발췌한 내용입니다. 정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(Binary Search)이 가능해진다. 선택 정렬 출처: https://codepumpkin.com/selection-sort-algorithms/ 데이터가 ..

주제 DFS와 BFS 1. DFS와 BFS? 대표적인 그래프 탐색 알고리즘으로 DFS(Deep First Search), BFS(Breadth First Search) 두 종류가 있다. 그래프 순회 문제는 주로 그래프의 한 정점에서 시작해 남은 모든 정점을 방문하는 문제 + 그래프란? 연결되어있는 원소간의 관계를 표현한 자료구조 중 하나로 정점(노드)과 간선의 집합이다. 더보기 정점(Vertex) : 노드라고도 하며 데이터를 저장 간선(Edge) : 정점을 연결하는 선 (link, branch 모두 같은 말) 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 단순 경로(simple path) : 경로에서 같은 간선을 두번 지나가지 않는 경로 차수(degree) : [무방향 그래프..

04-DataStructure4 주제 구현 완전구현 시뮬레이션 구현 문제 · 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. ex) 완전 탐색, 시뮬레이션 유형 ▶ 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 ▶ 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 21918번 : 전구 21918번: 전구 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { /** * N -> 전구 개수 * M -> 명령어의 개수 * 1 -> 전..

Greedy 탐욕 알고리즘은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선인 상황에서 사용할 수 있는 알고리즘이다. 그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 동적 프로그래밍을 사용하여 풀 수 있는 문제 중 부분 최선이 전체 최선인 경우, 시간 복잡도를 줄이기 위해 사용한다. 예를 들어 최소 비용을 구하는 문제에서 언제나 비용이 작은 것을 골랐을 때 그 답이 곧 전체의 최소 비용이 되는 경우이다. 현재 상황에서 지금 당장 좋은 것만 고르는 접근 방법이다. 부분 정답이 항상 전체 정답을 포함하고 있을 때 사용할 수 있는 방법이다. 그리디 알고리즘을 이용해 문제를 풀면..

🟡14425 문자열 집합 설명 N개의 문자열로 이루어진 집합 S가 주어졌을 때, 주어지는 M개 문자열 중에서 집합 S에 속하는 문자열이 몇 개인지 구하는 문제이다. N개의 문자열이 주어지면 그 문자열을 key값으로 0을 value값으로 하는 딕셔너리를 만든다. M개의 문자열을 차례로 돌면서 집합S안에 존재하면 count 값을 +1 해준다. 딕셔너리는 해시테이블로 구현되어 있어 내용을 순차적으로 보는 것이 아니라 해당 단어를 바로 찾아가기 때문에 이 과정은 시간복잡도가 O(1)이다. import sys input = sys.stdin.readline n, m = map(int, input().split()) s = {} count = 0 for i in range(n): str = input().rstri..

💗10799 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net [ 풀이 ] 스택 이용 "(" 일 경우 스택에 일단 append ")"일 경우 레이저인지 아닌지 구분해야함 ")"일 때 바로 이전 문자가 "("라면 레이저이므로 스택 길이만큼 쇠막대기 개수 더하기 바로 이전 문자가 "(" 가 아니라 ")"라면 쇠막대기이므로 +1 [ 코드 ] steel = list(input()) stack = [] result = 0 for i in range(len(..

💗스터디원 스터디장 : 신지연 스터디원 : 김규리, 김은지, 민휘, 서희, 정영주, 조은영, 한채연 💗진행방법 & 그라운드 룰 일주일에 4문제 이상 토요일까지 코딩테스트 인터뷰하듯이 깃허브에 정리 후 PR 올리기 (풀이과정, 내 풀이의 시간 복잡도, 사용한 자료구조 또는 알고리즘에 대해 공부한 점 자유로 추가해서 정리) 해당 주차에 백준아이디로 폴더 만들기 stutynote.md 파일 하나에 정리 후 PR 월요일 7시 30분 전까지 최소 두명의 코드를 리뷰하고 코멘트달기 GDSC 블로그에 돌아가면서 각 문제 별 코드 & 풀이 과정 적기 벌금 : 1,000원 / 1문제 리뷰 코멘트 : 2주 이상 코멘트를 남기지 않을 시, 9, 10주차 블로그 작성 및 발표 💗주차별 문제 및 발표자 코딩테스트 나올만한 유형..