Bonfire

Leetcode Find if Path Exists in Graph시작점과 끝점이 주어진 간단한 그래프 문제처음 나는 dfs 문제로 풀었다가 메모리나 속도가 다른 풀이들에 비해 떨어지는 것을 확인하고, bfs로 코드를 바꿨다.그러고나니 메모리는 상위 0.5%정도 됐다. (근데 웃긴건 몇번 돌려보니 결과가 상당히 랜덤이었다..)나의 코드from collections import dequeclass Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: graph=[set() for _ in range(n)] visited=[False for _ in ..

잡설더보기어제는 사실 챌린저 문제로 방의 개수라는 그래프 문제가 나왔다.권장시간이 4시간이기도 했지만, 요즘 너무 바쁜 일정에 PS하듯 고민할 시간이 없어 일단 TIL은 제출하고, 추후에 곰곰히 고민해서 공부할 예정이다. 무작정 1시간 고민하고 답을 보는건 지금 별로 좋지 않은것 같다..일단 점이 이동하면서 다시 만나면 도형이 생성된다는 것까지는 생각해보았으나.. 시간문제로 미들러 문제인 가장 먼 노드르 대체한다. 프로그래머스 가장 먼 노드나는 이 문제를 힙을 사용한 다익스트라를 활용해서 풀었다.시작이 노드1로 고정되어있기 떄문에 모든 정점까지의 거리를 구한뒤 최대 크기를 구하면 되는 간단한 문제였다.나의 코드def solution(n, edge): import heapq graph=[[] f..

K-th Smallest Prime Fraction오늘의 이분탐색 문제였는데.. heap 자료구조로 풀었다.내 접근 방법은 다음과 같다.가장 작은 수는 맨 앞 수인 1과 맨 뒤에 있는 임의의 수인 arr[-1]로 나눈 값이다.그렇다면 그 다음 작은수는 자연스럽게  - 분자가 1 다음에 나오는 수 또는 분모가 맨뒤 앞에 나오는수로 둘 중 하나를 바꿔주면 된다. 그 둘을 힙 구조에 넣고, 가장 작은 값을 빼면, 항상 가장 작은 값이 나오므로, 답을 구할 수 있다.주의해야할 점은 중복이 생기지 않게 해야한다는 점인데, 나는 그냥 튜플로 순서쌍을 저장해서 체크했다.  나의 코드class Solution: def kthSmallestPrimeFraction(self, arr: List[int], k: int..

JAVA 자료형과 제어문자료형자료형의 선언str B = "Hello"Call by value값을 저장 ("HELLO")Call by Reference위치를 저장 (B)변수 이름 작성 유의사항숫자로 시작 불가특수문자는 $, _ 만 사용 가능변수이름에 **$**만 주는 건 가능하나, **_**만 주는건 불가능키워드 사용 불가일반적으로 많이 쓰는 이름 작성시 대소문자Package, Webfile 같은 것은 소문자로 작성Class만 대문자로 시작하도록 작성상수명을 작성시 전부 대문자로 작성, 단어를 여러개 결합시 가독성을 위해 밑줄을 사용.변수의 생존 기간변수는 선언된 시점에서 생성된다.생성된 변수는 자신이 선언된 열린 중괄호{ 의 쌍인 닫힌 중괄호} 를 만나면 메모리에서 삭제된다.자료형의 종류기본 자료형참조 ..

프로그래머스 도둑질오늘의 문제도 DP문제다.이 문제는 원형 DP 문제로 백준에도 RGB거리 2라는 비슷한 DP 문제를 풀어 봤었다.https://www.acmicpc.net/problem/17404보자마자 어떻게 풀지 방향성이 정해져서 몇번 시도 후 바로 정답을 구할 수 있었다.핵심 아이디어는 기본적인 DP처럼 1을 골랐을때, 안골랐을때 => 2를 골랐을 때는 1을 안고른 누적합을 참고하고, 2를 안골랐을때는 1을 고른 누적합을 참고하면, 결과적으로 연속되지 않은 경우들을 골랐을때의 최대 합을 구할 수 있다.1을 고르면 => 마지막것은 못고르는 것 중 최대2를 고르면 => 마지막것을 고르거나 못고른 것 중 최대나의 코드def solution(money): # 1. dp1 0번째를 골랐을때 # ..