keicoon15

https://leetcode.com/problems/isomorphic-strings/ 205. Isomorphic Strings Easy Topics Companies Given two strings s and t, determine if they are isomorphic. Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same charac..

Graph ( node - edge ) 구조에서 PathFinding 의 해결 방법인 "A star" 의 구현입니다. A* 알고리즘의 구현 예로 2 차원 배열을 자주 사용하는데, wiki 의 pseudocode 를 참고하여 작성했습니다. wiki 에서는 없는 "Visited" 를 두어 탐색을 마친 node 를 재방문하지 않도록 했습니다. heuristic func ( H ) 는 func 로 두어 자유롭게 작성할 수 있습니다. 먼저, Edge 를 두어 노드 사이의 간선의 이동 비용 ( Cost ) 를 두었습니다. 이는 Path 의 재구성 ( 탐색 종료 이후 ) 에도 재사용됩니다. // relation of graph node class Edge { // src, des is Node constructor(..

Maximum Subsequence Score - LeetCode Maximum Subsequence Score - LeetCode Can you solve this real interview question? Maximum Subsequence Score - You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k. For chosen indic leetcode.com nums1, nums2 주어진 숫자 배열에서 k 개의 index 를 뽑아, nums1 에서는 총합..

Kth Largest Element in a Stream - LeetCode Kth Largest Element in a Stream - LeetCode Can you solve this real interview question? Kth Largest Element in a Stream - Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Implement KthLargest class: leetcode.com 주어지는 배열에서 "k" 번째로 큰 수를 찾는 문제입니다. 큰 수라는 내용에..

https://school.programmers.co.kr/learn/courses/30/lessons/150364 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 트리에서 1, 2, 3 의 공을 내려보내 각 노드가 원하는 값을 갖는 공의 순서를 찾는 문제입니다. 트리를 만드는 과정은 DS 를 구현해서 진행했습니다. 이후 트리의 각 노드에서 순서가 변경되는 로직이 있고 이 부분도 노드 구현에 반영한 flow 함수를 구현했습니다. 처음에는 공의 경우의 수를 따라가며 backtracking ( 가지치기 ) 로 접근했는데 몇몇 케이스에서 "시간 초과" 가..

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 맵에서 시작 지점과 도착 지점이 주어진 상태로 k 거리로 도달 가능한 경로를 찾는 문제입니다. 최단 거리가 아닌 k 거리의 위치를 찾아야 하고, 도달 가능한 경로 중에서 알파벳 정렬이 가장 빠른 조건이 붙기 때문에 몇 가지 예외 처리가 필요합니다. 우선, dfs 와 같은 탐색을 통하면 k ( 입력 최대 값 ) 이 크기 때문에 시간이 오래 걸릴 수 있습니다. 그것과는 별개로 문제와 주어진 ..

https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제이다. 표 ( table ) 의 기능들 ( update, replace, merge, unmerge, print ) 을 구현하면 된다. 가장 성능에 민감한 기능은 replace 로 N^2 가 소요된다. 이 부분은 mapping table 을 두어 개선할 수 있지만 문제가 시간 복잡도에 민감하지 않으므로 구현을 가져갈 수 있다. 그 다음으로 merge 기능의 예외 처리가 필요한데 동일 셀..

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이진 트리로 구성 가능한지 판단하는 문제이다. 이진 트리를 구성 하는 룰에 따라 LeafNode ( 자식이 없는 마지막 노드 ) 가 있다면, 그 부모의 노드도 있어야 하기에 이진법으로 변환한 값을 보고 부모의 여부를 판단할 수 있다. 입력된 값을 이진법으로 변환한 뒤 인덱싱을 위해 암묵적 ( 문제의 점선 ) 노드를 모두 생성한 뒤 ( white space ) 왼쪽, 오른쪽의 노드가 있으면서 부모..

https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 입력 파라미터 값의 제한을 보고 시간 복잡도를 걱정할 문제라고 생각이 안들었다. 시간 복잡도가 필요하다면 좋은 아이디어로 접근해야 한다. 문제 풀이는 전체 경우의 수 ( 최대 4^7 ) 의 케이스에서 Best 를 찾아본다. 할인율은 10, 20, 30, 40 ( 총 4 개 ) 의 케이스이기에 n 개의 이모티콘의 경우의 수를 만들고 ( N ) 유저의 수 ( N ) 에서 이모티콘의 구입과 서비스 가..

https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 택배 배달과 수거하는 과정을 만족하면서 최소 이동 거리를 구하는 문제이다. 택배 배달과 수거하는 과정은 배달을 끝내고 수거를 하는 과정에 연속이며, 택배를 배달하면서 이동한 거리만큼은 다시 물류센터로 돌아오기 때문에 수거하는 과정을 같이 진행할 수 있다. 모든 집에 배달 및 수거를 진행하기 위한 순회 ( N ) 과 집 마다 배달 및 수거를 분배하는 순회 ( N ) 이 요구된다. O ( N^2 )..