Algorithms (24) 썸네일형 리스트형 Binary Search 응용하기 https://en.wikipedia.org/wiki/Binary_search_algorithm Binary search algorithm - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Search algorithm finding the position of a target value within a sorted array This article is about searching a finite sorted array. For searching continuous function values, see bisec en.wikipedia.org binary search를 책으로 배우고 실제로 응용할때 bi.. 백준 알고리즘 9938번 문제 : 방 청소 https://www.acmicpc.net/problem/9938 9938번: 방 청소 문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대 www.acmicpc.net Disjoint Set을 이용한 문제입니다. 문제는 백준 알고리즘 사이트에서 확인하세요. 이번 문제는 이해하기가 너무 힘든 문제였습니다;;.. 고급 자료구조 - Disjoint Set Disjoint? 뭘까요? 사전을 찾아보니까 "분리된" 이라는 형용사 입니다. 아하 그럼 disjoint set은 분리된 집합이라는 뜻이겠네요. 집합간의 intersection이 없는것이 disjoint set입니다! disjoint set은 Kruskal MST algorithm과 같이 그래프 상에서 각각의 정점이 연결되었는지를 검사할때 요긴하게 사용됩니다. Minimum Spanning Tree는 Tree인 만큼 Cycle이 형성되면 안되는데요. 이 Cycle 찾기위해 인접한 정점을 일일이 찾는다면 상당히 복잡해집니다. 이럴때 사용하는 것이 Disjoint Set! disjoint set을 활용하면 그래프 상에서 각각의 정점이 서로 붙어있는지(Cycle을 형성하는지) 알 수 있습니다. 먼저 자료구조니.. 백준 알고리즘 2302번 문제 : 극장 좌석 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 n >> m; if (n 40 || mn) { return 0; } seats = vector(n + 1, vector(3, 0)); for (int i = 1, temp; i > temp; i.. 백준 알고리즘 2580번 문제 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 문제는 백준 알고리즘 사이트에서 확인하세요 오늘 포스팅할 문제는 스도쿠 문제입니다 초등학생때 한번씩 풀어보셨죠?? 규칙은 간단합니다 좌우에.. C++ STL::Queue Queue는 상당히 유용한 자료구조 입니다 ㅋㅋ BFS, TSP, BACKTRACKING 등 참 많이 쓰여요. 저장한 순서대로 데이터를 사용해야한다면 가장 사용하기 적합한 자료구조입니다. 제가 써본 STL들의 특징이 있는데요. 인자값으로 const 값을 받는다는 것입니다. Java를 사용해보신분들은 겪어보신적이 있으시겠지만 가끔 의도치않게 레퍼런스 변수가 인자로 넘어가서 프로그램이 꼬이는 경우가 있습니다. 제가 써본 STL들은 값을 복사해가기 때문에 계속 같은 변수를 이용해 push함수를 호출해도 별 무리가 없었네요! 소스코드 신나게 짜놨더니 속에서 꼬여서 전부다 바꿔야한다면.. ㅂㄷㅂㄷ.. 이렇게 구조체를 선언하고 구조체를 원소로 갖는 queue를 만들수도 있습니다 ★ 자주 사용하는 메서드 ★ push.. 백준 알고리즘 1238 - 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 문제는 백준 알고리즘 사이트에서 확인하세요~ 문제 분석 N개의 마을중에 X번째 마을에서 파티를 열면 모든 마을에 사람들이 X번째 마을로 왔다.. 백준 알고리즘 9869 - Milk Scheduling https://www.acmicpc.net/problem/9869 9869번: Milk Scheduling Farmer John has N cows that need to be milked (1 판단의 기준 즉 Deadline을 지키면서 판단기준에 맞도록 스케쥴하는것이 최적화된 해답과 가깝습니다~ Deadline은 어떻게 지킬 수 있을까요? 번호 DeadLine 1 3 2 2 3 2 4 2 예를 들어보았습니다 4개의 작업이 있고, 저마다 deadline이 존재합니다. 어떻게 deadline을 지킬 수 있는지 알아봅시다! 1 2 3 4 5 6 넉넉하게 스케쥴을 작성할 공간을 만들어 줍니다~ 번호순으로 스케쥴링을 하면 진행 번호 1 2 3 4 5 6 1 task1 2 task2 task1 앞이 비었음에도 불.. 이전 1 2 3 다음
