알고리즘

시 : 시간복잡도이 : 입력 크기바 : 바깥 경우(코너 케이스)알고리즘 문제를 푼다는 것이 어떤것을 공부하는 것인지에 대해 연구중에 있음PS 를 푼다는 것의 목적은짧은 시간안에 제한시간내에 풀리는 알고리즘 구현(이게 가장 중요한게 정보 올리피아드도 절반 이상은 골실 문

https://zoomkoding.github.io/codingtest/2019/09/09/coding-test-list.html

링크

\[^\\n]의 의미는 \\n이 있을 때까지 읽는 것이고이게 없을때는 0을 반환하여 탈출하게 된다.단 반드시 배열만 사용해야 한다.\`하면 이제 M_PI를 사용 가능memset은 배열이든 벡터든 원하는 행열은 모두 채워주는 함수이다.으로 초기화 해줄 수 있다.

그냥 순진하게 모든 경우를 하면 시간, 공간 복잡도 측면에서 비효율적모든 선택지를 고려하지 않고, 각 단계마다 지금 가장 좋은 방법만을 선택 -> 즉 사용자가 처음부터 어떤 케이스만을 고려하게 된다.이때 정당성 증명이 굉장히 중요하다.그리디 알고리즘이 항상 성립할까?

어떤 수 N이 주어졌을 때, 숫자를 섞어 30의 배수를 만드는 문제30을 소인수 분해하면 2x3x5=30이다. 이때 2의 배수는 2,4,6... 3의 배수는 모든 자리 다 더한 값이 3의 배수, 5는 끝자리가 5와 0인데 2의 배수 때문에 끝자리는 0으로 고정된다.그리

스택 문제 9093 단어 뒤집기 문자열 관련 문제를 다룰때는 한 문자씩 다루기 보다는 String으로 한번에 읽어 들여서 처리하는 것이 훨씬 편리하다. 읽어들일 때 getline 함수 사용하기 getline 함수는 string.h 와 string 라이브러리 두개에

그냥 풀면 시간 없는 문제

브루트포스 문제중에서 순열문제는 결코 그냥 푸는 문제가 아님문제의 핵심 키워드는을 얼마나 요긴하게 사용하는가 이다.우선 그냥 브루트 포스를 하더라도 시간이 오래걸린다.부등호 문제는 대표적인 순열문제를 확인할 수 있는데우선 그냥 브루트 포스로는 결코 풀리지 않는다는 점이

임의의 수열을 다른 순서로 섞는 연산그래서 순서가 매우 중요한 의미를 가지고 있을때 사용한다.(123 != 132)총 N!개가 존재하고 모든 순서를 다 시도해봐야 할때. 숫자의 나열이 입력으로 들어오면 사용하는 경우가 많음11! 이하인 브루트 포스에서 숫자 나열인 문제

BFS의 목적은 임의의 정점에서(시작점) 시작해서, 모든 정점을 한 번씩 방문하는 것이다.BFS는 최단거리를 구하는 알고리즘 = 최소비용 문제(<-> DFS 는 최단거리를 구할 수 없음)※ 단 모든 가중치가 1일 때 가능최소 비용 문제이어야 한다.간선의 가중치가

알고리즘 다이나믹 프로그래밍 일명 DP를 풀때는 점화식이 있는 유형인 경우 점화식이 있다면 우선적으로 점화식을 세운다 배열이 무엇을 의미하는지 정의한다. 초기화 한다. 의 세 단계로 왠만큼 문제가 풀린다. 키워드 문제가 점점 작아진다. 점화식이 있다. 문제

소수 문제는 기본적으로 그냥 범위내에서 소수의 갯수를 구하는 문제와 어떤 소수가 있는지를 구하는 문제로 나뉜다.보통은 위와 같은 방식으로 푸는데 이것도 속도 제한에 심하게 걸리는 편이다.그래서 나온것이 에라토스테네스의 체이다.그래서 에라토스테네스의 체가 뭐냐하면 2부터

그래프2 - DAG와 위상 정렬자료구조2 - 유니온 파인드, 힙, BST간선 리스트인접 행렬이렇게 2차원 그래프로 표현하는 방식 하지만 이 방식은 많이 사용하지 않음인접 리스트보다 많이 사용하는 방식정점의 갯수가 V개, 간선의 개수가 E개인 그래프에 대해서 V개의 연결

1. 그래프 > 그래프 문제 알고리즘은 동일하다. > 단지 데이터

간선 리스트인접 행렬이렇게 2차원 그래프로 표현하는 방식 하지만 이 방식은 많이 사용하지 않음인접 리스트보다 많이 사용하는 방식정점의 갯수가 V개, 간선의 개수가 E개인 그래프에 대해서 V개의 연결 리스트로 그래프 정보를 저장상호 배타적 집합2가지 연산으로 이루어져 있

정렬은 O(NlgN)이 걸리는 정렬을 사용해야 한다.정렬을 직접 구현하는 것 보다는 언어에 구현되어 있는 것을 사용하는 것이 좋다.C++은 algorithm 헤더 파일에 있는 std::sort를 사용한다.• Java는 Arrays.sort나 Collections.sor

동전2

링크

비트연산을 사용해서 부분 집합을 표현하는 방법비트연산의 종류비트연산 방법두 수 A와 B를 비트 연산 하는 경우에는 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.비트연산의 시간복잡도O(1) 내부에서 알아서 상수시간 안에 처리not 연산의 경우에는 자료형에 따라 결과가

보드의 상태가 주어졌을 떄, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 문제 이때 파란구슬도 있기 때문에 파란구슬은 빠지면 안된다.NxM 1x1 크기의 칸이 있어서 빈칸, 벽, 구멍, 빨간

DFS와 목적이 동일, 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는것특징은 DFS와 다르게 최단 거리를 구하는 알고리즘이다. 단 BFS는 모든 가중치가 1이어야만 하고 가중치가 1이 아니면 다익스트라 알고리즘을 이용하게 된다.

수 정렬하기 빡샌기준메모리 관련해서는 사전에 미리 공간을 만들어 놓으면 메모리 문제가 생길 가능성이 낮아진다.그리고 조건을 보면 수의 범위가 10000으로 적은편이기 떄문에 배열 삽입이라는 방법으로 빠르게 처리하는게 맞는거 같다. 내가 참고한 소스는 아래와같다.http