Razelo 기술노트

import math class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) l = len(s) for i in range(l // 2): if s[i] != s[l - 1 - i]: return False return True # def isPalindrome(self, x: int) -> bool: # s = str(x) # l = len(s) # if l == 2: # return s[0] == s[1] # is_even = l % ..

leetcode 문제 중 Rust의 다양한 타입변환을 참고하기 좋은 문제가 있어 기록해둔다.   자세한 내용은 주석에 상세하게 적어두었으니 참고바란다.  알고리즘 문제 풀이 중 가장 기본적인 내용은 타입간 변환이다. i32 -> char -> char 's  -> string -> i32 -> 혹은 u8 u32 usize 등으로 변환이 자유자재로 가능해야한다.  이게 안되면 중간에 막히는 곳이 너무 많다.   /** 1530 ~ 1545 i32 char's string간 변환이 핵심인 듯 하네요 */impl Solution { pub fn sum_of_encrypted_int(nums: Vec) -> i32 { let mut output = 0; f..

간만에 카페에서 쉬면서 평화로운 시간을 보낸다. 역시나 쉴때는 리트코드 푸는게 제일 재밌다.  심심해서 Rust로 풀어봤다.   재밌는 문제다. 문제 자체는 쉬운 편인데 Rust로 풀자니 Rust자체의 문법에서 살짝 걸려넘어지는 부분이 있었다. 정리해둘만한 부분이 있는데 같이 살펴보자.  자 우선 for word in &words에서 &로 borrow해서 사용한다. 이렇게 사용하는 이유는 borrow해서 사용하지 않으면 밑에서 words를 참조하려고 할때 위에서 소유권이 이미 이전되었기 때문에 컴파일 에러가 나기 때문에 borrow해서 사용해야 한다. 또 재밌는 부분은 String타입은 개별 word를 접근하려고 할때 String타입 그 자체에서 [] indexing으로 접근할 수 없기 때문에 word...

심심해서 오랜만에 c++로 leetcode 문제를 풀어봤다.  1417 Reformat the string 이라는 문제다. 쉬운 문제라 휘리릭 풀 수 있다.  역시나 PS는 한동안 안하면 다시 시작할때 꽤나 하기가 싫은 경향이 있긴 하다.  class Solution {public: string reformat(string s) { vector digits; vector chars; vector result; digits.reserve(s.length()); chars.reserve(s.length()); result.reserve(s.length()); for(char c: s) { ..

백준 16939 문제이다. Java로 풀이했다. 참고로 이 문제는 굉장히 좋은 문제이다. 문제 자체의 퀄리티가 굉장히 좋다. 문제가 깔끔하고 실력 향상에도 많은 도움이 된다. 예전에 한번 풀려고 시도했지만 당시에 답안에 거의 근접했는데 사소한 로직에서 실수를 해서 풀지 못했다. 대략적인 풀이방법은 알고있었지만 오늘에서야 해당 로직을 수정하게 되었다. 구현 문제이고 정말 흥미로운 문제이다. 개인적으로 이런 문제를 좋아한다. 어째서인지 복잡한 구현 문제가 가장 재미있다. 그리고 참고로 이 문제는 도전 정신을 자극했다. 풀릴것같으면서도 풀리지 않아서 오히려 그렇게 느낀 것 같다. 28일전에 풀려고 했다가 다시 2주전에 시도했다가 오늘에서야 완벽하게 풀었다. 아래에서 솔루션을 설명하도록 하겠다. 코드가 꽤 길기..

최근에 백준을 풀던 중 꽤 흥미로운 문제를 발견했다. 시간이 오래걸리기도 했는데 과정에서 꽤 재미를 느꼈다. 또한 배울점이 많은 코드라는 생각이 들어서 첨부했다. 조금 어렵다는 생각이 들기도 했는데 문제 자체가 굉장히 흥미로워서 그냥 붙잡고 불었다. 원래 좀 어려운 문제를 만나면 약간의 스트레스가 생기기 마련인데 이 문제는 그냥 재밌는 문제다. 다른 분들도 이 문제는 꼭 답지 보지 말고 풀어봤으면 한다. 백트래킹 문제인데 부루트포스도 같이 사용해서 풀 수 있는 문제이다. 문제는 아래와 같다. 문제 링크: https://www.acmicpc.net/problem/2529 자 간단하게 dfs 순회하면서 모든 가능한 경우의 대해서 돌아보면 된다. 물론 백트래킹 특성에 따라서 특정 조건에 따라서 가지치기하는 조..

아침에 재밌는 문제를 발견했다. https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A b: continue if curr_pos == b: print(count) break plus_one = int(str(curr_pos) + '1') mul_two = cu..

간만에 재밌는 문제를 만났다. 1576. Replace All ?'s to Avoid Consecutive Repeating Characters 문제인데 문제 자체도 재밌고 풀이 방식을 보던 중 꽤나 기발한 접근법을 보게 되어서 인상깊어서 기록해둔다. 우선 문제 링크는 아래와 같다. https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters/ Replace All ?'s to Avoid Consecutive Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expan..

최근 심심해서 리트코드 문제를 몇개 풀었는데 그 중 재밌는 문제가 몇개 있어서 정리해본다. 1572번 문제이다. EASY인데 첫번째 솔루션에 비해서 코드를 꽤나 효율적으로 개선해서 정리해볼 필요가 있다고 생각해서 적어둔다. 일단 아래는 첫번째 제출한 솔루션이다. 꽤나 비효율적이라는걸 알 수 있다. 일단 for loop 이 두개 있다는것부터 비효율적이다. ''' Runtime: 207 ms, faster than 24.29% of Python3 online submissions for Matrix Diagonal Sum. Memory Usage: 14.1 MB, less than 57.39% of Python3 online submissions for Matrix Diagonal Sum. ''' class..

재밌는 문제를 찾았다. 그리고 최근에 느낀거지만 Leetcode 에서 submit 을 하면 성능과 메모리가 어느정도 되는지 나오는데 그걸 줄여보려고 코드를 바꾸려고 했던 적이 많다. 근데 확실해진건 이걸 기준으로 성능, 메모리 최적화를 하긴 어렵다는 것이다. 그 이유는 그 결과가 항상 다르기 때문이다. 즉 그냥 근사치 정도가 아니다. 90퍼센트 효율이 뜨던 코드가 갑자기 10퍼센트 효율이 뜨는 경우도 있다. 그래서 그냥 이런 성능이랑 메모리 효율성을 따지기 보다 그냥 코드만 보기좋게 다듬는 연습을 하는게 더 낫다는 생각이 들었다. 그런데 마침 오늘 꽤 괜찮은 문제를 발견했고 최대한 코드를 줄여보려고 노력을 했는데 list comprehension의 한계에서 막혔다. 즉 list comprehension ..

꽤 쉬운문제라고 생각하고 풀었는데 생각치 못한 부분에서 막혀서 답지를 보고 푼 문제이다. 참고로 블로그에 기록해두는 이유는 답지를 보고 풀었는데 거기서 꽤 많은 점을 배울 수 있었기 때문이다. 아래는 문제 링크이다. 꽤 간단한 문제이다. https://leetcode.com/problems/valid-boomerang/ 자 그렇다면 내가 처음 접근한 오답을 먼저 보자. (이 코드 안봐도 된다. 아예 틀리기도 했고 너무 부실하다. ) class Solution: def isBoomerang(self, points: List[List[int]]) -> bool: points = sorted(points) last_point = points[-1][0] for i in range(1, 3): if points..

이 문제는 어려운 문제가 아니다. 굉장히 쉬운 문제다. 그냥 지문 그대로 옮겨서 구현만 하면 되는 문제다. 그런데 문제를 풀어낸 솔루션에서 굉장히 재미난 동작을 발견했다. 파이썬 언어차원에서의 동작인것 같은데 처음에는 왜 이렇게 동작하나 의아했는데 꽤나 재밌다는 생각이 들어서 따로 뽑아서 블로그에 정리하고자 한다. 우선 문제 링크는 아래와 같다. 슥 봐도 쉬운 문제임을 알 수 있을 것이다. https://leetcode.com/problems/n-repeated-element-in-size-2n-array/ 그런데 중요한건 문제를 어떻게 풀었냐가 아니다. 문제를 풀어낸 과정에서의 코드 몇줄에서 발생한 신기한 동작이다. 내 솔루션은 아래와 같다. from collections import defaultdi..

최근에 리트코드를 풀고 있는데 696 문제에서 막혀서 수십분 정도를 낭비했다. 이후에 discuss에 있는 솔루션 중 하나를 참고했는데 코드가 너무 이뻐서 올려둔다. class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ #Using the map function to find the combined length of 0 and 1 that are cut apart L = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split(''))) #Because it is limited that only 0 and 1 can be next to ..

실버 2로 랭크되어있는 백준 11060 점프점프 문제이다. 원래 문제풀이는 검색하면 바로 나오기 때문에 필요성을 느끼지 못해서 블로그에 문제풀이 관련 포스팅을 따로 하지 않는데 이 문제의 경우는 좀 아쉬웠다. 메모리 초과로 풀지 못해서 답답한 감이 있어서 포스팅을 하게 되었다. (이 문제는 dp로 풀어내는 방법도 있다고 한다. 처음부터 bfs로 접근했기 때문에 더 아쉬웠다는 생각이 들지만 어차피 어떤 방법으로 접근하든 풀어내는 사람은 문제없이 잘 풀어내기에 단념하고 다른 분들 코드를 읽어보고 있다. ) from collections import deque import sys input = sys.stdin.readline n = int(input()) # 1이라면 시작과 동시에 종료 if n == 1: ..

https://www.youtube.com/watch?v=IJDJ0kBx2LM

쉬운 문제라고 생각했는데, 마지막에 가서 꽤나 고생을 한 문제이다. 어떻게 해결해야할지 전부 떠올렸고 코드까지 모두 작성했지만 사소한 실수때문에 문제가 풀리지 않았다. # 0338 import sys sys.setrecursionlimit(10**7) N = int(input()) graph = [] for i in range(N): graph.append(list(map(int, input().split()))) visited = [[False] * N for _ in range(N)] def dfs(x, y): if x= N or y= N: return False value = graph[x][y] if value == -1: print("HaruHaru") exit(0) if visited[x][y..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 백준 1058문제이다. 처음에는 이 문제가 Y의 영역 중에서 가장 큰 영역을 구하라는 것으로 착각하여 dfs로 풀었다가 오답처리되었다. 문제를 깊게 읽어보지 않은 탓이다. 문제를 조금 만 더 깊게 읽어보면 답을 구할 수 있다. 문제를 잘 읽어보면 친구와의 관계에 대해 나온다. 즉 A와 친구이고, B와 친구인 C가 존재해야 한다. 라는 구문이 존재한다. 즉 한다리 건너뛰어서 친구인 사람이 있어야 된다는..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 백준 유기농배추 문제 이다. sys.setrecurtionlimie()을 써주지 않았을때는 에러가 발생했다. RecursionError인데, 재귀말고 반목문으로 작성해봐야겠다. 만약 시간이 없어서 반복문으로 작성하지 못하였을 경우엔 sys.setrecurtionlimie()에 백만정도로 값을 세팅해주면 문제없이 돌아간다. # 0823 ~ 0858 # 백준 1012 import sys from collectio..

위상 정렬을 공부하는 와중에 이해가 가지 않는 부분이 있는데, 긴가민가해서 정확히 눈으로 확인해보고 싶어 직접 그림으로 풀어보았다. 이해가 가지 않는 부분은 다음과 같다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있습니다. -> 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못합니다. 왜 사이클에 포함된 원소는 어떤 것도 큐에 들어가지 못할까? 라는 생각이 들었는데, 머릿속으로 큐에 집어넣었다가 빼면서 하려니 중간에 실수를 할 수도 있을 것 같아서 바로 그림으로 그려보았다. 다음과 같이 사전에 준비된 그래프가 존재한다. 그리고 보면 알겠지만 (B -> D -> C -> B) 로의 사이클이 존재한다. 그럼 이제 A를 큐에 집어넣고, 간선을 삭제하면 다음과 같이 진행된..

아래 두 코드는 같은 문제를 자바와 파이썬으로 각각 풀어낸 것이다. (오랜만에 풀어봤다.) 이분탐색문제였는데, 이 문제 뿐만 아니라 다른 문제들도 마찬가지로 작성해야할 코드의 양에 있어서 상당한 차이를 보였다. 자신이 가장 편한 언어를 선택하라고 해서 사실 c++과 파이썬, java중 어느 것을 선택하더라도 별 반 차이가 없는 상태에서 시작했었다. 당시에는 숙련도가 모두 비슷했었다. (c++ stl의 사용법을 100프로 알고있던 상태는 아니어서 c++의 경우 숙련도가 조금은 떨어지긴 했다.) 주로 사용하는 언어가 자바여서 자바로 주로 풀이하였는데, 한 문제를 풀면서 python으로도 똑같이 풀어보는 방식으로 진행했다. 한문제를 여러언어로 바꿔서 풀어본적이 대부분이었는데, 여지껏 문제를 풀면서 느낀 점이 ..

괜히 char배열로 받아서 하나씩 비교하다가 빙빙 돌고서야 제대로된 해답을 찾았다. 원형으로 연결하는 것을 굳이 인덱스로 원형으로 따지기 보다는 그냥 output을 하나 더 더해서 원형처럼 효과를 내주는 것이 좋다는 것을 뒤늦에 알았다. 쉽게 말하면 그냥 하나의 String에서 검사해야한다면 그걸 원형으로 돌기 위해서 인덱스를 가지고 연산하는 둥의 고생을 하지 말고 그냥 String 복사본을 뒤에 붙여주는거다. "Hello" + "Hello" = "HelloHello" 가 되는거다. 여기서 돌면 원형으로 도는 것과 비슷한 효과를 얻을 수 있다. 이게 더 간결하다. 그리고 난 뒤에 contains를 이용해서 해당 키워드가 받은 문자열에 존재하는지만 확인하면 되는거다. import java.io.Buffer..

제목과 동일한 질문을 교수님께 여쭤본 적이 있다. 답변은 아주 간단했는데, " MSD부터 정렬하게 되면 정렬이 되지 않습니다. " 였다. 사실 직접 해봤어야 했는데, 그 간단한 과정을 해보지 않고 질문을 해서 지금 생각해보니 조금 멍청한 질문이 아니었나 생각이 든다. 질문할 당시에는 왜 굳이 낮은 자리수부터 비교해야하는가에 대해 생각해보면서 낮은 자리수부터 비교한다면 A, B가 있다고 가정할때 A의 MSD가 B의 MSD보다 큼에도 불구하고 낮은 자리수부터 비교하면서 자리수를 거슬러 올라가는 과정에서는 그 사실을 알지 못함으로 A가 B보다 큼에도 계속해서 낮은 자리수를 비교함으로써 그것이 낭비라고 생각했다. 반면에 MSD부터 비교한다면 처음 비교할때부터 이미 A가 B보다 큼이 기정사실이 되어버리니 그 밑의..

피보나치 구할때는 배열을 한칸 더 선언해줘야한다. 즉 [n+1] 이런식으로 하나 더 만들어놔야 한다. 왜냐면 n의 피보나치수를 구하고 싶다고 했을때 0부터 n-1까지 더한 수가 n에 기록되야 하기 때문이다. 즉 0~n-1은 n개인데 여기서 n칸인 1개까지 더해서 n+1이 필요한거다.

Recursive Call Algorithm (재귀 함수)Permalink Maximum value or Minimum value (최대값 또는 최소값 찾기) : 가장 큰 숫자를 기억해가며 진행함 Euclid (유클리드 알고리즘) : 두 정수의 최대공약수(GCD)를 빠르게 구하기 Factorial (팩토리얼) Fibonacci (피보나찌 수열) Sum (합계) Sorting Algorithm (정렬 알고리즘)Permalink Selection Sort (선택 정렬) https://www.daleseo.com/sort-selection/ Bubble Sort (버블 정렬) https://www.daleseo.com/sort-bubble/ Quick Sort (퀵 정렬) https://www.daleseo...

roka88.dev/98 기본 정렬 알고리즘의 종류와 정리 최종수정일자 : 2020-01-03 이 글은 이미 공부 했었으나, 정렬을 쉽게 정리하지 못하는 사람을 위해 정리하였다. 정렬의 종류도 많으며, 설명하기가 쉽지 않다. 동작은 다양하며, 머리속에 어렴풋이 roka88.dev ict-nroo.tistory.com/category/ICT%20Eng/Algorithm?page=5 'ICT Eng/Algorithm' 카테고리의 글 목록 (5 Page) 주니어 개발자가 성장하는 공간 ict-nroo.tistory.com

package list.doublylinkedlist.implementation; //양방향성이 있는 이중연결시스트. 더 많은 메모리를 사용하는 것이 단점임. public class DoublyLinkedList { private Node head; private Node tail; private int size = 0; private class Node{ private Object data; private Node next; private Node prev; public Node(Object input) { this.data = input; this.next = null; this.prev = null; } public String toString() { return String.valueOf(this..

package list.linkedlist.implementation; public class LinkedList { private Node head; private Node tail; private int size = 0; private class Node{ private Object data; private Node next; public Node(Object input) { this.data = input; this.next = null; } public String toString() { return String.valueOf(this.data); } } public void addFirst(Object input) { Node newNode = new Node(input); newNode.nex..

package algorithm; public class ArrayList { private int size = 0; private Object[] elementData = new Object[100]; public boolean addFirst(Object element) { return add(0,element); } public boolean addLast(Object element) { elementData[size] = element; size++; return true; } public boolean add(int index,Object element) { for(int i = size-1;i>=index;i--) { elementData[i+1] = elementData[i]; } eleme..

리스트와 배열의 차이 리스트에서 데이터를 삭제하면, 해당 데이터가 사라지면서 해당 데이터 뒤에 있던 데이터가 한칸 앞으로 전진하게 된다. 하지만 배열에서 요쇼를 삭제하면, 그냥 그 자리는 비어 있게 된다. (특정한 처리를 해주지 않는이상) 그러므로, 리스트는 데이터가 있는지 없는지를 체크하지 않아도 되는 장점이 있다. 하지만, 배열은 어딘가가 비어있을 수도 있으므로, 데이터가 있는지 없는지 확인해야 한다. 그만큼 리스트보다 더 많은 공간을 차지한다. 하지만 이게 오히려 장점이 될 수 있다. 요소의 자리 (즉 인덱스)값이 바뀌지 않으므로, 배열은 특정 값의 키 즉 인덱스를 유지할 수 있다. 하지만 리스트는 앞의 데이터가 삭제되면, 한칸씩 앞으로 자동으로 당기므로, 인덱스 값이 변한다. 그러므로, 배열에서만..

자료구조와 알고리즘 입문 - 자바편에 힙정렬이 나왔다. 하노이의 탑도 이해가 잘안갔고, 특히 재귀적 호출이 너무 복잡했다. 그래서 일부는 직접 그림판에 그림을 그려서 영상으로 찍어서 내가 하는말을 들어가면서 이해했는데, 글쎄,,, 힙정렬이 좀 이해가 잘안간다. 이해가 안가는건 일단 외우라고 했으니... 일단은 외워야 겠지... 이게 안좋은 방법인건 알고 있다. 근데 일단은 머릿속에 집어넣고 그 다음에 이해해야겠다. package algorithm; public class heap { private void solve() { int[] array = {230,10,60,550,40,220,20}; heapSort(array); for(int v:array) { System.out.println(v); } ..