https://velog.io/@tlatldms 로 이사갔습니다! https://velog.io/@tlatldms 카카오 코딩테스트 - 프렌즈4블록 string은 immutable 하므로 배열처럼 str[3] = 's' 이렇게 assign 해줄 수 없다. 그래서 입력 값을 board[i] = list(board[i]) 로 ['s','t','r'] 형태로 바꿔줬다. 한 블록이 여러 2x2에 해당될 수 있으므로 중복 처리를 위해 한 턴 체크를 할 때 사라지는 블록을 set에 저장했다. 처음에 s = {} 형태로 set도 되는 줄 알고 초기화했는데 무조건 dictionary로 인식하는 것 같다. s = set()로 초기화해야 한다. 블록은 열 단위로 empty 칸을 보면서 처리했는데, board[m-1][j]부터 1씩 빼면서, 즉 보드의 바닥부터 체크했다. 그러면 o(m) 으로 해결할 수 있는데, 빈 칸이면 카운트를 세고, 빈칸이 아니면 이때까지 나온 빈.. 카카오 코딩테스트 - 압축 array.index(key) 하면 배열 내의 index를 반환해준다. 하지만 배열이라 하나씩 체크해가며 비교해야하니 O(n)이다. 다른 사람의 풀이를 보니 아예 key를 문자열로, value를 index로 한 dictionary를 선언해서 쓰던데 시퀀셜하게 저장하고 그 index를 가져와야하니 배열로 해도 되지만, 역으로 그 index를 문자열로 접근해 가져와야하니 dictionary로 만들어 O(1)의 시간으로 접근하는게 나은 것 같다. 그리고 처음에는 start, end의 index로 하지 않고 start에 i를 추가해가며 start+i를 사용했는데, 파이썬의 배열[s:e]가 사실 s~e-1로 슬라이싱해주다 보니 1씩 더하고 빼는게 좀 헷갈리는것같다 차라리 e를 계산해두고, 슬라이싱할 때 e+1로 .. 카카오 2020 Blind 블록 이동하기 파이썬 BFS + 시뮬레이션 문제 현재 상태가 가로/ 세로인지, 위/오/아/왼으로 움직일건지로 구분했다. 잘 찾아보면 dir xy로 돌릴 수 있는 규칙을 찾을 수 있을 것 같은데 개인적으로 이렇게 복잡할 땐 오히려 하나씩 생각하면서 구현해가며 푸는 게 시간이 덜 걸리는것 같다 같은 칸에 대해서도 가로, 세로의 경우가 있을 수 있으므로 기준을 잘 잡는게 중요하다. visit 배열을 visit[101][101][2]로 잡았는데, 마지막 2칸은 세로 / 가로의 경우를 나눈 것이다. 가로일 때는 왼쪽칸, 세로일 때는 위쪽칸을 기준으로 잡았다. 기준을 왼쪽, 위로 잡아 구현했다는 것을 명심하고 칸 수 계산을 잘 해야 한다. 예를 들어 가로로 놓여진 로봇의 현재 (x,y) 에서 오른쪽으로 옮기고 싶으면 board[x][y.. (프로그래머스 )카카오 코딩테스트 자동완성 문제 #include #include #include #include using namespace std; int total_cnt; struct trie { trie * next[26]; int count=1; }; void dfs(trie * t) { if (t->count == 1) { total_cnt++; return; } else { total_cnt += t->count; } for (int i=0; inext[i] == NULL) continue; dfs(t->next[i]); } } void find(const char * str, trie * t) { if (*str == '\0') return; int alpha_num = (*str)-'a'; if (t->next[alpha_num]->c.. 백준 15686번 치킨 배달 풀이 https://www.acmicpc.net/problem/15686 BFS + 조합 완전탐색 치킨집에서 집으로 배달을 한다고 문제 이름 그대로 받아들였으면 빨리 풀었을 것 같다 처음에 손님들이 치킨집에 가서 치킨먹는 그림을 생각하고 풀었다가 실패했다. 내가 멍청한거랑 도대체 무슨 상관일까 싶지만 ㅋㅋㅋ 최소여야하는건 집에서 치킨집까지의 치킨 거리의 합이니 주어진 m개의 치킨집은 모두 써야 한다. 그리고 치킨집의 개수 중에서 m개를 뽑아 m개의 치킨집으로 만들 수 있는 모든 경우를 검사했다. 문제에서 대놓고 조합으로 모든 경우를 구하라고 써놓은것같다.. 몇달 전 이 문제를 처음 풀었을 때는 모든 집의 입장에서 치킨집까지의 거리를 구하려고 시도했었지만 시간초과가 났다. 집의 입장에서 모든 조합된 치킨집들과의.. 이전 1 다음
