khakha's dev log

문제 https://www.codetree.ai/training-field/frequent-problems?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 최고의 알고리즘 전문가들이 체계적인 코딩테스트 문제 유형 분류와 학습 커리큘럼을 제시합니다. 알고리즘 학습의 A to Z를 경험해보세요! www.codetree.ai 접근 갖가지 조건들을 다 붙혀논 문제라 구현하기 너무 힘들었다 ㅠ 특히 특정 정사각형을 선택하고, 그 부분만 회전하는 것을 코드로 짜는게 매우 어려웠다. 만약, 2차월 배열 전체를 시계방향 90도 회전한다면 1 (0,0) 2 (0,1) 3 (0,2) 4 (1,0) 5 (1,1) 6 (1,2) 7 (2,0) 8 (2,1) 9 (2,2) 7 (0,0) 4 ..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 select_chicken() : 백트래킹으로 주어진 M 갯수만큼의 치킨 조합 구성 calc_dist() : 조합이 완성되면 각 집별로 가까운 치킨 거리를 구해서 도시의 치킨 거리 최솟값을 구해준다. 코드 # 백트래킹 풀이 N,M = map(int, input().split(' ')) city = [] home = [] chick = [] visit = [[0 fo..

문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 접근 구현 문제 HTML 삽입 미리보기할 수 없는 소스 위 조건을 주어진 방향으로 거리만큼 이동한 좌표를 n 으로 나눈 나머지를 계산해서 구하고, 음수인 경우 +n 을 해주는 것으로 cloud 좌표를 구할 수 있다. cloud 좌표를 list말고 tuple로 넣어주면 시간초과에 걸리지 않았음. 코드 import sys input = sys.stdin.readline direction ..

문제 https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true The Coin Change Problem | HackerRank Given a list of 'm' coin values, how many ways can you make change for 'n' units? www.hackerrank.com 접근 dp를 이용한 풀이. 주어진 모든 동전의 경우를 하나씩 살피면서 1원부터 n원까지 만들 수 있는 경우의 수를 메모이제이션해가며 만들 수 있는 모든 경우를 구해준다. 코드 def getWays(n,c): dp = [0] * (n+1) dp[0] = 1 c.sort() for coin in c: if n >= coin: ..

문제 https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem?isFullScreen=true 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 접근 문자열 문제 defaultdict, set을 이용해서 풀었다. 'YES' 가 되는 경우는 모든 문자가 같은 갯수로 나타날 때 ex) "aabbcc" 1개 삭제 가능한 경우 갯수가 다른 문자(대신 갯수가 더 커야함)가 하나 있고, 그 차이가 1일 때..

문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근 백트래킹 + 브루트포스 중요한 부분은 dfs 내에서 cnt == n / 2 일 때 두 개의 팀으로 나눠서 각각의 능력치를 구해주는 것인데. 여기서 visited 배열을 활용해서 방문한 것과 방문하지 않은 것들 두개로 팀을 나눠서 능력치 계산 후 차이를 구해준다. 코드 n = int(input()) perform = [[] for _ in range(n)] for i in range(n): perform[i]..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근 브루트포스 (백트래킹) 주어진 +,-,*,/ 갯수를 하나씩 빼가면서 dfs 탐색 + 백트래킹을 통해 모든 경우의 수를 탐색한다. 코드 N = int(input()) num = list(map(int, input().split())) add, sub, mul, div = map(int, input().split()) min_value..

문제 https://www.hackerrank.com/challenges/candies/problem Candies | HackerRank Help Alice to save money by minimizing the total number of candies. www.hackerrank.com 접근 그리디 일단 최소 1개씩은 먹야하니 정답 배열을 길이 n만큼 1로 초기화하고 시작. 1. 첫번째 반복문에서는 인덱스 0 -> n-1 순서로 탐색하면서 오른쪽 친구 점수가 높으면 왼쪽 친구 갯수 + 1로 사탕 개수 더해준다. 이렇게 하고 나면 ex) arr = [1,2,3,4,3,2,1] 일때, ans = [1,2,3,4,1,1,1] 이 된다. 왼쪽 친구가 점수가 더 높은 경우도 비교해주려면 2. 두번째 반복문..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 백트래킹 + dfs 벽을 세울 수 있는 자리에 3개 벽을 세우는 모든 경우를 찾고 모든 경우 마다 안전 영역을 dfs를 통해 구한 후, 가장 큰 값을 구해준다. 코드 from collections import deque # import copy import sys input = sys.stdin.readline def bfs(): # copy_area = copy.deepcopy(area) -> 속..

문제 https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem?isFullScreen=true#! Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 접근 ranked는 내림차순, player는 오름차순인게 문제 풀이 핵심. ranked의 뒤부터 (가장 작은 점수부터) player의 앞부터 (가장 작은 점수부터) 비교하면 비교 횟수를 최소로 줄일 수 있다. 반복문 안에서 현재 player가 위치할 인덱스를 찾아주는 과정을 반복하면 ranked 배열에서 지나친 점수에 대해 ..