목록코딩테스트 알고리즘/탐색 (6)

sooleeandtomas

[day26] 코딩테스트 알고리즘 - 거리두기 확인하기 (feat.파이썬)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv.2 에서 난이도 상 🤟 문제 포인트 #A 대기실은 5개, 각 대기실은 5x5 [[5],[5],[5],[5],[5]] 5크기의 배열 * 5 를 다뤄야 한다. #B 내가 갈 길이 이길이 아닌지 맞는지 알 수 없지만 알 수 없지만 알수없지만 문제를 풀어야 하네 O, X 인지 확인필요 O 인 경우 and 내가 방문안한 곳인지 1. 방문했다고 체크 2. 거리 저장 X 인 경우 아예 고려 안해도됨. 고려할 필요가 없어!!!!!!!!! #C 맨해튼 거리 2 이하 위의 O인경우 저장한 distance 활용 distan..
코딩테스트 알고리즘/탐색 2022. 11. 7. 23:57
[day25] BFS 기초 (1)

😎 BFS (Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 여기서 가장 가까운 노드란 해당 노드와 같은 레벨에 있는 노드들(형제 노드)을 먼저 순회하는 방식이다. BFS는 "큐" 자료구조를 이용한다. 큐는 FIFO의 질서를 가지는 자료구조이다. 😎 BFS 구현 필수 요소 3가지 1. start Node 루트노드같은 시작 노드가 필요하다. 2. visited Nodes 탐색을 중복하지 않도록 visited노드이면 패스한다. 이를 위해 해당 노드가 visited인지 기억을 해놓는다. 3. queue popLeft가 필요하기 때문에 python에서는 deque를 활용한다. from collections import ..
코딩테스트 알고리즘/탐색 2022. 11. 1. 00:28
[day17] 코딩테스트 알고리즘 - 깊이/너비 우선 탐색 (타겟넘버) (feat.파이썬 product)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 설명 문제는 DFS Depth-First-Search 깊이 우선 탐색이다. 문제를 보면 이진트리로 탐색을 한다는 것의 힌트를 얻을 수 있다. 1. 더하거나 빼기 (2가지 경우로 뻗어 나간다) 우선 기준점을 [0]으로 시작한다. 일단 0을 루트노드로 가지는 것이다. 각 노드는 이진트리로 2개의 자식 노드를 가질 수 있다. 이 자식 노드는 각각에 -1 과 +1을 더한 값들이다 . 이렇게 numbers를 전부 탐색하면서 1,-1를 더한 자식 노드를 만들어간다. 결과적으로, numbers의 수들을 빼거나 ..
코딩테스트 알고리즘/탐색 2022. 10. 13. 00:42
[day13] 백준 9095번 완전 탐색 (1,2,3 더하기) python

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 완전탐색의 두번째 문제. 솔직히 이번 문제도 이런 규칮기 있다는 걸 모른다면 풀기 어려울 것 같다. 규칙이 딱히 없는 d[1]=1, d[2]=2, d[3]=4 로 정해놓고 시작한다. 그 다음 수부터는 바로 앞 규칙 수 + 두번째 앞 규칙 수 + 세번째 앞 규칙수를 더한 것과 같다. 이는 d[n-1] + d[n-2] + d[n-3] 으로 적용할 수 있다. 그리고 각 d[n-1] 이 1 혹은, 2 혹은 3이 될 때까지 재귀함수를 돌린다. 참고 코드 import sys N = int(input()) def sol(num): if num == 1: return 1 e..
코딩테스트 알고리즘/탐색 2022. 10. 9. 01:45
[day12] 코딩테스트 알고리즘 - lv.2 완전 탐색 (소수 찾기) python (feat.permutations)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘은 python 문법 폭탄을 맞았다. python의 set, permutations, 병합 업데이트 연산자 |= vs |, extend vs append ... 를 배웠다. 하단에 나와있는 문법들을 참고하여 아래 코드를 보자. 참고 코드 from itertools import permutations def solution(numbers): answer = 0 case = makeCase(numbers) for n in case: if isPrime(n): answer += 1 return answer de..
코딩테스트 알고리즘/탐색 2022. 10. 8. 00:55
[day11] 코딩테스트 알고리즘 - 완전 탐색 (카펫) python

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제는 어렵지 않은 것 같다. (10,2)가 주어졌을 때, 전체의 블록 수를 구한다. => 12 (10 + 2) for문을 돌면서 12의 약수를 구한다. (12 % i == 0) for문은 12부터 2까지 돈다. 아래 이미지처럼 2보다 가로나 세로가 작게되면 가운데 블록이 0개가 되기때문에 2까지만 고려해준다. [12,1],[6,2],[4,3][2,6][1,12] [가로,세로] 이 중에서 (가로-2) x (세로-2) == yellow가 되면 for문 박차고 나온다. 아래 이미지처럼 노란색의 블록 개..
코딩테스트 알고리즘/탐색 2022. 10. 7. 00:27
이전 Prev 1 Next 다음