빠르고 꾸준하게

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905# 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 이 문제는 완전 탐색으로 풀 수도 있겠지만, 시간 초과를 피하기는 쉽지 않을 것 같습니다. 1000 * 1000 조건에다가 중복되는 연산들이 많기 때문이죠. 중복되는 연산이 있다? 그렇다면 생각해볼 수 있는게 다이나믹 프로그래밍(DP)이였습니다. 어쨌든 3 * 3 정사각형이 만들어지기 위해서는 2 * 2 정사각형이 만들어져야 가능했으니까요. DP로 생각해보면, 먼저 현재 위치가 [i][j]라고 했을 때, [i-1][j], [i][j-1], [i-1][..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]11404(파이썬) - 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제는 제목을 읽으면 바로 떠오르는 풀이법이 하나 있죠. 바로 플로이드 워셜입니다. 플로이드 워셜은 다익스트라 알고리즘과 함께 최단거리를 계산하는 문제의 풀이법으로 유명한데요, 혹시 처음 들어보신분들은 아래 게시물을 한 번 읽고오시면 도움이 될 것 같습니다. 다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap)) 다익스트라 알고리즘 최단경로 알고리즘으로 특정 노드에서 ..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 후보키(2019 KAKAO BLIND RECRUITMENT)

https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 최근 문제를 풀면서 유형이 정해져 있지 않은 구현문제푸는 연습을 많이 해야겠다는 생각을 했습니다. 때문에 프로그래머스에서 2단계 문제들을 모두 풀어보고 있죠. 이 문제 또한 단순한 구현 문제인데, 생각하고 푸는데 꽤 오랜 시간이 걸렸습니다...

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 15685(파이썬) - 드래곤 커브

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 이 문제는 뭔가 엄청 어려운 거 같았는데 엄청 어려웠던... 문제입니다. 하지만 그림을 그려보면서 문제를 읽다보니까 '규칙을 무조건 찾아야겠다'라는 생각이 들었습니다. 0,1,2,3의 방향을 가지고 규칙을 찾다보니 방향이 앞에 이전 세대의 정보를 뒤집어 거기에 1을 더해주면 됩니다. 4면 다시 처음인 0으로 돌려주면 됩니다. 이 구현은 4로 나눈 나머지로 계산해주면 됩니..