Dalin's Archive

와아아아~~ 엄청 오랜만에 문제를 풀었다 !!!! 문제 보러가기 풀이 😍 떡 종류는 1-9번! N일 동안 떡 팔러 가는데, 그날 파는 떡의 종류들은 매일 달라진다. 전날의 떡과 오늘의 떡은 꼭 달라야 한다. 떡을 줄 방법이 있으면, 매일 호랑이한테 줄 떡을 순서대로 출력한다. 떡을 줄 방법이 없으면, -1을 출력한다. 처음에는 백 트래킹을 생각했다. 호랑이한테 줄 수 있는 떡의 경우들로 가지를 뻗어보다가, 처음으로 정답까지(N일 동안 호랑이한테 다른 떡 주는 경우) 가면 그만 탐색하면 되겠다고 생각했다 !! 또 N이 최대 1000이니까 그 정도면 dfs 를 돌릴 수 있다고 생각했다! dfs 함수를 만들고 그 인자로 며칠인지(day), 그 동안 호랑이한테 준 떡들(history)을 넘겼다. 매일 호랑이한테..

백준으로 문제 보러 가기~ 인트로(TMI) 저번 주부터 회사에 다니기 시작했다! 나는 주로 React를 다뤘는데, 회사에서는 Vue를 사용한다.. 그래서 Vue 공부를 하느라고 문제를 별로 못 풀었다 ㅠㅠㅠ 그러다 푸니까 넘 재밌었다!!!! 쉬운 줄 알았는데 시간 초과가 많이 나서 신경을 썼다...재밌는 DFS문제였다!! 풀이 세로 R칸, 가로 C칸 표 모양의 보드에 대문자 알파벳이 써있다. 좌측 상단에서 시작해서, 상하좌우 4칸 중 한 칸으로 갈 수 있다. 매번 다른 알파벳을 지나면서, 가장 많이 이동하는 칸 수를 구하는 문제였다!! 이동하는 모든 경우를 고려해야 하고 R, C 가 20 이하여서.. DFS로 풀 수 있을 거라고 생각했다. 처음에는 방문했던 알파벳인지 체크하는 것을 set으로 했는데, 시..

문제 보러 가기! 간단 소감 오랜만에 dfs 문제를 풀어서 재밌었다 ㅎㅎ 그리고 visited 아이디어를 생각하는 것도 특이하고 재밌었다~~ 문제 설명 로봇이 4방향(동서남북) 중 한 방향으로 N번 이동한다. 각 방향으로 이동할 확률을 준다. 같은 곳을 또 방문하면 이동 경로가 단순하지 않다고 한다. 로봇의 이동 경로가 단순할 확률을 구하는 문제였다. 풀이 로봇이 4방향으로 N번 이동하고, N이 14보다 작다고 해서 딱 순열! 이 생각났다. DFS로 각 방향을 가봤다. dfs를 할 때 가지고 다니는 변수는 지금까지 몇 번 이동했는지, 현재 인덱스, 현재 위치까지 이동할 확률. 그런데 로봇이 단순하지 않은 경로로 이동할 경우, 더이상 볼 필요 없이 리턴해주면 되니까 백트래킹이라고도 할 수 있겠다. visi..

문제 보러 가기! 가지치기 없이 그냥 DFS로 풀었다~ N의 범위가 작아서, 그냥 해도 되는 것 같다! 시간 복잡도는 3^9 * 10 인데, 계산하면 196,830. 1초 내에 충분히 계산될 수 있다. DFS로 하고 DFS에 history와 idx를 만들었다. idx는 1부터 N까지 어떤 숫자를 볼 차례인지 담당한다. idx가 N+1이 되면 숫자를 다 본 것이다. 이때 수식의 결과가 0이 되는지 체크하면 된다! idx가 N+1 미만일 때는, 매번 +, -, 공백(숫자 이어지는 것) 의 경우로 재귀를 돈다. 헷갈렸던 부분! 바로 바로 idx가 N+1될 때 출력하면 안되어서(ASCII 순서에 따라서 출력하라고 함), 되는 경우를 리스트에 넣었다가 정렬한 후에 출력했다. ㅠㅠㅠ 계속 '출력 형식이 잘못되었습니..

