Algorithm

1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 난이도 : 실버2 풀이 과정 : 일단 시간제한이 0.2초이고 문자열이 십만, 명령어의 개수가 50만이므로 최악의 경우 최대 연산 개수가 십만*50만 = 500억이 된다. 그러면 O(n)으로 짜면 무조건 시간 초과가 나고 선형 시간에 알고리즘을 짜야된다. 선형 시간에 이 문제를 푸는 방법은 바로 연결리스트 자료 구조를 이용하면된다. 배열/벡터와 달리 연결리스트는 특정 인덱스의 원소를 삭제, 추가 하는데 시간복잡도가 O(1..

https://www.youtube.com/playlist?list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY 바킹독의 실전 알고리즘 강의 코딩테스트 대비를 위한 바킹독의 실전 알고리즘 강의입니다. 블로그 URL : https://blog.encrypted.gg/category/강좌/실전%20알고리즘 www.youtube.com 1. 배열 1) 성질 O(1)에 k번째 원소 확인, 변경 가능 추가적으로 소모되는 메모리의 양이 거의 없음 데이터들이 붙어있으므로 캐시지역성(cache hit rate)이 좋음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 임의의 위치에 원소에 삽입/삭제하기 위해서는 O(N) 시간이 걸림 insert, erase 함수 구현하기 #include us..

(5) 바킹독의 실전 알고리즘 강의 - YouTube 바킹독의 실전 알고리즘 강의 코딩테스트 대비를 위한 바킹독의 실전 알고리즘 강의입니다. 블로그 URL : https://blog.encrypted.gg/category/강좌/실전%20알고리즘 www.youtube.com 위 강의를 보고 학습한 내용을 바탕으로 작성하였습니다. 1. 시간복잡도, 공간복잡도 1) 시간 복잡도 - 컴퓨터는 1초에 대략 3~5억개 정도 연산 처리 가능 - 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 - 빅오 표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!) O(1) O(logN) O(N) O(N..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24 67개 문제 풀이로 익히는 C++ 자료 구조와 알고리즘!코딩 테스트 준비 및 최신 C++ 문법으로 알고리즘을 학습하자!C++ 자료 구조부터 그리디 알고리즘, 분할 정복 알고리즘, 그래프 알고리즘, 동적 www.yes24.com 🔔 1장 리스트, 스택, 큐 1.1 들어가며 응용 프로그램 설계시 중요 고려 항목 중 하나는 데이터 관리. 데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용할 수 있음 응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 "자료 구조" 선택해야 함 1.2 연속된 자료 구조와 연결된 자료 구조 데이터를 처리하..

2792번: 보석 상자 (acmicpc.net) 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 난이도 : 실버2 해결 과정 : 이분 탐색으로 푸는 문제 였습니다. 나눠줄 때 한 색깔종류로만 나눠줘야 하기 때문에 각 색상의 개수 / 질투심 값과 나눴을 때 나머지가 나온다면 +1 해서 각각 더해진 cnt 값이 학생의 수와 같으면 right 값을 줄여주는 식으로 구현 하였습니다. 맨 첨에 left값을 0으로했다가 100퍼에서 틀렸다고 나오길래 1로 고쳐줬습니다. 코드 : #include #include #inclu..

14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 와.. 그냥 빡구현으로 풀었슴... ㅋ ㅋ ㅋ 푼다음에 다른 사람꺼 풀이 보니까 dy dx 배열 선언해서 4방향으로 돌수 있게 반복문으로 처리한거같았는데 나는 그 방향 바뀔 때 dy dx가 규칙성 있게 바뀔 거라는 건 예상이 가지만 수식이 도저히 생각이 안나서.... 그냥 동서남북 조건 나눠서 일일히 x랑 y값 선언해주면서 했음.. 위에 chk함수는 청소하고자 하는 (r,c)가..

15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 각 집마다의 치킨거리를 구해 마을의 총 치킨거리가 최소가 되도록하는 문제입니다. n이 50이므로 최대 집 개수+치킨집개수은 250이 됩니다. 따라서 집개수와 치킨집 개수가 반반이라고 했을 때 최대 125*125 = 15625 번 연산을 하므로 제한시간이 1초라서 완탐으로 풀 수 있는 문제 였습니다. 완전탐색문제가 되면 복잡할거없이 치킨집을 조합으로 m개 고른다..

2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 풀이 과정 : 위상정렬 문제로 사이클 여부 판별 + 중복간선 제거 를 해결해야되는 문제였습니다. 저는 맨처음엔 벡터로 하려다가 set자료형을 이용하여(중복을 허용하지 않음) set배열로 입력을 받았습니다. 만약에 중복된 간선이 나오면 삽입을 해도 set배열의 크기가 같으므로 만약 삽입을 했는데도 전에랑 크기가 같으면 진입차수를 저장하는 배열은 업데이트를 하지 않게 해주었습니다..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 최근에 코테를 몇번 참가해보면서 구현을 정확하고 빠르게 푸는 것의 중요성을 깨달았다. 이 문제는 구현+bfs인데, 백준에서 bfs문제중 바이러스 문제가 있어서 그거 먼저 풀면 도움이 될듯하다. n과 m이 최대 8까지기 때문에 완탐! 으로 가능하다 왜냐면 0이나올수 있는 곳에 벽 3개를 두는 것이기 때문에 최대 64C3 번 연산 이기 때문 관건은 벽 3개를 두는 방법을 어떻게 ..