https://www.acmicpc.net/problem/1100
1100번: 하얀 칸
체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하시오.
www.acmicpc.net
- chess 맵을 만들어주고 (흰색 ,검은색) i+j가 홀수 이냐? 짝수 이냐? 로 나누시면 됩니다.
- 그 후 입력을 받으면서 그때그때 counting을 증가시켜주시고
- 출력해주시면 됩니다.
<코드>
| 백준 1254 [C++] (0) | 2021.01.15 |
|---|---|
| 백준 6064 [C++] (0) | 2020.11.30 |
| 백준 10815 [C++] (0) | 2020.10.25 |
| 최대공약수 구하기 (재귀,유클리드호제법) (0) | 2020.10.08 |
| 백준 1316 (0) | 2020.02.28 |
https://www.acmicpc.net/problem/10814
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
www.acmicpc.net
- 문제에서 요구하는 정렬 조건만 잘 맞춰주면 되는 간단한 문제 !.
- 저는 vector 배열에 age와name을 저장하는 구조체에 whenin 이라는 언제 가입했는지(가입순서)
- 를 초기화 하는 과정에서 i를 넣어놓았고 정렬을 하는 과정에서 나이가 같으면 whenin을 비교하여 정렬하도록 하였습니다.
<코드>
| 백준 1620 [C++] (0) | 2021.01.09 |
|---|---|
| 백준 2887 [C++] (0) | 2020.10.27 |
| 백준 10825 [C++] (0) | 2020.10.25 |
| 백준 1181 (0) | 2020.01.15 |
| 백준 1427 (0) | 2020.01.08 |
https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
www.acmicpc.net
1. 첫 번째는 입력은 순위 입니다(점수가 아님) --조심 !
2. 전 첫번째 제출한 코드는 시간초과가 되었습니다. 당연한 것이 최악의경우를 생각해보면
입력을 고려해 보았을 떄 10000000000 이는 약 1억번 연산이 1초라고 계산해보면
당연히 시간초과가 나올 수 밖에 없겠죠.
3. 그래서 우선 서류점수로 오름차순 정렬을 한후
반복문을 돌리는데 이때는 전체를 다 탐색할 필요가 없이 본인보다 서류점수 우선순위가 높은 사람들
(즉 본인보다 낮은 index)
의 면접점수만 확인 하면 되기 때문에 입력이 커질경우 연산 횟수를 대폭 줄일 수 있습니다.
** 그리고 저 같은 경우 vector를 사용하였는데 시간적 측면에서 더 단축 하고 싶다면
그냥 max값을 define 하여 그만큼의 배열을 잡아 버리는 것이 시간적 측면에서는 더 이득인 것 같더라구요 !
<시간초과 코드>
<맞춘 코드>
https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
www.acmicpc.net
- 완전탐색 문제입니다..
- 저는 bfs를 이용한 완전탐색을 구현하여 모든 경우의 수를 모두 구했습니다.
- 구조체 를 선언하여 그 안에 연산자의 수를 count하는 변수들을 각자 모두 들고 있고
- 하나씩 사용하여 계산후 사용한 연산자의 수는 하나 줄여주고 다시 큐에 넣습니다.
- 이와 같은 방식으로 bfs를 구현하여 모든 경우의 수를 계산한 후 vector 에 넣어
- 내림차순 정렬을 통하여 0번째 항과 마지막 항을 출력하였습니다.
- 나름 상세하게 주석을 달아놓았습니다.... 도움이 되는 분들이 있었으면 좋겠네요..
- 채점현황을 보니 저는 코드가 상당히 긴 편이였습니다.. 한번 다른분들은 어떤방식으로 푸셨는지 저도 한번 알아봐야겠네요 !
<코드>
| 백준 1748 : 수 이어 쓰기 1 (0) | 2020.03.24 |
|---|---|
| 완전탐색(경우의 수) , 순열, 재귀를 통한 구현, 모든 카드 경우의 수 (0) | 2020.02.28 |
| 백준 14889 (0) | 2020.02.24 |
| 백준 7568 (0) | 2020.02.21 |
| 백준 6603 (0) | 2020.02.01 |
https://www.acmicpc.net/problem/7568
7568번: 덩치
우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰
www.acmicpc.net
- 아....너무쉬운 완탐 문제 였습니다...
- 처음에 문제를 파악할 때 입력 조건이 생각보다 크지 않다는 것을 체크 했어야했는데
- 처음에 무게순으로 정렬후 비교 작업하고 또 순서대로 출력해야 해서 구조체에 순서 저장 변수 따로 저장하고...
- 고생하다가 생각해보니 입력 조건이 크지 않다면 그냥 하나씩 전부와 비교하면 된다는 것....
- 그외에 특별할 것 없는 완탐 문제였습니다....... 입력 조건 파악을 잘하자....!
<코드>
| 백준 1748 : 수 이어 쓰기 1 (0) | 2020.03.24 |
|---|---|
| 완전탐색(경우의 수) , 순열, 재귀를 통한 구현, 모든 카드 경우의 수 (0) | 2020.02.28 |
| 백준 14889 (0) | 2020.02.24 |
| 백준 14888 (0) | 2020.02.21 |
| 백준 6603 (0) | 2020.02.01 |
https://www.acmicpc.net/problem/2217
2217번: 로프
N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을
www.acmicpc.net
-문제를 읽어보고 예시를 한번 그려보았더니 로프가 버틸 수 있는 중량의
-입력 값이 어떻게 주어지냐에 따라서 들 수 있는 최대 무게가 많이 달라질 수 있는 문제였습니다.
-몇개의 로프를 선택 하던 간에 그 로프들로 들 수 있는 중량의 최대 무게는
- (로프 중 가장적은 무게를 들수 있는 중량) * (로프의 개수) 입니다.
-로프 n개 선택 한다고 치면 큰 무게를 들 수 있는 로프를 두고 적은 무게를 들 수 있는 로프를 선택할 이유 가 없으므로
-큰것들 부터 n개를 선택 해 가면서 반복문을 1회 돌면서 그 값들을 비교하면 되는 문제 였습니다.
- 내림차순으로 정렬 후 앞에서 부터 로프의 개수를 하나씩 늘려가며 최대값만 저장 후 출력하였습니다.
<필기>
<코드>
https://www.acmicpc.net/problem/1931
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
회의실 배정에 관한 문제이다.
그리디 알고리즘 에 해당하는 문제이다
(기준은 끝나는 시간!) 빨리 끝내고 다른 회의를 최대한 넣어야 하기 때문이다. 이는 조금만 생각해도 알수 있었다.
하지만 처음짠 코드에서 채점 87%정도에서 틀렸습니다 ! 를 많이 보았는데
내가 고려하지 않은 반례가 테스트케이스에 있다는 것이였는데... 찾는데 꽤 오래걸렸다.
그것은 바로 끝나는 시간만을 기준으로 정렬을 했기 때문 이였다.
예를 들면 시작/끝이 3/3 3/3 1/3 같은 경우 회의 3개를 진행할 수 있는 것인데
조건에서 파악하여 앞에 두개 3/3 3/3은 카운트 할 수 있었으나
3/3을 해버리면 currenttime을 3으로 바꾸어 버리기 때문에 1/3이 카운트 되지 않는다.
즉 끝나는 시간이 같다면 시작시간이 먼저인것을 앞에 두게 정렬을 하여야 한다.
<필기>
<코드>
https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
그리디 알고리즘 기본문제 인 것 같다.
대기시간이 최소로 되게끔( 대기시간의 총합)
어쩌면 형평성 측면에서는 잘못되었다고도 할 수 있겠다..... 오직 효율성 만을.....
문제자체는 간단하고 쉽습니다.
오름차순 정렬을 시킨후 이전까지 걸렸던 시간과 그 사람이 걸리는 시간을 합을 더해서
총 결과(합) 에 더해주고 그 자신이 걸리는 시간이 들어있던 배열에 그 자신을 포함한 걸린 시간을 넣어주면 되겠습니다.
<필기>
<코드>
