프로그래밍38 [자료구조] 백준 1655: 가운데를 말해요 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 발상의 전환이 필요했다. 솔직히 한 번에 풀지 못했고(테스트케이스는 맞았으나, 시간초과가 남) 다른 사람의 풀이를 구글링하고 난 다음에야 문제를 풀 수 있었다. 처음에는, 매 입력마다 list를 정렬하고, 그 가운데 값을 출력하는 간단한 문제로 생각했다. 그러나 이 경우는 매번 전체 리스트를 순회하며 정렬하기 때문에 비효율적이었다. 그래서 구글링을 통해 알게 된 발상이, input을 받는 자료.. 2024. 3. 3. [구현] 백준 23304: 아카라카 팰린드롬 23304번: 아카라카 (acmicpc.net) 23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇지 않다면, IPSELENTI를 출력한다. www.acmicpc.net 어떤 문자열이 앞으로 읽어도, 뒤로 읽어도 똑같으면 그것을 팰린드롬이라고 한다. 여기에, 해당하는 문자열의 중심을 기점으로 접두사와 접미사 역시 팰린드롬인 것을 '아카라카 팰린드롬'이라고 정의하고, 주어진 문자열이 아카라카 팰린드롬임을 확인해야 한다. 먼저 해당 문자열이 앞으로 읽어도, 뒤로 읽어도 같은지 판단한다. for (int i = 0; i < str.size(); i++) { if (str[i] != str[str.size() - 1 - i]) { return false;.. 2024. 1. 18. [구현] 백준 1347: 미로 만들기 1347번: 미로 만들기 (acmicpc.net) 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 이 문제에서 찝찝한 점은 처음 시작할 때 미로가 몇 칸짜리인지 미리 알 수 없다는 점이다. 따라서 최악의 경우를 고려해서 미로의 최대 크기를 미리 구해 놓고, 그 중간에서부터 주어진 input에 따라 미로를 그려 나가는 작업을 하였다. 이 경우는 통상적인 정의의 "미로"라고는 할 수 없겠지만, input이 모두 'F'인 경우가 미로 크기가 가장 길어지는 경우일 것이다. input 길이는 50보다 작으므로, 나는.. 2024. 1. 16. [BruteForce] 백준 16197: 두 동전 16197번: 두 동전 (acmicpc.net) 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 재귀함수를 이용한 brute force 문제. 동전은 무조건 2개이고, 가능한 입력 방향은 4개이다. 다음과 같은 구조를 생각하면서 재귀함수를 작성하였다. 사실 대단히 어려운 문제가 아니지만 42% 정도에서 계속 오류가 나서 고생을 했는데, 알고 보니 내가 base case 조건을 [버튼을 10번 보다 많이 누를 것]이 아닌 [버튼을 10번 이상 누를 것]으로 오독해서 생긴 문제였다. 재귀함수를 짤 때는 항상 ba.. 2024. 1. 9. 이전 1 2 3 4 5 6 7 ··· 10 다음
