합니다, 개발공부📝 합니다, 개발공부📝

문자열 찾기 1) longest-substring-without-repeating-characters문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/ 1. 슬라이딩 윈도우 반복되지 않는 가장 긴 문자열의 길이를 반환하는 문제다. (풀고 보니 슬라이딩 윈도우와 비슷한 방식으로 풀었다.)n = 문자열길이, k = 현재 윈도우 길이 (최대 n)이라고 가정할때, temp.contains(), temp.indexOf(), temp.substring(...) + s[i] 모두 O(k)의 시간복잡도를 갖고, 이 연산이 최대 n번 반복될 수 있다. 시간복잡도 : O(n^2) 문자열 연산이 계속 일어나므로 새로운 문자열이..

행렬 채우기 1) set-matrix-zeroes문제 : https://leetcode.com/problems/set-matrix-zeroes/0이 표시된 행렬의 열과 행을 모두 0으로 바꾸는 문제이다. 1. 모든 0위치를 찾아 저장하고 해당 열과 행을 전체 0으로 설정하는 방법 시간 복잡도 : O(m x n) + z (0의 갯수) * (O(m+n)공간 복잡도 : 최대 O(m x n) (0의 갯수를 따로 저장함)class Solution { fun setZeroes(matrix: Array): Unit { if(matrix.size == 0) return val zeros = mutableListOf>() val v = matrix.size ..

Floyd’s Cycle Detection Algorithm - 투포인터 문제   플로이드의 사이클 탐지 알고리즘이란 연결 리스트에서 사이클을 감지하는 문제에서 자주 사용되는 알고리즘으로 토끼와 거북이 알고리즘으로도 불린다. 두개의 포인터를 사용해서 리스트를 탐색하는데, 하나의 포인터는 거북이처럼 한칸씩 이동하고, 나머지 포인터는 토끼처럼 m칸씩 움직인다. (2칸) 만약 사이클이 없다면, 빠른 포인터는 끝(fast.next == null)에 도달하고, 사이클이 존재한다면 느린 포인터를 결국 따라잡게 된다. (slow == fast) 시간 복잡도 : O(n)공간 복잡도 : O(1)  1) linked-list-cycle 문제 : https://leetcode.com/problems/linked-list-c..

Clone Grpah 문제 링크 : https://leetcode.com/problems/clone-graph/description/dfs를 이용해서 deepCopy를 수행하는 문제다. /** * Definition for a Node. * class Node(var `val`: Int) { * var neighbors: ArrayList = ArrayList() * } */class Solution { fun cloneGraph(node: Node?): Node? { if(node == null) { return null } val map = mutableMapOf() return dfs(node, map) } ..

https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 두개의 큐를 놓고 popleft()와 append()를 반복하면서 두 큐의 합을 동일하게 만드는 문제였다. 여기서 과연 for 문을 몇번 돌 것인가가 질문이었으며 처음에는 두 큐의 길이의 최댓값인 6000000번을 돌도록 설정하였으나 이후 다음의 게시글을 참고하여 최대 이동 횟수 (len(queue1)-1)x3 + 마지막 이동 후 검사 1 을 이용하도록 수정할 수 있었다. https://scho..

https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 탐색을 통해서 도형의 모양을 찾고 보드에 넣을 수 있는 도형의 크기의 합을 구하는 문제이다. 먼저, 보드를 돌면서 맞춰야 하는 퍼즐의 모양을 dfs를 통해 탐색하였다. 여기서 position은 가장 기준의 되는 부분을 (0, 0)으로 잡고 상하좌우 네 방향으로 돌면서 기준점에서 이동하는 방향을 통해 block을 구한다. 보드 안에있는 모든 구멍을 다 구해서 block..

https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 탐색을 이용하여 최단 경로를 찾는 DFS/BFS의 문제 유형이다. 겹치도록 제작된 사각형들의 바깥 테두리따라 시작 지점부터 최종지점까지 최단 경로를 구하는 문제이다. 여기서 주의할 점은 칸이 아닌 테두리를 이용하여 경로를 이용하는 것으로 1개 간격으로 테두리 모양을 이룰 경우 이를 같은 칸으로 인식할 수 있기 때문에 보드의 크기와 모든 수를 2배로 하여 경로를 구한 ..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 시뮬레이션 및 구현 유형의 문제이다. 문제의 단계는 다음과 같다. 이동방향은 (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)이다. n*n 만큼의 board와 , m 번의 이동방향 및 이동 카운트가 주어진다. 처음 구름의 위치는 (n-2, 0), (n-2, 1), (n-1, 0), (n-1, 1)이다. 구름이 주어진 ..