Kelly's journey to a coding master

문제https://www.acmicpc.net/problem/1799 요약이 문제는 백트래킹 문제인데, 매개변수 k를 어떻게 설정할지 고민하면서 시간을 정말 많이 썼다. 결국 다른 분의 기술 블로그에 나온 코드를 이해하여 완전히 이해하는 것을 목표로 잡고 풀게 되었다. (https://rapun7el.tistory.com/60) 일단 내 코드에서는 체스판 위의 공간을 어두운 부분과 밝은 부분, 두 부분으로 나누어서 아예 독립적으로 두고 각 부분에 놓을 수 있는 최대 비숍의 개수를 구한 뒤, 이 둘을 더해주는 방식으로 전개된다. 그리고 black, white 함수는 각각 backtracking 알고리즘으로 동작하며 비숍을 선택하는 모든 경우를 찾아 최대 비숍 개수를 계속 갱신해준다. 여기서 함수의 매개변수..

문제https://www.acmicpc.net/problem/17143소감시뮬레이션 알고리즘으로 분류되는 문제들의 특징을 검색해본 적 있다. 머리를 많이 굴릴 필요는 없지만 코드가 매우 길다는 점이다. 그런데 이 문제는 머리를 좀 써야 했다. 특정 부분에서 시간 복잡도를 줄여야 했는데, 그 부분에 직접 구상한 수학 공식을 적용해야 했기 때문이다. 아래에서 코드를 통해 설명을 이어나가겠다.코드import sysinput = sys.stdin.readlinedef fish(sec): for i in range(1, R+1): if graph[i][sec]: size = shark_info[graph[i][sec]][1] graph[i][sec] = 0..

코드import sysinput = sys.stdin.readlineT, W = map(int, input().split())drop = [0]for _ in range(T): drop.append(int(input()))dp = [[0 for _ in range(W+1)] for _ in range(T+1)]for t in range(1, T+1): for w in range(W+1): j = 1 if drop[t] == w % 2 + 1 else 0 dp[t][w] = max(dp[t-1][0:w+1]) + jprint(max(dp[T])) 풀이처음에는 알고리즘 분류를 보지 않고 풀기 시작했으며, T라는 유한한 횟수동안 반복하고 이전의 선택이 이후의 선택에 영향을 ..

문제 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 이 문제는 예제 입력 8개 모두 다 잘 통과되었는데도 '시간초과'가 자꾸 떠서 이유를 찾느라 꼬박 이틀을 들여다보았던 문제이다. 코드에 이상이 없는 것 같은데 도대체 무엇이 잘못되었는지 찾느라 아주 고생을 했었다.. ㅜ (갠적으로 코딩하면서 이게 젤 힘듦) 아무튼 힘들게 얻은 성공인 만큼 문제의 원인을 기록하여 다음엔 틀리지 않기 위해 글을 남긴다. (그리고 그 누군가 이 문제를 풀며 '..

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 import sys def bfs(x, y): dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] w = 1 # 그림의 넓이 while queue: x,y = queue.pop() for i in range(4): new_x = x + dx[i] new_y = y + dy[i] if (new_x = n or new_y = m)..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr KAKAO TECH 홈페이지의 문제 해설 각 개인 정보가 수집된 날과 약관 종류로부터 보관 가능 날짜를 구하고, 오늘 날짜가 보관 가능 날짜를 지났는지를 구하면 되는 문제입니다. 개인 정보의 유효기간은 해시 테이블 등의 방법으로 구할 수 있습니다. 날짜를 비교할 때 YYYY.MM.DD 형태 그대로 비교해도 되지만, 2000년 1월 1일로부터 며칠이 흘렀는지를 계산하면 정수 형태로 쉽게 비교..