CS Student’s SAP&Tech Journey💫

1. 구현(Implementation) 유형의 문제란?구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다.알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 구현 알고리즘 문제의 2차원 공간은 행렬(Matrix)의 의미로 사용되고 자주 출제됩니다.행렬이란 2차원 데이터를 일종의 표와 같은 형태로 쉽게 나타내는 수학 개념입니다. 즉, 파이썬에선 2차원 배열을 말합니다.보통 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용됩니다.시뮬레이션 문제같은 경우에는 어떠한 캐릭터나 사..

1. 그리디 알고리즘(탐욕법)이란?그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.쉽게 말하면 탐욕스럽게 최고의 선택만 취하는 것을 말합니다.일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.그리디 해법은 그 정당성 분석이 중요합니다.단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.✔️ 그리디 알고리즘은 항상 최적의 해를 보장하지 않습니다.일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다. 트리에서 경로를 이동..

🧪 프로그래머스 문제: 특정 형질을 가지는 대장균 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제를 처음 접했을 때, GENOTYPE이라는 컬럼에 형질 정보가 저장되어 있다는 것을 보고 처음엔 단순히 LIKE나 IN 같은 조건문으로 처리하려고 생각할 수 있습니다. 하지만 GENOTYPE 컬럼의 정체는 비트마스크 형태의 정수값이라는 점을 눈치채야 합니다. 각 대장균 별 형질을 2진수로 나타내면 다음과 같습니다.ID 1 : 1000₍₂₎ ID 2 : 1111₍₂₎ ID 3 : 1₍₂₎ ID 4 : 1101₍₂₎각 대장균 별 보유한 형질을 다음과 같습니다.ID 1 : 4 ID 2 : 1, 2, 3,..

1. 백준 2108번 통계학[백준] 2108번: 통계학 2. 오늘의 회고0. 문제 분석산술평균 : N개의 수들의 합을 N으로 나눈 값중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값최빈값 : N개의 수들 중 가장 많이 나타나는 값범위 : N개의 수들 중 최댓값과 최솟값의 차이 1. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 2. 출력출력 부분에서 주의해서 봐야 할 점은 산술평균을 출력할 때는 소수점 이하 첫째 자리에서 반올림하여 정수값을 출력해야 한다. 최빈값을 출력할 때는 최빈값이 여러 개 있을 때 최빈값 중 두 번째로 작은 값 ( = 3, 4가 있으면 두번째가 작은 값은 4이다)을 출력한다. 3. 문제접근1. 입력 값을 n..

1. 백준 1874번 스택 수열[백준] 1874번: 스택 수열 2. 오늘의 회고 0. 문제 분석 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. ..

1. 백준 1436번 영화감독 숌백준 1436번: 영화감독 숌 2. 오늘의 회고 0. 문제 분석종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다. : 처음에는 앞뒤로 숫자를 더하면서 붙여야 하는지 해결 방법이 보이지 않았다. 입력 범위를 보고 브루트포스로 해결해도 된다는 생각을 한 후 문제를 풀 수 있었다. 브루트 포스 알고리즘은 시간과 ..

99클럽 코테 스터디 4일1. 백준 24444번 알고리즘 수업 -  너비 우선탐색 1[백준] 24444번: 알고리즘 수업 - 너비 우선탐색  2. 오늘의 회고 0. 문제 분석N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. : 인접 정점은 오름차순으로 방문시켜야하므로 정렬해주어야 한다.  1. 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ ..

1. 너비 우선 탐색 BFS ( Breadth-First Search )BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 한다.더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 2. BFS 동작 예시[Step 0] 그래프를 준비 (방문기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1[Step 1] 시작노드 ‘1’을 큐에 삽입하고 방문처리합니다.[Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접노드 ‘2’..

1. 백준 24479번 알고리즘 수업 - 깊이 우선탐색 1 [백준] 24479번 : 알고리즘 수업 - 깊이 우선탐색 2. 오늘의 회고 0. 문제 분석N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. : 인접 정점은 오름차순으로 방문시켜야하므로 정렬을 해주어야 한다. 1. 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.다음 M..

1. 깊이 우선 탐색 DFS ( Depth - First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 스택 자료구조 혹은 재귀함수를 이용하며, 구체적인 동작 과정은 다음과 같습니다.탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. 2. DFS 동작 예시 (예시는 번호가 낮은 인접 노드 부터 방문)[step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1[step 1..