관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net bfs + heapq로 풀어낼 수 있는 문제. 현재 위치에서 1. bfs로 '잡아먹을 수 있는 물고기 좌표'를 탐색한다. 2. 탐색..

https://level.goorm.io/exam/43114/%EA%B3%B5%EC%97%B0-%EC%A2%8C%EC%84%9D/quiz/1 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io DP문제.

https://level.goorm.io/exam/43144/%EB%8B%AC%EA%B1%80-%EB%B6%80%ED%99%94%EA%B8%B0/quiz/1 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 출력 부문의 설명이 별로 명확하지 않다. '처음부터 달걀이 전부 부화한 상태일 경우' 0 출력 '처음부터 달걀이 부화할 수 없는 상태일 경우' -1 출력 이외의 경우, 부화할 때까지의 최소 날짜를 출력하라는 뜻이다.

https://level.goorm.io/exam/49104/%EC%99%B8%EC%A3%BC/quiz/1 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 1. 날짜를 역순으로 생각해야 한다. 현재 날짜가 7일이라면, 마감일이 6일 이전인 업무는 참여할 수 없다. 맨 마지막 날짜부터 첫번째 날짜까지를 순회하면서 '해당 날짜에 가장 이윤이 남는 작업'을 찾는다. = 마감일과 보수를 저장한 배열을 '마감일'이 높은 순, '보수 높은 순'으로 정렬한다. 이 경우 '마감일'이 동일한 작업은 가장 높은 보수를 제공하는 작업으로 정렬된다. 2. 동일한 날에 여러 업무가 들어올 경우, 나중을 위해 저장해야 한다. 마감일이 7일까지인 업무가 있고 3일차에..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 위상정렬 + bfs를 적용한 느낌의 문제.

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 접근 방법이 백준 키로거 문제와 흡사하다. [Python] 백준 5397. 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에.. insp..

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 전체 scoreboard 값이 주어져 있고, alice의 score가 주어지면 해당 score는 전체 scoreboard에서 몇 등인지를 표시하는 문제. 해커랭크에서 이 문제는 'Implementation'으로 분류돼 있다. 처음 봤을 땐 단순히 'alice의 매 score를 scoreboard에서 binary search해서 풀면 되겠다' 생각했는데, time l..

https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem Sherlock and the Valid String | HackerRank Remove some characters from the string such that the new string's characters have the same frequency. www.hackerrank.com 문자열의 개수를 셌을 때, 문자열 한 개만 지웠을 때 모든 문자열의 개수가 동일하면 YES, 아니면 NO를 출력하는 함수. "문자열 한 개만 지웠을 때" YES가 가능하려면, 세 가지 경우가 있다. 1. 문자열 개수 자체가 1개인 경우 2. 가장 많이 등장한 문자열에서 1개를 제거했을 때,..

https://www.hackerrank.com/challenges/big-sorting/problem Big Sorting | HackerRank Sort an array of very long numeric strings. www.hackerrank.com 난해한 문제는 아니었지만, Python sorting의 특징을 하나 알 수 있었던 문제. 해당 문제 forum을 들어가보면 더 자세히 알 수 있다. Python에서 int -> str, str -> int 형변환은 연산량이 비싼 편이다. 특히 이 문제처럼 숫자값이 클 경우 연산량이 매우 비싸게 작용한다. 따라서 일반적으로 생각하는 문제해결방법인 '문자열을 숫자로 변환 -> 대소비교 -> 정렬' 식의 연산은 time limit에 걸린다. 대안으로 k..

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com constraint 값이 꽤 커 보여서, 2D Array로 그래프를 구성하는 대신 defaultdict를 사용했다. bfs로 그래프를 순회하면서, 시작점의 color와 순회지점의 color가 일치하는 지점에서 순회 횟수를 반환하면 된다.