메이쁘

https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비� www.acmicpc.net Disjoint - Set 알고리즘 중 하나. 처음에 풀긴 풀었는데 브루트 포스 처럼 풀어서 속도랑 메모리가 엄청났었다. 하지만 Disjoint-Set (Union-Find) 알고리즘으로 해결한 굇수님의 코드를 보고 한 대 쎄게 맞은 느낌이 들었다. 아직 나는 부족한 것이 많고, 배울 것이 많다. 처음에 하단 소스코드를 보면 무조건 헷갈리고 어려울 것이다. 핵심만 기억하자. - 처음 비행장 게이트 배열..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 그놈의 시간 초과 때문에 (제한시간 1초) 그리고 나만의 이진 탐색 방법을 사용하려고 하다보니 예외가 계속 나와서 그거 해결하느라 시간이 오래걸렸다. 결국에는 내 탐색 알고리즘으로 문제를 해결했으나.. *** 실제 이진탐색을 사용하는 방법도 있다. 베스트 정답을 보니 이렇게 쉽게 풀 수 있는 방법이 있었어? 생각이 들며 이 방법을 공부했다. *** 정말 감사합니다..

https://www.acmicpc.net/problem/10711 10711번: 모래성 문제 명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 �� www.acmicpc.net 시간초과 때문에 꽤나 애먹었던 문제.. 핵심 키워드는 이거다. "모래성이 아닌 빈 모래를 활용하라." BFS, DFS, Deque, 2중 for문 등등 여러 방법을 동원해봤지만 테스트케이스는 통과하는데 시간은 초과되는 문제가 계속 일어났다. 그러던 중, 번뜩 떠올랐다. "굳이 파도 한 번마다 모래성 주위 8방향을 탐색하며 갯수 셀 필요가 있을까?" "모래성은 어차피 줄어들고,..

https://www.acmicpc.net/problem/2804 2804번: 크로스워드 만들기 문제 창영이는 크로스워드 퍼즐을 만들려고 한다. 두 단어 A와 B가 주어진다. A는 가로로 놓여야 하고, B는 세로로 놓여야 한다. 또, 두 단어는 서로 교차해야 한다. (정확히 한 글자를 공유해야 한 www.acmicpc.net 쉬운 문제이기 때문에 별도 알고리즘이 딱히 없었다. A, B 두 단어가 존재하면 A는 가로, B는 세로로 출력하는데 우선순위가 1) A와 B의 공통 문자를 찾는 것(A for in B for) 2) A 내 공통문자 중 인덱스가 가장 작은 것 3) B 내 공통문자 중 인덱스가 가장 작은 것 이고, 출력 시 A 공통문자 인덱스는 B 출력에 영향을, B 공통문자 인덱스는 A 출력에 영향을..

https://www.acmicpc.net/problem/16570 16570번: 앞뒤가 맞는 수열 수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계 www.acmicpc.net 처음에 시행착오를 거치고 나서 정답을 도출했다. 바로.. 시간 초과! 제한 시간은 2초였기 때문에 for문 3개로는 버티질 못했던 것이다. 그래서 for문을 2개로 줄이는 방법이 없을까...? 무조건 있겠지... 이걸 찾는 것이 이 문제의 취지다! 라고 생각하여 골똘히 계속 생각했고, 해결 방법을 알아냈다!!!! 그래서..

안녕하세요. 거두절미하고 간단 정리! 바로 작성하겠습니다. Heap(힙) - 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조. - 여러 개의 값들 중에서 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조. - 힙 트리에서는 중복된 값을 허용한다. - 힙은 키와 값을 가지는 노드가 이루어진 트리이다. - 주로 배열을 사용하고, 배열의 첫 번째 인덱스 0은 사용하지 않는다. - 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. (루트 = 1, 왼쪽 자식 = 2, 오른쪽 = 3) - 왼쪽 자식 index : 2 * 부모 index - 오른쪽 자식 index : (2 * 부모 index) + 1 - 부모 index : 자식 index / 2 - Max heap(최대 힙) : ..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net DFS와 BFS를 섞은 문제 하지만 필자는 DFS만 사용했다. (다른 사람들보다 성능은 조금 떨어진다..) 이 문제는 가장 짧은 다리 길이 를 구하는 문제이다. 그래서 필자가 푼 이 방법은 붙어있는 육지들 중 가장자리 육지들의 좌표값들만 별도 저장해뒀다가 붙어있는 육지 별로 1:1 매칭하여 x, y 차를 구한다. x, y 차란 두 개의 육지 P1, P2가 존재할 때 gapX = Math.abs(P1.x..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 쉬운 문제. 핵심은 1. 연속된 같은 숫자들이 있으면 하나로 생각 2. 0 과 1 중 연속된 같은 숫자들의 종류 개수가 작은 것이 정답 ex) 0011100 일 때, 00 / 111 / 00 -> 종류 0 / 1 / 0 -> 개수 : 0 - 2개, 1 - 1개 이므로 1번만 뒤집으면 모든 숫자를 같게 할 수 있음. *** 참고로, 종류 개수 셀 때 맨 마지막 문자까지 세야 하므로 for문 종료 후..

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 팰린드롬 문제 중 꽤 어려운 문제이다. *** 팰린드롬 유사 문제 https://maivve.tistory.com/29 (JAVA) 백준 10942번 : 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진..

https://www.acmicpc.net/problem/2810 2810번: 컵홀더 문제 십년이면 강산이 변한다. 강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람 www.acmicpc.net 문자열 처리 관련 문제이다. 이 문제도 크게 어려움은 없다. 문제에서 알아둬야 할 것들은 이 부분이다. 1) 양 끝 좌석에는 컵홀더가 하나씩 존재한다. 2) 커플석(L)은 항상 그 사이에 컵홀더 존재X 3) 좌석의 양 쪽(왼쪽, 오른쪽) 에는 컵홀더가 존재 = 인접한 좌석 사이에 컵홀더가 존재 4) 자기 자신의 좌석 양 옆에 있는 컵홀더에만 컵을 놓을 수 있다. 바로 매커니즘으로 넘어가겠다. 매커니즘 1..