잡담연구소

IDEA 보자마자 아 조합구현이네? 생각했다. 1 ~ 8까지 있으면 조합을 통해 1,4,6,7 을 고르고 이걸 start라고 생각하면 선택받지못한 사람들은 link가 된다. start 내 사람들을 2명씩 골라서 점수를 내고, link도 똑같이 해 점수의 차를 비교하면 된다. n명 중 n/2명을 고르는 것도 조합으로 구현하고 n/2명 중 2명을 고르는 것도 조합으로 구현하려고 했는데 그러면 지저분해져서 어차피 2명이니까 투포인터로 합을 구했다. 선택 된 사람과 선택받지못한 사람을 어떻게 나누지? 에 대해 많이 고민했다. temp라는 벡터에 넣어주고 1 ~ n 까지 temp안에 없으면 link 팀 있으면 start팀 이렇게 구성을 하다 보니까 시간이 더 걸릴 거 같더라,,,, 생각을 해보니 visited가 ..

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 아... 이 문제도 3시간 안에 푸는 문제 중 하나였는데,,,, ㅜㅜㅜㅜ 이게 bfs로 풀릴 거라곤 생각도 못했다. 맨 처음에는 아 그리디네?? 왜 실버1이지?하면서 풀었다. 틀렸단다 아무리 봐도 틀릴 구석이 없는데,,,ㅜㅜ 맨 처음에 생각했던 건 입력받은 편의점 좌표들에 하나하나 옮겨가면서 이전 편의점과의 거리를 계산해 1000이하면 다음으로 넘어가고, 1000보다 크면 sad를 출력하는 거였다. 틀린코..

www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 아ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ AI 부캠 코테 준비하겠다고 1시간에 3문제 푸는 거 연습했는데,,,,꼴랑 한문제밖에 못풀었다,,,,,, 시험볼 때 엄청 긴장하는 체질인데 큰일이다,,,,,긴장안해도 한 문제라니,,,, 다리놓기 문제는 실버5라서 엄청 만만하게봤다. 딱 보자마자 ? 순열이네 역시~~ 이러면서 순열 코드를 짜고 돌렸는데 계속 시간초과가 뜨더라,,,,29C13같은 경우 답이 나오지도 않음 이 문제에선 최대 수가..

www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net IDEA 어려운 문제는 아니지만 나에게 큰 교훈을 준 문제다,,,ㅜ 문제 설명을 먼저하자면 두가지 조건을 만족시키는 0,1로만 이루어져있는 수의 개수를 구하는 거다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. DP문제라고 생각해 DP로 풀었다. 최근에 풀었던 쉬운 계단 수 문제랑 비슷해보여서 , DP[M][N] : 끝..

www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 12번 푸러따,,,,,,, 의지의 한국인이라는 걸 보여줘버려따,,,,,,,, 문제를 처음 접했을 때는 어떻게 풀어야할지 감도 안오고 우선순위큐로 뭐 어쩌라는건지,,, 싶어서 다른 문제 풀었는데, 머리를 감다가 번득 생각났다. 우선순위에서 제일 작은 값을 꺼내고, 소수들과 곱해서 다시 집어넣으면 되겠구나! 그래도 시행착오를 많이 겪었다. 크게 세번의 과정을 거쳐 풀 수 있었다. ❌실패코..

3주차에 힙정렬을 구현하면서 힙에 대해서 간략하게 정리했었다. 3주차 힙정렬 👉 blahblahlab.tistory.com/33 1) 힙이란 ? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure) 부모노드와 자식노드 사이에 일정한 대소관계가 존재한다. 부모노드가 자식노드보다 더 크면 최대힙(max heap) 부모노드가 자식노드보다 더 작으면 최소힙(min heap) 형제끼리는 대소관계가 존재하지 않는다. 부모와 자식간의 인덱스는 왼쪽자식 = 2 * 부모노드 , 오른쪽 자식 = 2 * 부모노드 +1 을 성립한다. 그림으로 보는 게 훨씬 직관적이다. 부모노드가 자식노드보다 큰 최대힙의 ..