난이도: Lv.3유형: BFS해결 여부: 정답내가 생각했던 아이디어/큰 가닥가능한 이동 경우 나누자. 각각 가로인경우와 세로인 경우.. 그래서 좌표로 표현하기. 근데 이건 나중에 알고보니 상관 없었다.근데 쌩으로 좌표에다가 기록은 안됨. 차가 2칸짜리여서 경우의수가 여러가지임... 해싱을 해야할듯 -> 딕셔너리에 추가하기? (x1,y1,x2,y2) : result 회전:가로인 경우 [(i,j),(i,j+1)] -> [(i-1,j),(i,j),] or [(i,j),(i+1,j)] or [(i,j+1),(i+1,j+1)] or [(i-1,j+1),(i,j+1)]회전:세로인 경우 [(i,j),(i+1,j)] -> [(i,j),(i,j-1)] or [(i,j),(i,j+1)] or [(i+1,j-1),(i+1..
Algorithm/BFS,DFS
난이도: Lv.3유형: DFS/BFS해결 여부: 틀림내가 생각했던 아이디어/큰 가닥칸수기반이니 일단 큰것부터 그리디인접한 칸 비어있으면 안된다. = 걍 game_board에서도 table의 블럭처럼 어떤 형태 들어가는지 똑같이 처리해라. 칸수 같은 것끼리만 넣을 수 있다.그러면 조각의 분류가 먼저인거 같은데? 어떻게 조각의 분류를 나타낼 수 있지?최소크기의 모든걸 포함하는 직사각형 하나 만들고 들어가는지?아니면 좌표로 정하기? 이게 더 낫겠다. 그리고 숫자 범위에 따라 최소값으로 한번 가공하는 식으로 객체지향으로 푸는게 낫겠군.. 오답 이유일단 시간도 다 되었고, 어차피 이 속도면 실전에서는 틀렸다 생각해 문제풀이 중단하였다. 결국 큰 흐름은 알겠는데 뭔가 공간구현이 내가 약한것 같다.해답리스트 좌표 ..
난이도: Lv.3유형: bfs해결 여부: 틀림내가 생각했던 아이디어/큰 가닥-길찾기 문제. 출발지와 목적지 정해짐. union tree 아니면 다익스트라 다 -1로 해놓고 destination 0, 그리고 destination에서 뻗어나가기?길 중심의 bfs로 가능할 거 같은데라고 생각해서 접근했으나 문법 오류로 틀렸다.오답 이유일단 중간에 삭제할일이 생겨서 리스트를 SET으로 바꾸고 했는데 SET는 순회중에 삭제가 안된다... 문법오류난다.해답그래서 인접리스트를 쓰는게 정답이었다. 이 문제에서는 굳이 삭제 안해도 시간 timeover 안나왔고, 항상 이런 인접 주어지면 바로 인접리스트 형태로 바꾸는게 중요하다#기억할 문법 - deque 초기화 할때는 그냥 값 넣지 말고 d=deque([start]) 이..
난이도: Lv.3유형: DFS/BFS해결 여부: 오답 내가 생각했던 아이디어/큰 가닥결국 가장 바깥선을 어떻게 찾을것인가? 에 관한 문제라고 보고 처음에는 그냥 하려다가 붙어있는 선 ㄷ자 형태가 판별 안되는 것을 깨닫고 2배로 늘리는 것을 생각했다.그런데 그것보다는 그냥 선 말고 전체 면적을 기준으로 True/False하고 이후에 선을 판정하는 방식을 생각했는데 틀렸다.오답 이유2배로 늘리는게 모범답안이긴 했다. 해답격자점이랑 선/면적 로직 파악이 좀 잘 안되가지고 틀렸다. 딱 시뮬레이션 같은 문제였는데 차피 시간 다되서 틀렸다. #기억할 문법 - 어딘가에 슬라이싱 째로 넣을꺼면 같은크기의 값으로 []로 감싸서 넣어야 한다- 그리고 2차원 배열은 첫번째 인덱스 행으로는 넣을 수가 없어서 2번째는 슬라이싱..
난이도: Lv.3유형: bfs/dfs해결 여부: 정답내가 생각했던 아이디어/큰 가닥전형적인 bfs/dfs 택일하는 그래프 연결문제다. 정답을 받았다. 오답 이유해답차집합으로 하는것보다는 그냥 visited 로 true/false 기록하는게 더 효율적이라고 한다.#기억할 문법 #set 활용 문법set.add(값) #값 추가set.remove(값) #값 제거 set.discard(값) #값 제거 (값이 없어도 에러 안남)set.union(set2) #합집합set.intersection(set2) #교집합set.difference(set2) #차집합set.isdisjoint(set2) #두 집합이 서로소인지 확인 (공통 원소가 없는지)set.issubset(set2) #부분집합인지 확인 (자신이 다른 집합의 ..
난이도: Lv.3유형: BFS/DFS해결 여부: 한번 틀리고 해결 아이디어BFS/DFS 형태로 다음 단어 탐색하면서 지워나간다.오답 이유 혹은 알게 된것아이디어 자체는 맞았으나 문법에서 한군데 틀려서 보고 고쳐야 했다.words = [i for i in words if i != temp] 라고 했다가 틀렸다. words=[i for i in words if i not in temp] 라고 해야 했다. temp 는 리스트니까 무조건 저렇게 해야했는데 아예 자료형이 다르니까 != 는 당연히 True뜨고 무한루프 걸려서 틀림여기서 시간 개선하려면 from collections import deque 한 후에 deque에다가 집어넣고 popleft() 쓰는게 더 시간이 빠르다고 한다. 그리고 set()이 Li..
난이도: Lv.2유형: BFS/DFS해결 여부: 통과아이디어경우의 수를 BFS 써서 풀어라 이거 같은데 나는 어 그냥 쌩으로 풀어버렸다. 복잡도는 차이가 없어서..?오답 이유 혹은 알게 된것처음에 빠른 방법 없나 DP나 부분합 고민해봤는데 그냥 모든 경우의 수 다하는 수밖에 없다고 생각했다.sort 후 rfind와 find 써서 최종 제출하려 했으나 문자열이 아닌 그냥 리스트에서는 find를 지원 안하는 것도 있고 아 걍 count쓰면 편하겠다 싶어서 count로 쉽게 풀어버렸다이 방식으로 한건 대충 case 크기 보았을떄 2^20 이면 대충 1000 * 1000 이니까 메모리 약 100만칸 . 파이썬 배열 한칸에 36byte로 약 40Mb. 만약 범위가 25개면 메모리초과 오류가 날 거라고 했다.그래서..
난이도: Lv.2유형: DFS/BFS해결 여부:오답아이디어2차원 배열에서 목적지까지 가는 최단거리 숫자 쓰는 간단한 문제오답 이유 혹은 알게 된것이전에 풀었떤 문제 응용하는 것과 비슷했다. 근데 일부분에서 걸려서 오래걸렸다.파이썬에는 NUll 대신 None을 쓴다는 점. 그리고 배열 값이 자동으로 0으로 초기화 된다는 점 때문에 초기화에 좀 걸렸다. 무엇보다 2차원 배열 하는과정에서 또 현기증 도져서 dx,dy 잘못더해서 찾는데 걸렸다. 만약에 성능을 높이고 싶으면 collections에서 deque 쓰는게 list에서 pop() 보다 deque popleft() 성능이 좋다고 한다. 여담으로 이런 코드로 통과받는 미친놈도 있었다. eq 로 object == ? 들어갈때 쓸 수 있는 코드같다. 파이썬 더..
