Coding Test (17) 썸네일형 리스트형 [코딩 테스트 합격자 되기] 백트래킹 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=VvcEx75Bgvk&t=1s[백트래킹의 개념]가장 최근에 방문했던 노드로 다시 돌아감완전 탘색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색[백트래킹을 푸는 과정] [c++ 코드]상태 정의 : 문제의 각 단계에서 가능한 상태를 정의유망 함수 (isPromising) : 현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색 X해결책 확인 (isSolution) : 현재 상태가 문제의 해결책인지 판단재귀 호출 : 유망한 상태로 이동하면서 문제 해결[예제]부분합N-Queen추천 문제 https://school.programmers.co.kr/learn/courses/30/lesson.. [코딩테스트 합격자 되기] 그래프 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=OmYQsxreXNo&embeds_referring_euri=https%3A%2F%2Fwww.inflearn.com%2F&source_ve_path=MjM4NTE [그래프의 구현 방법]인접 행렬 [c++ 코드]행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 됨노드 대비 간선이 적을 경우 메모리 공간 효율이 좋지 않음인접 리스트 [c++ 코드]특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비 없음특정 노드에 모든노드가 연결된 경우, 탐색시 O(N)이 될 수 있음 (드문 케이스) [DFS와 BFS]c++ 코.. [코딩 테스트 합격자 되기] 집합 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=pQ4fcGEG-PY [목차]상호배타적 집합이란?집합의 연산union 연산과 find 연산경로압축 / 랭크기반 알고리즘으로 개선하기집합의 구현상호배타적 집합 : 교집합이 없는 집합관계 [집합의 표현] [집합의 연산]find : 특정 노드의 루트 노드를 확인하는 연산- 특정 노드부터 루트노드가 나올 떄까지 거슬러 올라가기- union 연산에서도 활용됨- 경로 압축 : find 연산을 할 때 루트노드를 찾는 과정에서 거쳐간 노드들의 경로 압축 - 경로 압축 후 find 연산의 시간 복잡도 : O(N) -> O(1) union : 두 개의 집합을 하나의 집합으로 합치는 연산- find 연산을 통.. 백준 1일 1코테 D+100 요즘 사이드 프로젝트 개발하는게 재밌어서 하루종일 하다보니코테를 밤 늦게 하게된다. 이전처럼 시간을 많이 투자하지 못하고 있는 상황인데,오늘자로 백준을 꾸준히 한지 100일째 되는 날이다. 상반기를 어영부영 끝내고나서 1일 1코테를 하리라 다짐했기에어떻게보면 취준을 본격적으로 시작한지 100일즈음 되었다는 얘기다. 마지막으로 LG 인턴 면접을 본게 6월 말인데 시간참 빠르다그 이후로 영어 공부, 개인 프로젝트 하느라 회사 지원을 못했는데이제 다시 면접 준비도 하고 지원도 슬슬 시작해야겠다.파이팅 [코딩 테스트 합격자 되기] 트리 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=CXiVJgUjL6o&embeds_referring_euri=https%3A%2F%2Fwww.inflearn.com%2F&source_ve_path=MjM4NTE [트리 용어]차수 (degree) : 노드의 자식 수노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수[이진 트리 표현 - 배열]루트 노드 인덱스 : 1왼쪽 자식 노드 : 부모 노드 인덱스 * 2오른쪽 자식 노드 : 부모 노드 인덱스 * 2 + 1구현 쉽지만, 빈 공간이 많음 (메모리 공간 낭비) [이진 트리 표현 - 인접 리스트]각 리스트의 인덱스는 부모 노드자식 노드는 부모 노드에 해당되는 인덱스에 추가공간 활용도가 .. 알고리즘 문제 오답 노트 오답 노트알고리즘 문제를 풀며 틀린 원인 분석 및 새로 알게된 부분 정리 코딩 테스트 전 한번 보고 갈만한 노트1. 출력값에 % 10 (마지막 자리 수만 출력) 을 요구할 때는 조건을 모두 고려해서 계산 후 최종 값에 % 10 계산 필요 ex) 백준 16946 벽 부수고 이동하기 4 : 틀렸습니다 -> 맞았습니다2. 배열 크기가 너무 크면 배열 초기화에도 시간이 걸림 아래 코드 주석 부분 (방문 확인을 위해 checked 배열 사용) 을 set 으로 변경하여 시간 초과 해결 ex) 백준 16946 벽 부수고 이동하기 4 : 시간초과 -> 맞았습니다# count the number of grids can be movedcan_move = [[0] * M for _ in range(N)]f.. [코딩 테스트 합격자 되기] 해시 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=KsfmSyIYX3g&t=3s 배열의 경우 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함 O(n)contents 자체를 가지고 위치 (index)를 알 수 있는 것이 해시 해시 함수를 사용해서 변환한 값을 인덱스(해시값)로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 O(1) 해시함수 : 임의의 키를 해시테이블의 인덱스로 변경해주는 함수해시 테이블의 크기가 N이라면 해시함수는 0 ~ (N-1) 사이 값을 내야 함충돌을 최소화 할수록 좋은 해시함수* 충돌 : 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환하는 것 [해시함수 종류]나눗셈법 : h(.. [코딩 테스트 합격자 되기] 스택/큐 [인프런] 코딩 테스트 합격자 되기 C++강의 링크 : https://www.youtube.com/watch?v=-TGCT74wFeg&t=2s FILO (First In Last Out)사용 예시 : 함수 호출 관리, 페이지 탐색, 괄호 짝 맞추기- 가장 최근 원소를 봐야하는 경우 사용- 추후 DFS, 백트래킹에서 사용 FIFO (First In First Out)사용 예시 : 줄 서기, 요세푸스 문제 - 들어온 순서대로 나갈 때 사용- 추후 BFS에서 사용[풀이할 문제] (스택/큐 관련문제, 필수풀이) 괄호 회전하기(문제 10)=> https://school.programmers.co.kr/learn/courses/30/lessons/76502주식 가격(문제 12)=> https://school.pro.. 이전 1 2 3 다음
