Razelo 기술노트

이 문제는 어려운 문제가 아니다. 굉장히 쉬운 문제다. 그냥 지문 그대로 옮겨서 구현만 하면 되는 문제다. 그런데 문제를 풀어낸 솔루션에서 굉장히 재미난 동작을 발견했다. 파이썬 언어차원에서의 동작인것 같은데 처음에는 왜 이렇게 동작하나 의아했는데 꽤나 재밌다는 생각이 들어서 따로 뽑아서 블로그에 정리하고자 한다. 우선 문제 링크는 아래와 같다. 슥 봐도 쉬운 문제임을 알 수 있을 것이다. 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으로도 똑같이 풀어보는 방식으로 진행했다. 한문제를 여러언어로 바꿔서 풀어본적이 대부분이었는데, 여지껏 문제를 풀면서 느낀 점이 ..

오랜만에 시간이 남아서 백준 9094문제를 풀어보았다. 티어도 브론즈로 낮아서 쉽게 풀 수 있었는데, 왜인지 속도가 너무 느렸다. 그래서 계속해서 코드를 바꿔보면서 시도했는데도 코드가 너무 느려서 처음에는 반목문안에 있는 sysout 출력문이 문제라고 생각해서 StringBuilder에 결과를 모두 append 해준 다음에 반복문 밖에서 출력해주는 걸로도 바꾸었는데 소용이 없었다. 그러다가 if문 안에 있는 Math.pow(j, 2) 를 j * j 로 바꾸었더니... 결과는 위에 표를 보면 알겠지만., 1556에서 372까지 속도가 줄어들었다. 이제부터는 Math.pow 를 통해 제곱하지 말고 j*j를 통해 그냥 제곱해주자. Math.pow는 반복문안에서 함수를 계속 호출하는 셈이었으니 속도가 느릴 수 ..