본문 바로가기

알고리즘

(28)
[알고리즘, 완전 탐색] 그래프 내 계급 갯수 찾기 보호되어 있는 글입니다.
[bfs 알고리즘][javascript][node.js] 백준 2021번 최소 환승경로 2021번: 최소 환승 경로 (acmicpc.net) 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 기업 입사 코딩테스트에 비슷한 문제가 나왔는데, 시간 안에 못풀었다... 조금만 더 생각하면 풀 수 있었을만한 문제였기에 직접 풀어보았다. 해당 문제의 아이디어는 간단하다. 1. 모든 역을 허브로 본다. 2. 역=허브이며 역Set([레인(노선)]), 레인(노선)Set([역])을 저장한다. 3. bfs를 사용하는데 queue에 역을 push한다. 4. 해당 역에서 갈 수 있는 la..
[대기업공채기출유형] 슬라이딩 윈도우 & 투 포인터 Sliding Window Data Structure: Sliding Window Technique | by Coding Freak | Techie Delight | Medium Window를 한 칸 옮기면 w-1칸은 겹친다 w를 계속 다 더하지 말고 이전 결과를 이용하자 (앞 제거 뒤 추가) 투 포인터 기법 두 개의 포인터를 만듬 각각의 요소에 의미부여 ex) 구간 합 > 투 포인터 사이가 window가 된다. 유사 유형 풀어보기 Find All Anagrams in a String - LeetCode Find All Anagrams in a String - LeetCode Level up your coding skills and quickly land a job. This is the best pla..
야놀자 경력공채 FE직무 코딩테스트 후기 야놀자 | 여행의 모든 것, 한 번에 쉽게 (yanolja.com) 야놀자 | 여행의 모든 것, 한 번에 쉽게 국내 호텔 모텔 펜션/풀빌라는 물론 레저/액티비티에 해외 숙소까지 모두 초특가! 지금 야놀자로 최대 80% 할인받으세요. www.yanolja.com 다들 유형이나 어떤 문제가 나오는지 궁금해서 들어왔을 것이다. 나는 솔직히 이번 코딩테스트는 잘보지 못했다. 아마 딱 커트라인만 넘겼을 것이다. 하지만 문제가 어렵지는 않았다. 문제풀이 시간에 회사 업무 혹은 외부 연락이 너무 잦아서 집중을 못했던것도 있고 내가 준비를 많이 안한 탓도 있기에 망쳤을 뿐이다. 원래 주로 파이썬으로 문제풀이를 하다가 JS로 코딩테스트를 본다는 것을 간과해서 손가락이 꼬여버렸다. 유형은 전형적인 해커랭크 스타일이다. 이..
대기업 코딩테스트 8 : 그래프 이론 https://github.com/ndb796/python-for-coding-test ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 그래프 알고리즘 크루스칼 그리디 알고리즘 위상 정렬 큐 or 스택 그래프 노드와 간선 정보를 가지고 있는 자료구조 연결 트리 최소 힙 부모에서 자식으로 내려오는 계층적인 모델 부모가 항상 자식보다 작은 자료구조 그래프의 구현 방법 인접 행렬 : 2차원 배열을 사용하는 방식 V^2 메모리 공간 시간 복잡도 1 인접 리스트 : 리스트를 활용하는 방식 E 메모리 공간 시간 복잡도 V 서로소 집합(Di..
대기업 코딩테스트 준비 6 : 다이나믹 프로그래밍 다이나믹 프로그래밍 중복된 연산을 줄이자 메모리 공간 활용을 통해 연산 속도 비약적 향상 탑다운 큰 문제를 해결하기 위해 작은 문제 호출 재귀 빅뱅 바텀 업 작은 문제부터 점진적 답 도출 반복문 메모이제이션 다이나믹 프로그램 실행 도중에 여기서는 이런 의미 아님 점화식 인접항 간 관계식 수열을 리스트로 표현 조건 큰 문제를 작은 문제를 나눌 수 있음 작은 문제에서 구한 정답은 큰 문제에서도 동일 메모이제이션 === 캐싱 practice : 1로 만들기 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) for i in range(2, x ..
대기업 코딩테스트 준비 5 : 이진 탐색 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 이진 탐색 순차 탐색 : 맨 앞에서부터 하나씩 확인 정렬되지 않은 데이터 이진 탐색: 정렬된 데이터 ​ O(logN) 파라메트릭 서치 최적화 문제 > 결정 문제 원하는 조건을 만족하는 가장 알맞은 값 찾기 범위가 어마어마하게 큰 조건 떡 썰기 필요한 길이보다 크면 시작점 증가 필요한 길이보다 크면 끝점 감소 ..
대기업 코딩테스트 준비 5 : 정렬 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 정렬 데이터를 특정한 기준에 따라서 순서대로 나열 그리디랑 자주 쓰임 이진 탐색 계수 정렬을 꼭 써야 하는 경우가 아니면 기본 제공 정렬 라이브러리를 활용한다. 선택 정렬 for i in range(len(arr)): minIdx = i for j in range(i+1,len(arr)): if arr[min..