와드의 블로그

문제어떤 주식의 매일의 가격을 나타내는 배열 prices가 주어집니다. prices[i]는 i번째 날의 주식 가격입니다. 주식을 단 한 번 사고 단 한 번 팔아서 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하는 문제입니다. 만약 어떤 이익도 얻을 수 없다면 0을 반환해야 합니다.입력: 주식 가격을 담은 정수 배열 prices (길이 1 이상 100,000 이하, 각 가격은 0 이상 10,000 이하)출력: 얻을 수 있는 최대 이익 (이익이 없으면 0 반환)링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock풀이: 저점 매수 및 고점 매도 (O(N) 탐색)이중 반복문을 사용하여 모든 매수/매도 타이밍을 검사하면 시간 복잡도가 O(N^2)..

문제주어진 문자열 s가 팰린드롬(앞뒤로 읽어도 똑같은 문자열)인지 판별하는 프로그램을 작성하는 문제입니다. 단, 문자열에서 영문자와 숫자만 고려하며 대소문자는 구분하지 않습니다.입력: 인쇄 가능한 ASCII 문자로 이루어진 문자열 s (1 출력: 팰린드롬이면 true, 아니면 false 반환링크: https://leetcode.com/problems/valid-palindrome풀이 1: StringBuilder를 활용한 문자열 정제 및 비교정규 표현식(Regex)에 의존하지 않고, 아스키코드(ASCII) 값을 직접 활용하여 유효한 문자만 걸러낸 뒤 한 번에 비교하는 직관적인 풀이입니다.문자열 정제 (알파벳 및 숫자 필터링):입력 문자열을 순회하며 소문자나 숫자인 경우 그대로 StringBuilder에 ..

문제괄호 기호인 '(', ')', '{', '}', '[', ']' 만으로 이루어진 문자열 s가 주어집니다. 이 문자열이 유효한 괄호 문자열인지 판별하는 프로그램을 작성하는 문제입니다. 유효한 문자열의 조건은 다음과 같습니다.열린 괄호는 같은 타입의 닫힌 괄호로 닫혀야 합니다.열린 괄호는 올바른 순서대로 닫혀야 합니다.모든 닫힌 괄호는 짝이 맞는 열린 괄호를 가지고 있어야 합니다.입력: 괄호로만 이루어진 문자열 s (1 출력: 유효한 문자열이면 true, 아니면 false 반환링크: https://leetcode.com/problems/valid-parentheses풀이: Stack과 조기 종료(Early Return)를 활용한 최적화괄호의 짝을 맞추는 문제는 가장 나중에 열린 괄호가 가장 먼저 닫혀야 ..

문제정수 배열 nums와 목표 정수 target이 주어집니다. 배열 내의 두 숫자를 더해 target이 될 수 있도록 하는 두 숫자의 인덱스를 배열에 담아 반환하는 프로그램을 작성하는 문제입니다.단, 정확히 하나의 정답만 존재한다고 가정합니다.동일한 원소를 중복해서 사용할 수 없습니다.정답의 순서는 상관없습니다.제한사항 (Constraints)2 -10^9 -10^9 링크: https://leetcode.com/problems/two-sum풀이 1: 브루트 포스 (Brute Force)를 이용한 완전 탐색가장 직관적인 방법으로, 이중 반복문을 사용하여 가능한 모든 두 숫자의 쌍을 확인하는 방식입니다.탐색 로직: 기준이 되는 숫자(nums[i])를 차례대로 순회하며, 그 뒤에 있는 숫자(nums[j])들과..

문제M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어집니다. (1 ≤ M ≤ N ≤ 1,000,000)출력: 한 줄에 하나씩, 증가하는 순서대로 소수를 출력합니다.링크: https://www.acmicpc.net/problem/1929풀이: 에라토스테네스의 체를 활용한 빠른 소수 판별탐색해야 하는 수의 최댓값이 1,000,000으로 매우 크고, 구간 내의 '모든' 소수를 구해야 하므로 각각의 수를 개별적으로 판별하는 대신 '에라토스테네스의 체' 알고리즘을 사용하는 것이 가장 효율적입니다.배열 초기화: 1,000,000까지의 수를 판별하기 위해 크기가 1,000,001인 boolean 배열 p를 선언합니다. 자바에서 bool..