[문제 보러 가기!](https://www.acmicpc.net/problem/17265 DFS로 풀었다. DFS에서 좌표, 그때까지 계산한 값, 연산자(그 직전이 연산자인 경우만)를 들고 다닌다. 학교에 도착하면(i==N-1 and j==N-1), 가능하다면 정답을 업데이트해준다. 아래, 오른쪽으로만 가라고 했으니까 그렇게 진행한다. 숫자일 때는 그 전의 연산자를 활용해서 계산해줬고, 연산자일 때는 숫자는 그대로 두고 그 연산자를 가지고 다음으로 넘겨주었다. 한 번 틀렸습니다.를 만났는데, 그 이유는 max_answer을 -1로 세팅하고 시작했기 때문이었다.. 처음에 0을 만나고 계속 -, 5, -, 5, -, 5, ... 이런 식으로 진행될 수도 있으니까 -1로 세팅하면 안되는 것이었다. 최대값을 구..

문제로 가기! 처음에는 윗칸의 수를 고르고 그 아래 칸의 수를 보고, 각자 set에 넣어서 두 set이 같은지 다른지 판단해주고.. 같으면 또 다른 (윗칸) 수를 골라보고... 다르면 그 아래칸의 수를 윗칸 수로 하는 수를 찾고... 그런 식으로 생각을 해서 코드를 짜긴 했는데, 틀렸다. 질문 검색에서 다른 분들이 주신 반례를 보고, 그림을 그려보니까 문제가 좀 더 잘 이해되었다. 방향이 있는 그래프(윗 칸 -> 아랫 칸)로 보고, 인접 리스트로 입력을 받았다. DFS로 탐색을 하면서 사이클이 발생한 것을 다 더하면 되는 문제였다. 나는 set을 활용해서 윗 칸의 수들의 집합, 아랫 칸의 수들의 집합이 일치하는지 보았다. 만약 일치하면 일치하는 집합을(윗 칸 수들의 집합이든 아랫 칸 수들의 집합이든 같으..

문제 보러 가기! DFS로 풀었다. 그대로 직진하거나, 방향을 바꾸거나!! 이때 시계방향이든 반시계방향이든 한 방향으로 돌아봐야 한다~ 대각선 방향으로 가야 하고, 두 개(카페, 디저트)의 방문 체크를 고려하는 게 특이했다~ # 대각선 방향 directions = [(1, 1), (1, -1), (-1, -1), (-1, 1)] def dfs(i, j, direction_type, dessert_cnt): global ans # 직진 or 꺾기 if direction_type < 3: tmp = direction_type + 2 else: tmp = direction_type + 1 for k in range(direction_type, tmp): ni = i + directions[k][0] nj = ..

문제 보러 가기 접근 일단 인접한 노드들을 저장해주었다. 어디가 부모인지, 어디가 자식인지 모르니까 일단은 방향 없이 모두~ 그리고 루트를 1로 삼고 거기에서부터 쭉~ 자식을 보러 갔다. 부모를 저장하는 리스트를 만들어서 부모 노드가 몇번 노드인지 저장해줬다. 인접한 노드들을 쭉~ 보되 이미 방문 체크가 되었다면 보지 않았다. 이미 방문 체크가 되었다면, 자식이 아니라 부모라는 뜻이니까.. 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 5) N = int(input()) adj = [[] for _ in range(N + 1)] for _ in range(N - 1): a, b = map(int, input().split()) ..

백준 2667번 문제 보기~ 📌 포인트 DFS로 풀었다! 🤨 헷갈렸던 부분 입력이 &#39;0110100&#39;이런 식으로 띄어쓰기 없이 들어옴. split하면 안됨! 처음에 split해서 계속 에러가 나왔다.ㅠ 👩‍💻 코드와 설명 dx=[-1,0,1,0] dy=[0,1,0,-1] def DFS(x,y): global cnt for i in range(4): #상하좌우를 체크! xx=x+dx[i] yy=y+dy[i] if 0

백준 1012번 문제 보러가기~~ 📌 포인트 DFS로 풀었다!! 방금 푼 단지번호 붙이기 문제와 비슷한 것 같다. 백준 단지번호 붙이기 문제 보러가기 내 풀이 보러가기 😅 위기 잘 풀었다고 생각했는데 &#39;런타임 에러 (RecursionError)&#39;가 나왔다. DFS로 풀었는데 다음에는 BFS로 생각해봐야지~ 백준 안내에 있는 대로 import sys sys.setrecursionlimit(10**6)를 추가해서 파이썬 최대 재귀 깊이를 크게 설정하니 성공했다. 👩‍💻 코드와 설명 import sys sys.setrecursionlimit(10**6) # 최대 재귀 깊이 설정 dx=[-1,0,1,0] dy=[0,1,0,-1] def DFS(x,y): for p in range(4): #상하좌우..