All-rounder developer

[백준][문자열] 99클럽 코테 스터디 8일차 TIL + 한국이 그리울 땐 서버에 접속하지

오늘의 학습 키워드문자열 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/9996N개의 문자열에 대해 패턴과 일치하는지 확인하는 문제이다. 일치하면 DA, 그렇지 않으면 NE를 출력한다. 판별할 문자열의 개수 N이 먼저 주어진다.다음으로 판별 기준이 될 패턴이 주어진다. 이 패턴에는 *이 하나 포함되어 있고, *자리에 빈칸을 포함한 특정 문자열이 들어갈 수 있다.이어서 N개의 판별할 문자열들이 주어진다.  🌱 나의 시도1. 입력 받은 문자열에 대해 *을 기준으로 앞(front)과 뒤(back)를 추출한다.2. 맨 앞의 문자열이 front와 일치하고, 맨 뒤의 문자열이 back과 일치하면 DA를 출력한다.3. 그 외 NE를 출력한다. 단, 주의할 점이 있다.이 문제에서..

[백준][스택] 99클럽 코테 스터디 7일차 TIL + 쇠막대기

오늘의 학습 키워드스택, 문자열  오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/10799오직 소괄호만을 이용하여 쇠 막대기와 레이저의 위치를 나타낸 입력이 주어진다. 입력의 길이는 최대 10만이다.  🌱 나의 시도이 문제에서 중요한 포인트는 레이저가 한 번 등장할 때마다 현재 겹쳐져 있는 쇠 막대기의 개수만큼이 잘리게 된다는 것이다.조금 더 구체적으로 로직을 정리해 보면 아래와 같다. 1. 현재 들어온 입력에 대해 쇠 막대기인지 레이저인지 판단한다.2. 만약 쇠 막대기라면 현재 쇠 막대기 개수를 1 증가시킨다.3. 만약 레이저라면 현재 저장되어 있는 쇠 막대기 개수만큼 정답 값에 더해준다.4. 위 과정을 반복한 후 최종적으로 몇 개의 쇠 막대기가 잘렸는지 판단해준..

1. 개요DFS 알고리즘을 적용한 문제 유형으로 2차원 배열에 포함된 특정 영역의 최대 개수를 구하는 문제가 많이 출제된다.아래 두 문제를 풀어보며 이러한 문제 유형에 대해 이해하게 되어, 그 내용을 정리해보려고 한다. 이 글에서는 내가 이해한 개념을 자세하게 풀어서 정리하고, 관련 문제의 코드도 함께 살펴 볼 예정이다.  단, 이 글은 DFS 알고리즘에 대해 이해하고 있다는 가정 하에 설명을 진행한다.만약 DFS 알고리즘의 개념이나 원리를 잘 모른다면 아래 글을 참고하기를 추천한다.https://developer-zoyh.tistory.com/17 [알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)0. IntroductionDFS와 BFS를 별도 게시..

0. IntroductionDFS와 BFS를 별도 게시물로 정리하려고 했으나 결국 하나의 게시물로 정리하게 되었다.둘은 이름이 비슷해서인지 잘 헷갈리는 것 같다.같은 게시물 안에서 동일한 그래프로 비교하면서 보면 더 잘 이해할 수 있을 것이라고 판단하였다.단, BFS, DFS 문제풀이는 본 게시물에서 다루지 않는다. 앞으로 DFS, BFS 문제를 공부하면서 차근차근 하나씩 추가해보겠다. 1. DFS (Depth-First Search, 깊이 우선 탐색)1. 정의이름에서 알려주는 것처럼 깊이를 우선적으로, 즉, 가장 깊이 위치하는 노드까지 탐색하는 알고리즘이다.DFS 문제를 풀 때는 스택을 활용하면 더 쉽게 해결할 수 있다.이것은 예시를 보면 더욱 잘 이해할 수 있으니 예시를 함께 보면서 확인하도록 하자...

