본문 바로가기

Algorithm

 (84)
BOJ7568 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net
BOJ2231 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net
[BruteForce] BOJ2798 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net
[BFS,DFS] 백준 1260번 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 간단하게 , DFS와, BFS의 동작 방식에 대해서 개념을 잡는 가장 기초적인 예제이다. 우선 최단 경로찾기에 대한 솔루션으로 알고있는 DFS는, 재귀형태로 구현하는 것이다. 즉, 가장 깊이 노드를 탐색하는 것이다. 어떤 노드를 탐색하고, 특정 노드에 대한 다음 탐색노드를 인자로 넣어서 바로 다음 탐색 노드로 함수를 호출하는 형태이다. 또, BFS는 탐색 가능..
[Two pointer] 15565번 풀이 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 귀여운 라이언 풀이 생각 보다 투포인터라는 개념만 있으면 쉽게 풀수있다. 우선 투포인터와 완전 유사하다. while 조건은 총 두개, left
[Two pointer] 16472번 고냥이 투포인터 고냥이 문제 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 투포인터와 Map으로 해당 문제를 풀수있다. 처음에 버벅였던게 크다.... 이문제는 진짜 혼자 오래동안 풀었다...열심히좀 해야겠다...(자기반성) 우선 소스에서 크게 볼부분이 있다. 투포인터는 탐색의 경우, 아주 유용하다 (부분합 구할때랑 동일) 투포인터는 문제를 풀때 항상 유념해야되는 부분이있다. 즉, index를 1크게 생각을 해야한다. 예를 들어보자 처음에 00으로 시작했다. ..
[Two pointer] 백준 16472 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net
[Two pointer] 백준 1806 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이것도 간단한 부분합이다. 포인트라고 하면 두가지 정도가 있다. left,right로, 단순 카운트가아니라, 정답에 부합할때 (주어진 합보다 이상인 경우) 일때, math.min으로 구하는것 그리고 답이 없는 경우, 그냥 0을 출력하게끔 하는것 이렇게 생각하고 풀면 된다. 다만 투포인터를 사용할때는 연속한, 어ㅉㅓ고 쩌쩌고 만 나올ㄸㅐ라는것을 꼭 명심하자

티스토리툴바