All-rounder developer

[백준][그리디] 회의실 배정

오늘의 학습 키워드정렬, 그리디 알고리즘 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/1931 10만 이하의 정수 n이 입력으로 주어지고, 이어서 n개의 회의 시간(시작 시간, 종료 시간)이 주어진다.하나의 회의실에 대해 최대 몇 개의 회의가 진행될 수 있는지 찾는 문제이다. 이 때 주의할 점은 아래와 같다.1. 회의 시작 시간과 종료 시간이 동일할 수 있다 → 예: (1, 1) 가능2. 이전 회의 종료 시간에 다음 회의가 시작할 수 있다. → 예: (1, 3), (3, 5) 가능 🌱 나의 시도최종적으로 정렬 + 그리디 알고리즘으로 이 문제를 해결하였다. 이 문제를 처음 보았을 때 그리디 알고리즘으로 시도해보고, 잡히지 않는 반례가 있을 경우 그래프 탐색으로 접..

[백준][그리디] 잃어버린 괄호

오늘의 학습 키워드그리디 알고리즘, 문자열 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/1541 입력으로 주어진 문자열 중 특정 부분에 괄호를 쳤을 때 가장 작은 값을 만드는 문제이다.입력으로는 덧셈/뺄셈 부호(+, -)와 숫자로 구성된 문자열이 주어진다. 🌱 나의 시도마이너스 사이에 있는 덧셈 부호를 모두 괄호로 묶어서 가장 큰 값을 빼 주는 방식으로 접근하였다.따라서 아래와 같은 흐름으로 코드가 진행된다.1. 문자열을 돌면서 마이너스를 만나면 스위치가 켜진다.2. 스위치가 켜지면 마이너스 사이의 값들을 스택에 넣어 모두 더해준 다음, 스택의 값을 전체에서 빼준다.formular = input()switch = False # 마이너스 부호를 만나면 덧셈 부호를..

[백준][정렬] 시리얼 번호

오늘의 학습 키워드정렬, 문자열 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/1431 오늘의 문제는 문자열을 여러 개의 조건으로 정렬하는 문제이다.입력으로 50 이하의 정수 n이 주어지고, 이어서 n개의 문자열이 주어진다.(1) 문자열의 길이(오름차순), (2) 문자열에 포함된 숫자의 합(오름차순), (3) 문자의 사전순 정렬(오름차순)을 기준으로 정렬한다. 🌱 나의 시도파이썬에서 제공하는 sorted 함수를 활용하였다.이미 최적화 되어 있기에 효율성에서도 적합하고, key 파라미터에 lambda 함수를 이용하여 여러 조건에 대한 정렬이 가능하기 때문이다. 정렬 기준 중 2번 조건에 대해 별도의 함수를 구현해주었고, 이를 lambda 함수에 아래와 같이 추가해주..

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

오늘의 학습 키워드스택, 문자열 오늘의 회고🌱 오늘의 문제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를 별도 게시..

오늘의 학습 키워드DFS 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/4963배열의 크기(w, h)와 배열이 여러 번 반복하여 주어질 때, 그 배열에 포함된 섬의 개수를 세는 문제이다. [주의할 점]1. 테스트 케이스의 개수가 고정되어 있지 않아 시간 복잡도를 예측하기 어려움이 문제에서는 w, h의 입력이 0 0으로 주어질 때 프로그램을 종료한다. 너비와 높이인 w와 h가 50 이하의 정수이므로, 배열의 크기가 많이 크지는 않으나 테스트 케이스가 몇 개나 반복될 지 모른다는 점에서 시간 복잡도를 예측하기 어렵다.2. 상하좌우 + 대각선 이동 가능상하좌우 뿐만 아니라 대각선으로도 이동 가능하다. 출발점 기준으로 인접한 8개의 위치를 모두 고려해주어야 한다. 우선 간..

오늘의 학습 키워드투포인터나는 투포인터라는 용어 자체를 처음 들어봤는데,투포인터로 푼다는 걸 딱 듣자마자 바로 풀리네? 넘 신기하다! 😚 오늘의 회고🌱 오늘의 문제https://www.acmicpc.net/problem/2559백준 문제는 미리보기가 안 뜨나 보다. 어제도 안 떴는데.. 흠. 배열의 길이 n과 간격 k가 주어지고, 온도 값을 담은 배열이 이어서 주어진다.연속 k간의 온도의 합이 최대가 되는 값을 구하는 문제이다. 🌱 나의 시도시도1.처음에 시도한 방법은 타임 아웃이 떴다.그 이유는 사실 명확하다. 아래 코드는 아주 간결하고 깔끔해보이지만 매우 비효율적인 코드이다.1. 우선 반복문을 통해 O(n)번 돌고 있다.2. 내부에서 sum(tem[i:i+k]) 함수는 O(n^2)으로 동작할 ..

오늘의 학습 키워드DFS, 시뮬레이션 오늘의 회고🌱 오늘의 문제 https://www.acmicpc.net/problem/2468(왜 미리보기가 안 불러와질까 🥹)2차원 배열이 주어지고 각각의 칸에는 지형의 높이 정보를 나타내는 자연수 값이 들어간다.이 문제에서는 장마철에 특정 높이 이상 비가 와 일부 지형이 물에 잠겼을 때, 물에 잠기지 않은 안전 영역의 최대 개수를 묻고 있다.여기서 안전 영역은 상하좌우로 인접해 있는 지점들이 최대를 이루는 영역을 말한다. 🌱 나의 시도최대 영역에 대한 개수를 세는 문제는 마침 어제 공부한 DFS 문제의 예시와 비슷했다.그래서 나는 이 문제를 재귀 함수를 이용한 DFS로 구현해보려고 한다.또한 이 문제에서는 장마철에 오는 강우량의 '높이'에 대해 명시하지 않으..

문제 링크: 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..