오늘의 학습 키워드메모이제이션, 시뮬레이션 오늘의 회고🌱 오늘의 문제피보나치 문제의 변형된 문제이다. 피보나치 문제가 특정 위치 n의 값에 대하여 n-1, n-2 연속된 두 값의 합으로 구해나갔다면, 이 문제는 n-1, n-3과 같이 한 칸을 띄운 두 값의 합으로 구하는 문제이다.이 외의 조건이 크게 달라지는 부분은 없어 기존의 피보나치 구하는 방식으로 구하면 크게 문제될 것이 없다. 🌱 나의 시도입력 값의 최대값이 116으로 크지 않아 복잡한 알고리즘을 사용하기 보다는 짧고 가독성 좋은 코드를 사용하는 것이 좋다는 판단을 했다. 동일한 연산을 반복하지 않으므로 재귀 함수가 불필요하며, 이전 연산 값을 저장해두고 사용할 수 있는 메모이제이션 정도면 충분하다. 현재 단계적으로 문제를 풀기 때문에 시간 ..

🌱 그래프 그래프는 노드와 간선으로 이루어진 자료 구조이다. 크게 노드와 엣지(간선)으로 구성되어 있다.그래프는 간선으로 연결된 노드들 간 이동할 수 있는데, 이렇게 간선으로 연결된 노드들을 인접하다(Adjacent)고 한다.  🌱 그래프 표현 방법그래프에서 인접한 노드들간의 관계를 나타내는 방법으로 크게 인접 행렬(Adjacency matrix)과 인접 리스트(adjacency list)가 있다.1. 인접 행렬인접 행렬은 단어 그대로 "행렬"의 형태로 인접한 노드 간의 관계를 나타낸 것을 의미한다.행의 노드와 열의 노드 간의 거리를 행렬값으로 확인할 수 있다. 따라서 인접한 노드 조회를 할 때 시간 측면에서 O(1)로 아주 빠르다.그러나 이 방식은 메모리 측면에서 비효율성을 야기할 수 있기에 조심해..

🌱 스택 (Stack)1. 기본 개념스택은 기본적으로 LIFO(Last In First Out), 혹은 선입후출 구조라고 한다. 즉, 나중에 들어간 것이 맨 처음 나온다. 다시 말 하면 처음 들어간 것이 맨 뒤에 나오는 구조이다. 동굴을 떠올리면 스택 구조를 쉽게 상상할 수 있다.2. 이상 상태스택은 고정된 크기를 갖는 자료구조이다. 따라서 고정된 크기에서 벗어나는 액션을 취할 때 두 가지 이상 상태를 가질 수 있다.1. 오버플로우(Overflow): 자료구조가 수용 가능한 범위를 가득 채운 상태해서, 초과하여 삽입 연산을 수행하려고 할 때 발생하는 현상2. 언더플로우(Underflow): 자료구조에 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행하려고 할 때 발생하는 현상* 예전에는 위 두 용어가..

문제 링크: https://www.acmicpc.net/problem/1929   오늘의 교훈: 입출력 범위를 잘 보자.... 소수 구하는 알고리즘은 처음 코딩 걸음마를 하던 시절부터 풀어왔다.그런데 오늘 문득 든 의문은 이것보다 더 효율적으로 푸는 방법은 없을지 궁금했다.우선 오늘 푼 방법 먼저 정리하고 효율적으로 풀 수 있는 방법이 있는지 추가로 찾아보자. 풀이import mathm, n = map(int, input().split())for x in range(m, n+1): isPrime = True if x != 1 else False for i in range(2, int(x**0.5)+1): if x % i == 0: isPrime = False if isPrim..

정의: 넓게는 알고리즘을 소스 코드로 바꾸는 것을 의미한다. 좁게는 문제에서 제시하는 제약 조건들에 대해 문법 및 라이브러리를 활용하여 꼼꼼하게 풀어내는 것을 의미한다.대표 예시- 완전 탐색: 문제에서 나올 수 있는 모든 경우의 수에 대해 계산하는 문제 유형- 시뮬레이션: 문제를 해결하기 위하여 각 절차를 한 단계씩 순차적으로 해결해나가는 문제 유형주의사항: 입력 조건이 자세하게 명시되며 문제의 길이가 긴 편이다.참고: 파이썬은 C, C++, JAVA에 비해 난이도가 낮은 반면 속도가 느리다는 단점이 있다. 이를 개선하기 위해 코딩 테스트 시 개발 환경에 PyPy를 지원한다면 PyPy를 선택하자. (실행 속도가 더 빠름)