백준 문제풀이 (31) 썸네일형 리스트형 [백준(BOJ)/C++] 6604번: 로또 - 코딩밥상 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 접근 방법 문제에서 요구하는것은 k개의 집합 중 로또 번호 6개를 고르는 경우를 모두 나열해서 오름차순으로 출력하는 것이다. 요구하는 바를 보면 k개 중 6개를 선택하는 조합이라는것은 쉽게 알 수 있었다. c++에서 조합을 구현해본 적은 없기에 헤매고있다가 저번주 스터디 수업에서 배웠던 조합과 순열을 구현할 수 있는stl을 배웠기에 이를 참조하여 문제를 풀었다. 논리 흐름(알고리즘) 핵.. [백준(BOJ)/C++] 5430번: AC - 코딩밥상 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 접근 방법 뒤집는 경우와 안뒤집는 경우가 나뉘기때문에 앞뒤로 컨트롤이 유용한 deque을 사용해야겠다고 생각했고, 까다롭다고 생각한건 string으로 입력을 받고 int형으로 덱에 집어넣어야 한다는 점이었다. 이는 형변환을 사용하겠다고 생각하고 문제풀이를 이어나갔지만, 몇군데 버벅이는 부분이 있었다. 논리 흐름(알고리즘) 첫번째 난관은 string으로 입력값을 받고 int형으로 deque에 저장하는 부분이었다. 다음과 같이 입력값에서 두자리 이상의 숫자.. 백준 19638번 - 센티와 마법의 뿅망치 https://www.acmicpc.net/problem/19638 19638번: 센티와 마법의 뿅망치 마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수 www.acmicpc.net 접근 방법 처음 문제를 보고 가장 키가 큰 거인에게 지팡이를 사용하고 줄어든 키를 다시 저장하기를 반복하며 centi의 키와 비교하자고 생각했고, 가장 큰 수를 앞에 저장하는 자료구조를 생각했는데 바로 최대 힙이었다. 특별한 순서 없이 가장 큰 수를 다루기에 가장 적합하다고 생각했다. 논리 흐름(알고리즘) 최대힙에 거인들의 키를 모두 저장 후 가장 키가 큰(최대 힙의 top) 거인에게.. 백준 25192번 - 인사성 밝은 곰곰이 https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 접근 방법 문제를 처음 보고 닉네임을 저장할 공간을 만들고 ENTER가 주어지면 초기화, 닉네임이 주어지면 탐색하여 이미 있는 닉네임일경우 다음루프, 없는 닉네임일경우 카운트 후 닉네임 저장을 하면 되겠다고 생각했다. 논리 흐름(알고리즘) 앞서 말했던 접근 방법대로 string배열을 만들어 여기에 닉네임을 저장하여 탐색해보았다. 하지만 이렇게 할 경우 시간복잡도가 n^2이 나.. 백준 17952번 - 과제는 끝나지 않아! https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 접근 방법 문제를 보자마자 각 과제의 점수와 걸리는 시간을 pair로 짝지어서 스택에 저장하자는 아이디어가 떠올랐다. 문제에서 주어진 1.번 조건을 보면 LIFO 스택을 사용하라고 알려주고있다. 논리 흐름(알고리즘) 새로운 과제가 주어질 경우(1) 과제의 점수와 걸리는 시간을 짝지어 스택에 저장해준다. 이 때 시작과 동시에 과제가 진행되기 때문에 걸리는 시간값에 -1을 해준다. 과제가 주어.. 백준 12789번 - 도키도키 간식드리미 https://www.acmicpc.net/problem/12789 접근 방식 문제에서 현재 줄 서있는 곳에서 처음부터 하나씩 비교해서 찾는 수가 아닐경우 밑의 공간으로 집어넣고, 마지막에 밑의 줄을 한번에 비교해서 문제를 풀기로 마음 먹었다. 여기서 현재 줄은 FIFO 이니까 queue로, 밑의 줄 공간은 LIFO 이니까 스택으로 잡자고 생각했다. 논리 흐름(알고리즘) 현재 줄을 queue로 생성하여 입력값을 받은 후, 간식받을 선을 지날 번호를 지정해 준다. 즉 지정 번호가 나타날 경우에만 다음 단계로 넘어간다. 우선 현재의 줄에서 간식 받을 번호(지정 번호)와 첫 순서 번호를 비교해 가며 찾는 수일 경우 그대로 pop해준 후 지정 번호를 다음 번호로 넘긴 후 과정을 반복 한다. 만약 지정 번호보다 .. 백준 1158번 - 요세푸스 접근 방식 문제를 보고 패턴(k값)이 있는 원형수열(?)임을 생각하고 전에 풀어봤던 풍선터뜨리기 문제가 떠올라서 그 문제 풀이와 같이 front와 back을 바꿔 원으로 돌아가는 패턴을 구현할 수 있는 덱(deque)을 통해 접근해 보았다. 논리 흐름(알고리즘) 주어진 사람 수 만큼의 숫자를 넣고, 주어진 key-1번(숫자가 pop되면서 1번 실행) front값을 back값으로 보내주면 front값에 순서대로 구할 값이 남게 된다. 러시안룰렛처럼 key번 돌리고 총알을 쏜다고 생각하면 된다. 총알이 다 떨어질 때까지 이 과정을 반복하면 답이 나온다. 마지막 출력 조건에서 삐끗했는데, 반복문에 단순히 ", "출력을 더해주면 마지막에 로 출력되기 때문에 따로 조건문을 걸어주었다. 백준 1406번 - 에디터 접근방식 커서의 왼쪽과 오른쪽을 구분하여 문자 하나하나 순서대로 최신화하기에 스택이 적합하다고 생각하여 문제를 풀어나갔다. 이 과정에서 처음엔 스택을 하나로 설정하였는데, 왼쪽과 오른쪽을 나누는 과정에서 스택을 2개로 나누어 따로따로 해결해 나가는것이 합리적이라는것을 깨달았다. 논리 흐름(알고리즘) 커서를 기준으로 왼쪽 문자들을 left스택에, 오른쪽 문자들을 right스택에 저장하고, 커맨드 키가 L일 경우 오른쪽 스택에서 왼쪽 스택으로 문자를 옮겨주고 R일 경우 왼쪽 스택에서 오른쪽 스택으로 문자들을 최신화 시킨다. B와 P일 경우에는 커서의 왼쪽 문자를 바꾸어주기 때문에 left스택에서 최신화 시켜주었다. 구현 과정에서 char형이기 때문에 가독성을 위해 switch문으로 구현할 수 있었다. 마지막.. 이전 1 2 3 4 다음
