본문 바로가기

전체 글

 (97)
[백준(BOJ)/C++] 3049번: 다각형의 대각선 - 코딩밥상 https://www.acmicpc.net/problem/3049 3049번: 다각형의 대각선 세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든 www.acmicpc.net 접근 방법 도형의 구성 요소의 개수를 세는 문제는 보통 서로간의 연관성에서 얻을 수 있다. 이는 보통 중학교 수학에서 배웠던 내용들이라 큰 어려움은 없을것이다. 다음 문제에서는 n각형 즉 꼭지점의 개수를 알려주었기 때문에 꼭지점과 문제에서 요구하는 답을 연관지어 생각하면 될것이다. 논리 흐름(알고리즘) 문제에서 요구하는 답은 꼭지점을 이어 만든 대각선들이 만나 생기는 교차점의 개수이다. 이를 연관지..
[백준(BOJ)/C++] 2217번: 로프 - 코딩밥상 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 접근 방법 모든 줄에 중량이 w/k만큼 걸린다는 말은 최소로 들 수 있는 줄의 중량값이 모든 줄에 걸린다는 뜻이다. 즉 (가장 약한 줄에 걸린 중량)*(관여한 줄의 수)가 들아올릴 수 있는 물체의 중량이다. 처음에는 줄의 최솟값을 구하고 n값을 곱한것이 답이라 생각하고 너무 쉽다 룰루랄라 했지만, 문제를 잘 읽어보면 "임의로 몇개의 로프를 골라서 사용해도 된다" 라고 나와있다. 이 문장이..
[백준(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해준 후 지정 번호를 다음 번호로 넘긴 후 과정을 반복 한다. 만약 지정 번호보다 ..

티스토리툴바