본문 바로가기

전체 글60

이것이 코딩테스트다 3일차 - 그리디 1. 그리디란?현재 상황에서 지금 당장 좋은 것만 고르는 방법 따라서 최적의 해가 나오지 않을 때가 많다 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 (정렬, 최단경로 등은 이미 알고리즘 사용법을 정확히 알아야 한다.) 최단경로 문제는 플로이드워셜 or 다익스트라를 이미 알고 있어야 한다 (다익스트라 알고리즘은 그리디 알고리즘으로 분류되긴 한다) 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓어서 단순 암기만으로는 안 된다 많은 유형을 풀어봐야 한다! 훈련! 창의력, 문제를 풀기위한 최소한의 아이디어를 떠올리는 능력을 요구한다. 1.1 문제가 이렇게 나오면 그리디를 고려하자단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀수 있을 때알게모르게 가장 큰 순서대로,.. 2023. 6. 2.
이것이 코딩테스트다 2일차 - 파이썬 문법 : 입출력, 라이브러리 입출력데이터를 입력받을 때는 문자열로 입력받는다.input()따라서 입력받은 데이터를 정수형 데이터로 처리하기 위해서는 정수로 바꾸는 int함수 사용int(input()) 여러 개의 데이터를 입력받을 때는 데이터가 공백으로 구분되는 경우가 많다 입력받은 문자열을 띄어쓰기로 구분하여 각각 정수 자료형의 데이터로 저장하는 코드의 사용빈도가 매우 높다list(map(int,input().split())) #입력받은 값을 공백기준으로 split하여 리스트 만듦 #map 함수로 리스트의 vlaue들을 int형으로 변환 #변환한 값들을 다시 list로 만듦 전형적인 소스코드n=int(input()) data=list(map(int,input().split())) # data.sort(reverse=True)등등 공.. 2023. 5. 31.
이것이 코딩테스트다 1일차 - 파이썬 문법 : 자료형과 함수 부록A2부 이론3부 문제 - 최소 3회이상 ADVICE책의 문제를 푼 다음 동일 유형의 문제 온라인 저지 사이트에서 풀어보기 if 그리디 풀었으면 그리디 다풀어보기(백준)책을 보는 동안에는 책에만 집중 (문제를 많이풀고 복기하는 방법)복기한 내용은 기록 -> 훌륭한 요약집문제해결에 대한 접근방식, 풀이방식을 기억 및 설명파이썬 문법자료형은 자동 무한 : INF, 최댓값이 있을 때는 예를들어 1e9(1,000,000,000)와 같이 설정 실수형의 연산에서는 정확한 값이 나오지 않을 수 있다. 메모리에 저장되는 값이 현실과 다름 보통 소숫점 다섯번째 자리에서 반올림한 값이 같으면 맞았다고 인정하기 때문에 a라는 변수가실수 이면answer = round(a,4) Return answer 거듭제곱 연산자 ** .. 2023. 5. 31.
탐색 DFS, BFS 이것이 코테다 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 중요한 자료구조스택 - DFS / python : list큐 - BFS / / python : deque (list는시간복잡도가 높음 - pop은 원소를 꺼낸 후에 이동 함)중요한 함수재귀함수 - 컴퓨터 메모리 - 스택 자료구조종료조건 반드시 명시 DFS동작 기본 - 재귀, 스택, 그리디 조건에 맞는 인접노드의 인접노드 계속 방문, 방문처리, 스택에 쌓음. 방문할 노드가 없으면 최상단 노드를 스택에서 제거, 그 다음 노드의 인접노드 방문, 방문처리, 스택에 쌓음. 반복 BFS동작 기본 - 재귀, 큐, 최단경로 탐색 시작 노드를 큐에 삽입, 방문처리 큐에서 꺼낸 노드의 인접노드중 방문하지 않은 노드를 모두 큐에 삽입, 방문하고 방문 처리 반복 2023. 5. 25.
11. java 템플릿 메소드 패턴 추상 클래스를 가장 많이 쓰는 경우 : 템플릿 메소드 패턴 when? controller를 만드는데 종류가 여러개인 상황 recommend? 사용자는 무조건 초기화 -> 실행 -> 마무리의 순서로 작동시키기 원한다 사용자가 특정 메소드에 접근하지 않게 하여 controller 오작동을 막아야 한다 1,2번 : 종류가 여러개지만 작동 순서가 같은 controller의 structure 필수 작동 순서 초기화 - 같은 코드 실행 - 다른 코드 마무리 - 같은 코드 무조건 위와 같은 순서로 동작되는 controller 템플릿을 만든다 3번 : 사용자의 controller에 대한 메소드 접근을 제한시킨다 (최초부모클래스인) controller abstract class의 접근 제한자를 변경시킨다. 메소드를 선언.. 2023. 5. 23.
chapter09 알고리즘 그래프(1) 버스노선 시공 일정 네비게이션의 경로탐색 -> 최소신장트리, 최단경로탐색으로 해결 9.1 그래프의 개요 9.1.1 그래프의 탄생 쾨니히스베르크 도시를 가로지르는 다리들을 한번만 건너서 순회하는 방법을 찾다가 고안 되었다 해결법은 한붓그리기 : 홀수개의 선으로 연결된 점이 없거나 두개인 도형에서만 가능하다. 9.1.2 그래프의 정의 V : 정점의 집합 E : 간선의 집합 G: 그래프 =(V,E) 길이 : 정점과 정점 사이에 있는 간선의 수 인접(또는 이웃관계) : 간선으로 연결된 두 정점 경로는 길이를 가지는데, 길이는 정점과 정점 사이의 간선의 수이다. 사이클(Cycle) : 어느 경로가 정점 하나를 두 번 이상 거치도록 되어있을 때 (트리에서는 볼 수 없다) 방향성 그래프 : 간선에 방향성이 있을 대 .. 2023. 5. 17.

티스토리툴바