Grace's Tech Blog

박상길님의 를 보며 문제를 풀고 정리한 것입니다. 그룹 애너그램 문제 출처: https://leetcode.com/problems/group-anagrams/submissions/ 문제 Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. Example 1: Input: strs = ["eat","tea","tan..

박상길님의 를 보며 문제를 풀고 정리한 것입니다. 가장 흔한 단어 (Most Common Word) 문제 출처: https://leetcode.com/problems/most-common-word/ 문제 Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique. The words in paragraph are case-insensitive and the answer should b..

박상길님의 를 보며 문제를 풀고 정리한 것입니다. 1. 문자열 뒤집기 (Reverse String) 문제 출처: https://leetcode.com/problems/reverse-string/ 문제 Write a function that reverses a string. The input string is given as an array of characters s. Example 1: Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2: Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] Constraints: 1 > s = ["h", "e", "l..

박상길님의 를 보며 문제를 풀고 정리한 것입니다. 1. 문자열 조작 (String Manipulation)이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말함 2. 문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야 정보 처리 분야: 어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용한다. 또한 많은 정보가 문자열로 구성되어 있으므로 문자열 처리는 정보 처리에 핵심이 된다. 통신 시스템 분야: 문자열 데이터 전송은 문자열 처리 알고리즘이 나오게 된 기원이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요하다. 프로그래밍 시스템 분야: 프로그램은 그 자체가 문자열로 구성되어 있고, 컴파일러나 인터프리터에서 문자열을 해석하고 기계어로 번환하는 과정에서 정교한 문자열 처리 알고리즘이 ..

동적계획법이란, 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것이다. 즉, '나'를 해결함으로써 더 큰 '나'를 해결하는 것 => '나'가 두 번 나오는 것으로 봐서 딱 떠오르는게 있다면?!! 바로 재귀호출! 즉, 동적계획법은 재귀호출을 사용한다. 동적계획법이 어떤 식으로 활용 될 수 있는지 예제 문제를 통해 살펴보자. 예) 피보나치 수 구하기 - 피보나치 수열의 n번째 수를 구하시오 풀이 1. 먼저 피보나치 수열의 특성 상 '재귀만 사용하여' 풀 수 있다. def getFibo(n): if n < 2 : return n else: return getFibo(n-1) + getFibo(n-2) 그런데 이 해결법이 가장 효과적일까? 아니다. 이 방법은 이전에 한 번 계산한 적이 있던 것이 다시..

단어 찾기 현수는 영어로 시는 쓰는 것을 좋아합니다. 현수는 시를 쓰기 전에 시에 쓰일 단어를 미리 노트에 적어둡니다. 이번에는 N개의 단어를 노트에 적었는데 시에 쓰지 않은 단어가 하나 있다고 합니다. 여러분이 찾아 주세요. ▣ 입력설명 첫 번째 줄에 자연수 N(3

1) 공주 구하기 정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다. 예를..

1) 가장 큰 수 선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하 여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다) 만약 5276823 이 주어지고 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 됩니다. ▣ 입력설명 첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다. ▣ 출력설명 가장 큰 수를 출력합니다. ▣ 입력예제 1 5276823 3 ▣ 출력예제 1 7823 코드) 더보기 num, m = map(int, input().split()) num = list(map(int, str(num))) #각 자리수에 있는 숫자 하나하나에 접근 할 수 있기 때문 # print(num..

소수(Prime Number)란 약수가 1과 자기자신 뿐인 수이다. 주의해야 할 것은 1은 소수가 아니며, 흔히 짝수라서 소수가 아닐꺼라고 생각할 수도(?) 있지만 2는 소수이다. 구현 소수에 관한 문제는 2가지로 생각해 볼 수 있다. 1) 특정 수(n)가 소수인지/아닌지 판별해야 할 경우 이때는 n의 약수 가 1과 자기 자신(n) 뿐이면 소수, 아니면 소수가 아니라는 정의를 이용하는게 좋다. 다시 말해, 1~n 중 1, n을 제외한 2~(n-1) 중에서 하나라도 나누어 떨어지는 것이 있으면 소수가 아니다. / 하나도 나누어 떨어지지 않으면 소수이다. 로 판단 할 수 있는 것이다. ※ 하지만 그냥 2~(n-1)을 모두 탐색하면서 검사하려면 시간복잡도가 O(n)으로 너무 크다.. 고 생각된다. 이를 줄일 ..