본문 바로가기

Problem Solving

 (152)
[백준/C++] 1043번 거짓말 BFS 풀이 문제를 읽고 testcase를 쭉 훑어보니 결국 진실을 알고 있는 사람과 연결되지 않은 사람들로만 구성된 파티를 찾아내는 것으로 인식했다. 먼저 진실을 알고 있는 사람을 queue에 넣고 같은 파티를 edge로 판단했다. 이후 연결된 모든 사람들을 BFS로 미리 찾는 것을 생각했다. 이후 파티 명단을 보면서 아까 BFS를 통해 찾아낸 사람이 1명이라도 있다면 거짓말을 칠 수 없다고 코드를 짜고 실행시켰는데 한번에 통과를 받았다. 알고보니 이 문제는 유니온파인드(분리집합)문제인데 알고나서 문제를 보니 정말 그랬다. 다음에 시간나면 유니온파인드로도 풀어서 풀이를 올려야겠다. #include using namespace std; queue que ; vector party[51] ; int graph[51][..
[백준 / C++] 2295번 세 수의 합 풀이 처음 문제를 읽었을 때는 N의 개수가 최대 1000개니 sorting한 이후 3개씩 슬라이딩 윈도우로 브루트포스 방식을 취하면 풀리지 않을까 생각하였으나, 슬라이딩 한 것들을 다시 확인 하는 방법에서 막혔고 다시보니 중복되게 선택할 수 있었다. 이후 map을 이용해 for문 3개 중첩을 무지성으로 시도하다 생각해보니 N3logN 이라 시간 초과 문제가 생겼다. (1000개를 3제곱하면 최소 10억이라 10초다. 심지어 map은 메모리 초과문제도 생겨 set으로 변경하였다) 더 이상 줄일 방법을 찾지 못해 힌트를 보았다가 다들 천재인가 싶었다. 풀이 방법은 간단하다. x,y,z 를 따로 구하지 않고 y,z를 합으로 한 배열(sum)을 하나 생성한다 (N2) 기존 배열을 arr라고 가정했을 때 x + y +..
[백준/C++/ICPC] 4090번 뱀파이어 숫자 오랜만에 골드를 풀어서 그런지 대략 일주일 걸린 것 같다. 처음 문제를 봤을 때는 안에 있는 숫자들을 순열로 뽑아서 나누는 지점을 정해서 브루트포스로 돌리면 답이 나올 것 같았다. 그런데 뱀파이어 숫자가 아닌 수를 입력으로 주는 경우 뱀파이어 숫자이며 input보다 큰 숫자 중 가장 작은 숫자를 출력에서 멘붕이 왔다. 내가 말한 방법은 100% 또 다시 x보다 큰 뱀파이어 숫자를 여러번 찾는 과정에서 시간 초과가 날 것 같았다. (10초라는 후한 시간이 있어 시도해볼까 싶다가 최근 정답률이 너무 떨어져서 신중해졌다.) 오늘 다시 곰곰히 생각해보다 문제를 쪼개보기로 결정하였는데 문제를 나눠보다보니 더 좋은 방법이 떠올랐고 뱀파이어 숫자 구분 함수를 아래와 같이 2개의 문제로 나눴다. 사용한 숫자가 모두 같..
[백준/C++] 2358번 평행선 뭔가 자세히 보다가 결국 x축과 평행한 선의 갯수와 y축과 평행한 선의 갯수를 찾으면 된다는 것을 알게되었다. map에 key값으로 x좌표와 y좌표를 따로 넣고, 같은 key값으로 숫자가 1번 이상 들어가게 된다면 평행한 선의 조건을 충족하므로 map으로 구현하였다. key값만 따로 보관하는 방법을 찾지 못해서 set에 key값을 저장해주었다. #include using namespace std ; set points ; map x_axis, y_axis ; int N, x, y, answer ; int main() { ios::sync_with_stdio(0), cin.tie(0) ; cin >> N ; for(int i = 0 ; i > x >> y ; x_axis[x..
[백준/C++] 23826번 와이파이 문제 설명이 장황한데 결국 첫 줄에 받은 공용와이파이가 manhattan distance( |X1 - X2| + |Y1 - Y2| ) 거리로 특정 방에 영향을 미치고 각 방에 설정된 공유기가 전파에 같은 방법으로 방해를 끼칠 때 가장 전파가 잘 터지는 방을 구하는 문제이다. 모든 방을 둘러보며 모든 공유기가 닿았을 때 미치는 결과를 확인해보아야 하므로 브루트포스로 해결할 수 있겠다는 생각을 하였다. 중간에 미치는 전파가 음수가 되는 실수를 했는데 예제 1번에서 잘 걸러줘 한 번에 성공할 수 있었다. 예제가 친절한 문제다.. /** * @file 25826.cpp * @author fpqpsxh * @date 2023-01-18 **/ #include using namespace std ; int sign..
[백준/C++] 25370번 카드 숫자 곱의 경우의 수 그냥 문제 하나 간단하게 풀고 싶어서 도전한 문제이다. 곱셈에 패턴이 보이지는 않고 1~9까지의 카드를 최대 7장 뽑는다면 매우 작은 숫자니 브루트포스 문제라고 생각하였다. 그러다 문득 곱셈이니 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1로 생각해보면 1~9를 곱한 것에 다시 1 ~ 9를 곱하는 형식을 N번 반복하는 형태가 되겠다는 생각을 하게 되었다. set을 이용해 중복 없이 key를 사용하면 편하겠다 생각했는데 sort가 되는 문제가 있어 배열 2개를 사용하여 중복 체크를 한 후 배열에 값들을 담아내는 형식으로 구현했다. (최대숫자도 400만 언저리니 배열 크기를 널널하게 잡았다.) /** * @file 25370.cpp * @author fpqpsxh * @date 2023-01-..
[백준/C++] 1920번 수 찾기 갑자기 동아리원 한 명이 이 문제 ios::sync_with_stdio(0) 하나 차이로 통과하고 못한다고 이야기해서 진짜인가? 하고 풀어봤다. 정답 비율을 보니 그럴 수 있겠다는 생각이 들었다. 문제를 보며 가장 먼저 한 생각은 그냥 10만개 솔트 N log(N) 2번이면 오바되고 하나의 배열을 솔트하고 이분탐색하는 방법이 시간 내에 통과할 수 있겠구나 했지만 귀찮아서 map으로 되나 짜봤다. /** * @file 1920 * @author fpqpsxh * @date 2023-01-10 */ #include using namespace std ; int main() { int N, M, tmp ; map mp ; vector ans ; cin >> N ; while(N--) { cin >> tmp ;..
[백준/C++] 25947번 선물할인 분명 실버2인데 생각보다 까다로웠던 것 같다. ICPC 2022 인터넷 예선 당시에는 1초라는 압박감에 pq를 사용해야하나 고민하다 뒤늦게 반례를 찾아서 생각해낸 방법은 Greedy(탐욕법)이었다. 작은 것부터 챙겨나가다가 못챙기는 순간이 생기면 그 물건을 할인해서 넣을 수 있는지 확인하고 그 이후 가지고 있는 값 중에 가장 큰 값을 차례대로 줄여가며 구매할 수 있는지 체크하면 되는 간단한 알고리즘이었는데 긴장해서 그런지 구현이 생각보다 막혔던 것으로 기억한다. 백준에 제출할 때는 로직은 분명 맞는데 왜 틀리지하고 고민하다가 마지막에 + 1을 해주게 되어 처음부터 넣을 수 없는 아이템일 때도 1로 체크되는 문제가 있었다. 역시 10% 이내나 90%이내에서 터지면 경계값 확인을 하는게 제일 좋은 것 같다...

티스토리툴바