목록알고리즘 (70)

택시짱의 개발 노트

[백준] 16988번 Baaaaaaaaaduk2 (Easy)

링크 https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 www.acmicpc.net 풀이 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 개수를 구하는 문제이다...
알고리즘 2020. 3. 25. 15:07
[백준] 5670번 휴대폰 자판

링크 https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 문제 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드 www.acmicpc.net 풀이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제이다. 입력받은 각 단어들을 트라이를 이용하여 트리를..
알고리즘 2020. 3. 24. 16:15
[백준] 14225번 부분수열의 합 (비트마스크)

링크 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 풀이 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제이다. 일단 비트 마스크를 이용하여 수열 S의 모든 부분 수열의 합을 구하고 map에 추가하고 모든 부분 수열을 구하고 나서 1부터 최대로 나올 수 있는 20..
알고리즘 2020. 3. 24. 14:28
[백준] 14425번 문자열 집합 (트라이)

링크 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. www.acmicpc.net 풀이 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제이다. 간단하게 집합 S를 map에 추가 하고나서 M개의 문자열을 map과 매핑하여 포함 여부를 확인하면 된다. 1. map..
알고리즘 2020. 3. 24. 14:22
[프로그래머스] 단어 변환

링크 https://programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 구하는 문제이다. BFS탐색을 이용하여 최소 값을 구하도록 하였고 이전 문자와 다음 문자를 서로 비교하여 다른 부분이 한 개만 있을 때 BFS의 queue에 추가되도록 하여 target 문자열을 만나게 되면 바로 return을 하도록 하..
알고리즘 2020. 3. 20. 16:05
[백준] 17822번 원판 돌리기

링크 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 풀이 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하는 문제이다. 이 문제는 원판을 돌리고 비교하고 인접한 숫자가 같으..
알고리즘 2020. 3. 20. 15:27
[프로그래머스] 줄 서는 방법

링크 https://programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 구하는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #define SIZE 22 const int INF = 2000000000; using nam..
알고리즘 2020. 3. 19. 18:10
[프로그래머스] 최고의 집합

링크 https://programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 구해야 되는 문제 이다. 예를 들어 원소의 개수가 2개 이고 원소들의 합이 6이라고 할 때 원소를 나누어 보았을 때 1,5 2,4 3,3 이렇게 3개로 나눌 수 있고 각각 원소의 곱은 5, 8 ,9이다. 이때 원소의 합을 원소의 개수로 나누었을 때 나오는 값에 가까운 수가 많을수록 원소들의 곱이 가장 크다는 것을 ..
알고리즘 2020. 3. 19. 15:10
Prev 1 2 3 4 5 6 7 8 9 Next