Programming

DFS (깊이 우선 탐색 알고리즘) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 BFS (너비 우선 탐색 알고리즘) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘 문제 해설 DFS 유형 : 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결 → 그래프 형태로 모델링 ex) 001 010 101 이라는 예시에 대해서 다음의 그래프로 모델링 할 수 있다. '0' 으로 상, 하, 좌, 우 연결된 노드를 묶으면 다음의 세 묶음이 나온다. 묶음을 찾아주는 프로그램을 DFS로 작성할 수 있다. 1. 특정한 노드의 주변 상, 하, 좌, 우를 살펴본 뒤, 주변 노드 중에서 값이 '0'이면서 방문하지 않은 노드가 있다면 방문 2. 방문한 노드에서 다시 상, 하, 좌, 우를 살펴보..

DFS (깊이 우선 탐색 알고리즘) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 * 그래프 노드(Node)(=정점) 와 간선(Edge) 으로 이루어져 있음 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 '두 노드는 인접하다' : 두 노드가 간선으로 연결되어 있음 그래프의 표현 방식 인접 행렬(Adjacency Matrix) : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 파이썬에서는 2차원 리스트로 구현 연결되지 않은 노드끼리는 무한(Inf) 비용으로 작성 차이점 : 모든 관계를 저장, 노드 개수 많을수록 메모리 불필요하게 낭비, 노드 연결 정보 얻는 속도 빠름 ex) 인접 행렬 방식 예제 INF = 999999999 # 무한의 비용 선언 # 2차..

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입(Push) : 데이터 삽입 삭제(Pop) : 데이터 삭제 cf) 오버플로(Overflow) : 저장 공간을 벗어나 데이터 넘쳐흐를 때 언더플로(Underflow) : 데이터 전혀 들어 있지 않은 상태에서 삭제 연산 수행할 때 스택 : 박스 쌓기, 선입후출 or 후입선출 별도의 라이브러리 사용할 필요 없음 append() : 리스트 가장 뒤쪽에 데이터 삽입 pop() : 리스트 가장 뒤쪽에서 데이터 꺼냄 stack = [] # 삽입(5) - 삽입(2) - 삭제() - 삽입(3) stack.append(5) stack.append(2) stack.pop() stack.append(3)..

구현 코딩테스트에서 자주 출제되는 유형 (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제 피지컬을 요구하는 문제 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우 구현하기 어려운 문제 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 ..

구현 코딩테스트에서 자주 출제되는 유형 (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제 피지컬을 요구하는 문제 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우 구현하기 어려운 문제 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 ..

구현 코딩테스트에서 자주 출제되는 유형 (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제 피지컬을 요구하는 문제 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우 구현하기 어려운 문제 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 ..