코딩 오름길

처음에 풀 때는 5까지 구해보고 풀어봤다. •n = 1 -> (1) 1개 •n = 2 -> (1 + 1) , (2) 2개 •n = 3 -> (1 + 1 + 1), (2 + 1) ,(1 + 2), (3) 4개 •n = 4 -> (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2+ 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1) 7개 • n = 5 -> (1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 1 + 2 + 1), (1 + 1 + 3), (1 + 2 + 1 + 1), (2+ 1 + 1 + 1), (1 + 2 + 2), (2 + 1 + 2), (2 + 2 + 1), (1 + 3 + 1), (3 + 1 + 1), (2 + 3), (3..

https://leetcode.com/problems/subsets/ Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 입력값이 [1,2,3]일 때 그림과 같은 간단한 트리를 구성한다면 이를 DFS하여 원하는 결과를 출력 할 수 있다. def dfs(index, path): ... for in range(index, len(nums)): dfs(i + 1, path + [nums[i]]) 경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태..

그래프 순회 - 그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정 - 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversals)에는 크기 깊이 우선 탐색(Depth-First Search)과 너비 우 선 탐색(Breadth-First Search)의 2가지 알고리즘이 있다. - 일반적으로 많이 쓰는 것은 DFS이다. DFS VS BFS - DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 백트래킹을 통해 뛰어난 효용을 보임 - BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. * DFS(깊이 우선 탐색) - 일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. - 코딩 테스트 시에는 재귀 구현이 더..

https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을때, 섬의 개수를 계산해라(연결되어 있는 1의 덩어리 개수 를 구하라) 풀이 1) DFS로 그래프 탐색 from typing import List def numIslands(self, grid: List[List[str]]) -> i..

https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 내가 푼 코드 if 문 안에서는 뇌에 흐름대로 잘 적었는데 else if 에서 좀 생각을 했던 것 같다. def solution(progresses, speeds): answer = [] time = 0 # 시간변수 count = 0 # 카운팅변수 while len(progresses): if (progresses[0] + ..

풀이) 풀이를 보면 굉장히 쉬운 문제다. 정답률이 20%대라는게 믿기지 않는 문제고, 나는 기존에 input() 함수만 입력값을 넣는 줄 알았는데, 찾아보니까 sys.stdin.readline 이라는 게 있었다. from sys import stdin, stdout n = stdin.readline() N = stdin.readline().split() m = stdin.readline() M = stdin.readline().split() for l in M: stdout.write("0\n") if l not in N else stdout.write('1\n') input 대신 sys.stdin.readline 쓰는 이유 - 여러 줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 ..

문제 파악 상위 k번 이상 등장하는 요소를 추출해라 예를들어, k = 2 이면 output [1, 2]가 나오고, k = 3이면 [1 , 2 ,3] 이 나온다. 문제풀이 1) Counter를 이용한 음수 순 추출 - 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우선순위 큐를 이용해 상위 k번 만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출 할 수 있다. - 파이썬에서 우선순위 큐는 힙을 활용하는 heqpq 모듈을 사용한다. # 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, # 우선순위 큐를 이용해 상위 k번만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다. def topKFrequent(self, nums: List[int..

문제. • put(key, value) : 키 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. • get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다. • remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다. MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // 1을 리턴한다 hashMap.get(3); // -1을 리턴한다(키가 존재하지 않음) hashMap.put(2, 1); // 값을 업데이트한다 hsahMap.get(2); // 1을 리턴한다 hashMap.remove(2); // 키 2에 해당하는 키, 값..

이 문제는 직접 구현했다. 직접 구현하니까 기분은 좋네요. deque만 알면 쉬운 문제였던 것 같다. deque 를 쓰면 시간복잡도도 많이 감소하니까 deque는 진짜 좋은 메소드인거 같다. 여기서 list를 쓰고 했으면 시간복잡도가 증가해서 좋은 코드가 되진 않을 것 같다. from collections import deque N = int(input()) deque = deque(range(1, N + 1)) while (len(deque) > 1): deque.popleft() #맨 왼쪽값 삭제 move_num = deque.popleft() deque.append(move_num) # move_num 뒤로 append 해주기 print(deque[0])

문제: - push(x) : 요소 x를 큐 마지막에 삽입한다. - pop() : 큐 처음에 있는 요소를 제거한다. - peek() : 큐 처음에 있는 요소를 조회한다. - empty() :큐가 비어 있는지 여부를 리턴한다. MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.push(); // 1 리턴 queue.pop(); // 1 리턴 queue.empty(0; // false 리턴 문제 그대로 스택을 이용해서 큐를 만드는 문제 생각해본 것 1) 스택 FIFO, 큐 LIFO 2) push할때 값을 역순으로 배치를 해보자. -> 도저히 안풀려서 책을 보니 스택하나로는 문제풀이 x 무한반복 문제풀이) 스택 2개 사용 class MyQue..