링크 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 키가 같은 사람이 연속해서 줄을 설 경우를 생각하는데 오래 걸려서 많이 고민한 문제였습니다. 5555 (4C2) 65555 같은 경우만 생각해서 33332333 같은 경우를 고려하지 못했습니다. 스택에 차례대로 줄에 선 사람들을 넣으면서 1. top 보다 작으면 push를 하고 2. top 과 같으면 push 할 때 second를 top의 second += 1 (..
Koala - 5기/코딩테스트 준비 스터디
링크 https://www.acmicpc.net/problem/15654 문제 풀이 입력받은 수를 사전 순으로 출력하는 것이 문제의 조건이다. 수 들이 임의의 순서로 주어지므로 이를 정렬하고, 완전 탐색을 이용한다. j 번째 인덱스를 참조할 때마다 visit[j]를 true로 설정하여, 중복으로 입력되는 것을 방지한다. 재귀가 끝난 이후 false로 설정하여, 해당 index를 참조할 수 있도록 한다. 코드 결과
링크 https://www.acmicpc.net/problem/2798 풀이 N개의 카드중 3개를 뽑아 더하여 구하는 조합 문제이다. 이번에 배운 next_permutation을 이용한 조합알고리즘을 사용해보았다. 3중첩 for문, next_permutation, dfs를 이용하여 구현하였으며 이중 for문의 성능이 가장 우수하였고 dfs는 시간초과로 인하여 틀렸다. 코드 for문을 이용한 코드 #include using namespace std; int main() { int n,m; int card[100]; cin >> n>>m; for (int i = 0; i > card[i]; } int result = 0; for (int i = 0; i < n; i++) { f..
링크 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 채널 N으로 이동할 때 100번에서 +, - 로만 이동하는 방법과 고장나지 않은 버튼으로 누를 수 있는 번호를 누르고 필요시 +, -로 이동하는 방법 중 최소의 값을 구했습니다. 처음 제출할 때 초기 ans값을 초기화 하는 과정에서 아무 생각 없이 0으로 잡아 틀렸는데 문제를 풀 때 멍때리지 말고 차근 차근 생각하면서 풀어야 겠다고 느꼈습니다 (자의적인 해석 ❌ 문제 꼼..
링크 https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net 풀이 문제를 처음 보자마자 떠올린 풀이는 nC3으로 세 점을 뽑는 방법이였지만 시간복잡도 때문에 두 점을 뽑고 이진탐색으로 나머지 한 점이 찍혀있는지 확인하는 방법으로 풀었습니다. 하지만 위 방법으로 풀어도 시간초과가 떠서 이리저리 코드를 바꿔보면서 한참 해맸는데 (분명 시간복잡도 계산해 보면 시간 초과가 뜰리가 없는데...) 이진 탐색을 구현하는 함수 코드에서 ..
링크 : https://www.acmicpc.net/problem/1969 입력 첫 줄에 DNA의 수 N과 문자열의 길이 M 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 출력 첫째 줄에 Hamming Distance의 합이 가장 작은 DNA를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다. 예제 입력 : 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 예제 출력 : TAAGATAC 7 첫째 줄 T T A T T T4개, A1개 T출력 후 Hamming Dist..
https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net * 한 게시글에 코드블럭 언어를 하나로 통일해야 하나봐요ㅜㅜ Swift 외 코드는 하이라이트가 정상적이지 않을 수 있습니다.. Intro 처음에는 sort를 한 뒤 nC3으로 3개 조합을 뽑고 x[0]+x[2] = 2*x[1]라는 식을 통해 검증하려 하였으나 시간 초과가 발생하였습니다. 결론적으로 sort를 사용하지 않고 nC2의 조합을 사용하여 시간 초과 문제를 해결했습니..
백준 아이디 김대성 - ee1234 송수헌 - songsuheon97 이충형 - cndgud9056 박민희 - qag331 박채원 - p3c1w3 이인 - aorwn970 이지수 - wltn2814 이해찬 - cksgodl 허윤석 - ssfic3380 허태영 - gjxodud1 황재웅 - ghkdwodnd321 전영서 - wjsdudtj20 - 벌금 X 1. 문제 인증 - 하루 한 문제(미참여 -400원), 일주일에 6문제 하루 빼고 매일 인증 1주차 2주차 3주차 4주차 5주차 6주차 7주차 김대성 OOOOOO OOOOOOO OOOOOO OOOOOX OOOXXX OOOOXX XXXXXX 송수헌 OOOOOOO OOOOOOO OOOOOOO OOOOOO OOOOOOO OOOOOOO OOOOOOO 전영서 기초..
