목록Computer Science/Algorithm (10)
재 현
탐색이란 ? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 것 사전 지식 1) 스택 자료구조 (박스 쌓기) 2. 큐 자료구조 ( 파이썬에선 deque 활용) 3) 재귀함수 * 재귀함수 (Recursion Function) : 자기 자신을 다시 호출 def recursive(i): recursive(i) #재귀함수는 종료조건을 반드시 명시해야한다. if i == 100: return #팩토리얼 함수 def factorial(n): if nb if a % b == 0 return b else: return gcd(b,a%b) * DFS ( Depth First Search) - 깊이 우선 탐색 - 그래프의 깊은 부분을 우선 탐색 - DFS는 스택자료구조 or 재귀함수를 사용한다 1. 탐색 시작 노드를 스..
기초 배경지식 + 구현력 1) 기초 배경지식 [코딩 문법, 시·공간 복잡도] + 자료구조 [ 배열, 트리, 그래프, 힙, BST, 스택 ,큐] + 알고리즘 [ DFS, BFS, 정렬, 백트래킹, DP, 분할정복, 최단거리] 2) 구현력 백준 랭작 -> 양질 문제 #컴퓨팅적 사고력 ( 배경지식을 공부했어도 문제 접근조차 못할 때) 한정된 시간복잡도 & 할당된 메모리를 머릿속에 생각하며 문제 풀기 => BOJ 모든 [별찍기] && [n,m] 시리즈 && SWEA 난이도 1~2문제 많이 풀기 #요즘 코테에 자주 출제되는 유형 dfs, bfs, 최단거리, dp, 해쉬, 이분탐색, 완전탐색, 투포인터, 문자열 # 알고리즘 삼성SW테스트에선 초급에서만 출제. 알고리즘 초급 : 완전탐색, DP초급, 큐, 스택, DF..
구현 = 시뮬레이션 + 완전탐색 머릿 속 알고리즘을 소스코드로 구현 풀이는 쉽지만 소스코드로 옮기기 어려운 문제 구현 ex) 1. 알고리즘은 간단한데 코드가 길어지는 문제 2. 실수연산을 다루고, 특정 소수점 자리까지 출력 3. 문자열을 특정한 기준에 따라 끊어 처리 4. 적절한 라이브러리 찾아 사용 [요구사항대로 구현] # 2차원 공간 시뮬레이션 및 완전탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용 dx = [0,-1,0,1] dy = [1,0,-1,0] x,y = 2,2 for i in range(4): nx = x+dx[i] ny = y+dy[i] print(nx,ny) # 시뮬레이션 # L R U D dx = [0,0,-1,1] dy = [-1,1,0,0] move_types = ["L..
거스름돈 (큰 단위가 작은 돈의 배수라면) n = 1260 count = 0 array = [500,100,50,10] for coin in array: count += n // coin n %= coin print(count) #화폐의 종류 k -> O(K) data = input() result = int(data[0]) for i in range(1, len(data)): num = int(data[i]) if num