Algorithm
[BOJ] 백준 16929 Two dots - Python/Java
문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 해설 이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다. 저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다. 그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이..
Algorithm
[프로그래머스(파이썬/Python)] 보석 쇼핑(2020 카카오 개발자 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 카카오의 효율성 문제를 풀면 눈물이 납니다. 이 문제를 풀 때도 1) O(N^2)으로 몇 가지 트릭을 넣은 풀이, 2) 이분 탐색으로 O(N*logN), 두 가지 방법을 시도해보았지만 모두 다 효율성 테스트를 통과하지 못했습니다... 사실, 이 문제에서 투 포인터를 써야겠다는 생각은 바로 들었지만 뭔가 계속 구현이 꼬이고 몇 가지 테스트 케이스가 틀리고를 반복하다보니 다른 방법으로 회피한 것 같은 느낌도 있었습..
Algorithm
[백준(파이썬/Python)] 1062_가르침
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 이 문제에서 'a','n','t','i','c'는 반드시 가르쳐야 하고, 모든 단어의 맨 처음 네 글자가 'anta', 'tica'라는 조건은 아마 시간 복잡도를 맞추기 위한 설정이거나 약간의 구현(?)을 유도하기 위한 것 같습니다. 하지만 기본적으로 단어의 개수나 알파벳의 수가 크지 않기 때문에 완전 탐색을 해야겠다는 생각을 할 수 있었고, 다만 조금이나마 효율적인 완전탐색을 하기 위한 ..
