[백준] 1158 요세푸스 문제
2023. 1. 10. 20:29
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 n번까지 n명의 사람이 원을 이루며 앉아있을 때, 순서대로 k번째 사람을 제거 원에서 사람들이 제거 되는 순서를 요세푸스 순열이라고 하는데, 이 순열을 구하기 문제 풀이법 queue를 쓰면 금방 풀린다 우선 1번부터 n번까지의 사람을 queue에 넣어놓고, queue가 empty가 되지 않을때까지 while문을 반복한다 while문에서는 k번째의 사람을 구하기 위해서, k -1 번째의 사람은 pop한 뒤, 다시 뒤에 push 한다 k번째 사람은 pop을 한 후, 출력하..
[백준] 5397 키로거
2023. 1. 10. 20:21
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 비밀번호 창에서 입력한 키가 주어졌을 때, 비밀번호 구하기 이때 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표만 입력 화살표는 로 입력되며, 커서를 옮기는 역할 백스페이스는 -로 입력되며 커서의 바로 앞에 글자가 존재한다면 그 글자를 지우는 역할 문제 풀이법 백준 1406 에디터와 굉장히 유사한 문제이다 다양한 위치에서의 삽입/삭제를 위해 list를 사용한다 커서의 위치는 ..
[백준] 1406 에디터
2023. 1. 10. 19:52
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 초기에 편집기에 있는 문자열이 주어지고, 명령어가 주어지면 해당 명령어에 맞게 수행 한 후의 문자열을 구하기 문제 풀이법 처음에는 vector로 풀었다 예제에 있는 답은 맞았지만 5% 즈음부터 시간초과로 실패하고 말았다 vector가 아닌 list로 풀어야 시간초과가 안난다고 한다 그 이유는 vector는 연속적인 배열이기에 중간에 요소가 하나 제거된다면, 당겨야 하는 상황이 발생한다고 ..
[백준] 1919 애너그램 만들기
2023. 1. 9. 20:14
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다 두 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하기 문제 풀이법 처음에 문제를 잘못읽고 다른 방향으로 문제를 풀려 했었다 "철자의 순서를 뒤바꾸어 같아질 수 있다" 라는 말을..
[백준] 11328 Strfry
2023. 1. 9. 20:01
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/11328 11328번: Strfry C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래 www.acmicpc.net strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어 내는 함수이다 두 개의 문자열이 주어졌을 때, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있으면 Possible 출력 얻을 수 없으면 Impossible 출력하기 문제 풀이법 strfry 함수를 적용하여 얻을 수 있다는 말은, 다시 말하면 문자열1과 문자열2가 ..
[백준] 13300 방 배정
2023. 1. 9. 19:47
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net n명의 학생들이 수학여행을 가는데 한 방에 최대 k명의 학생을 배정할 수 있다 방은 같은 성별, 학년별로만 이루어져야 할 때 필요한 방의 수를 구하기 문제 풀이법 우선 2차원 배열에 총 몇 명의 학생이 수학여행을 가는지 구한다 이중 for문을 돌면서 해당 학년, 성별의 학생들의 방이 몇개인지 더한다 0명 일 때 아무것도 하지 않는다 학생 수 최대 방 인원 학생..
[백준] 10807 개수 세기
2023. 1. 9. 17:44
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net n개의 정수가 주어졌을 때, 찾으려는 정수 v가 몇 개인지 구하기 주어진 정수의 범위는 -100보다 크거나 같고, 100보다 작거나 같음 문제 풀이법 처음에는 문제를 제대로 못보고 배열의 범위를 100으로 해서 틀렸다 하지만 주어진 정수의 범위가 -100 ~ 100이기에 배열의 범위를 201로 잡고, 인덱스에는 음수가 들어갈 수 없으니 정수에 100씩 더해줘서 인덱싱을 해주..
[백준] 3273 두 수의 합
2023. 1. 6. 20:28
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net n개의 서로 다른 양의 정수가 주어지고, 자연수 x가 주어졌을 때 a[i] + a[j] = x인 쌍의 수를 구하기 문제 풀이법 단순히 for(int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == x) cnt++: } } 했다가는 시간초과 난..
[백준] 2566 최댓값
2023. 1. 6. 19:58
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/2566 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 첫째 줄부터 아홉 번째 줄 까지의 한 줄의 아홉 개의 수 중에서, 최대값과 최댓값이 위치한 행과 열을 구하기 문제 풀이법 81개의 수를 입력받으면서 그때 그때 가장 큰 수와, 그 수의 행과 열을 저장후, 출력해주었다 하지만 제출했을 때 100%에서 틀린 닶이 나왔다 이것 저것 반례를 살펴보니 행과 열의 수를 초기화 하지 않아서 생기는 문제였다 만일 모든 수가 0이라면 x와 y는 max를 값을 찾아서 값이 ..
[백준] 1475 방 번호
2023. 1. 6. 19:45
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 방 번호를 붙일 수 있는 0 ~ 9까지의 플라스틱 숫자가 한 세트가 있는데, 다솜이의 방 번호가 주어졌을 떄 필요한 세트의 개수의 최소값을 구하기 이때 9와 6은 바꿔서 사용가능 문제 풀이법 방 번호를 10으로 나누면서 각 번호가 총 몇 번 사용되었는지 숫자를 셈 만일 6이 3개, 9가 1개이면 총 2세트만으로도 가능 만일 6이 4개, 9가 1개이면 총 3세트만으로도 가능 즉, (6의 수 + 9의 수 + 1) / 2 하면 총 몇 세트가 필요한지 알 수 있음 arr[6] = (6의 수 ..