문제 https://programmers.co.kr/learn/courses/30/lessons/92334?language=cpp 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 사실 풀자마자 어떻게 푸는지 감은 왔으나, 지나치게 오랜만에 문제를 접한 탓에 메소드들이 생각이 잘 안 나서 살짝 헤맸다.. 그래도 풀자마자 통과할 수 있었다...(다행) 이 문제는 특별한 자료구조나 알고리즘이 필요한 것이 아니라 그냥 요구사항을 제대로 이해해야하는 게 관건이다. 특히 신고한 유저 - 신고 당한 유저의 관계에 ..

문제 : 백준 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 흔한 BFS문제이나 생각보다 시간 초과가 계속 발생해서 고전한 문제이다. 효율적인 문제 접근을 위해서 방문 여부 처리와 소들간의 만남 여부 처리가 중요하다. 점차 발전해나가면서 시도한 결과는 아래와 같다. - BFS를 소를 일대일 대응시키고 연결되면 BFS 탐색 종료한다. - 일대일 대응은 비효율적. 소들간에 경로가 겹치는 경우에는 중복적인 작업이 많이 이루어진다. 그래서 일대다 대응으로 소들간의 연결 가능..

백준: 1800: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 상당히 오랫동안 블로그 업로드나 알고리즘 풀이를 오랫동안 쉬었다. 아무래도 직장에 들어가면서 자연스레 나태해진 탓일까... 사실 회사 내 보안이 철저해서 사진 하나 찍는 것도 조심스러워서 블로그 자체도 쉬게 되었다. 이러면 안되는데... 그래서 반성하고 최대한 하루에 하나씩 백준 문제풀이를 하고자 나만의 위클리 챌린지를 시작해보려고 한다..! 그런데 우선 첫 문제 골드부터 막혀서 너무 슬펐다..

프로그래머스: 링크 코딩테스트 연습 - 11주차_아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 사실 최단 거리를 구하는 문제라서 BFS를 썼어야 이론상 조금 더 효율적인데, 그냥 DFS 재귀가 손에 익어서 DFS의 형식으로 문제를 풀었다. 그것보다 더욱 중대한 문제가 풀이 과정 중에 발생했다. 생각보다 문제는 빠르게 이해한 편이었으나, 문제의 함정을 파악하고 이를 해결하는 데 상당히 오래걸렸다. 상하좌우로 단순히 이동하면 되는 문제가 아니라, ..

백준: 문제 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 내일 코테를 대비하기 위해 평소에 잘 풀어보지 않은 유형들 위주로 풀고 있다. 이번에는 위상정렬(Topological Sort)! 그래프 노드별로 선후가 정해져있어서 순서를 정하기 위해 크게 2개의 배열을 사용해야 한다. 만약 a → b 식으로 선수, 후수가 정해진다면, 1. 각 노드별 진입차수 inDegree, 즉 b 노드를 방문하기 위해 이전에 방문해야하는 a 노드 개수 기록 2. 각 노드별 후수 노드들, 즉 a에 대한 b 노..

백준: 문제 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 오늘 아예 작정하고 슬라이딩 윈도우 문제를 풀고 있다. 이전 두 문제는 별도의 배열을 사용해 조금 어렵게 접근했어야 했던 문제라면 이번 문제는 풀이 방식은 쉬우나 배열 처리가 어려운 문제였다. 왜냐하면 우선 전체 배열 크기를 문제에서 제시하지 않고 주어진 수의 범위를 통해 계산해야했기 때문이다. 여기서 K의 범위가 0이상 2,000,000이므로 전체 배열의 크기는 2,000,000 * 2 + 1이다. 이제 주어진 양동이를 알맞게 위치시키고, 앨버트를 한칸씩 옮기면서 2 * ..