본문 바로가기

코딩 테스트

 (4)
백준 15649: N과 M (1) 재귀 함수에 백트래킹을 섞어서 풀어본 수열 출력 문제import sysinput = sys.stdin.readlinen, m = map(int, input().split())checked = [False] * (n + 1)result = []def recur(depth): # Stop if depth == m: print(*result) return # Main for i in range(1, n + 1): if not checked[i]: # Tracking checked[i] = True result.append(i) # Recursio..
백준 1926: 그림 아이디어그래프 탐색인접한 모든 부분들을 탐색하는 문제이므로 BFS 또는 DFS.BFS, DFS 모두 다음과 같은 과정시작노드 방문 체크, 시작노드 큐 또는 스택에 삽입이후 큐 또는 스택이 빌때까지 while문 반복(1) 가공: 노드를 꺼내서 현재 노드로 정의하고 결과에 저장(2) 체크 및 삽입: 현재 노드의 이웃을 for 루프로 탐색하고, 체크 되지 않은 이웃 체크 후 삽입노드와 이웃의 표현이 문제에서 노드는 1, 2, 3 처럼 숫자 하나로 표현되지 않음.대신 행, 열 좌표로 표현.current_node 대신 current_row, current_colstart_node 대신 start_row, start_col이웃이란, 현재 노드에서 상하좌우 1칸을 움직여 도달할 수 있으며 값이 1인 것.neighbo..
백준 11047: 동전 0 아이디어그리디가 최적해 보장큰 단위의 동전은 항상 작은 단위의 동전으로 표현할 수 있으므로 그리디 알고리즘이 최적해 보장!큰 단위의 동전부터 for 루프coins.reverse()로 큰 단위 부터 루프나눗셈동전으로 금액을 나누어 얻은 몪만큼 동전 개수 카운트 증가.동전으로 금액을 나누어 얻은 나머지가 새로운 금액이 됨.탈출새로운 금액이 0이 될 때 이미 답은 나왔지만 for 루프를 계속 돌게 됨.탈출 조건을 주고 최적화 가능 (둘다 O(n)이므로 성능 차이는 미미하다).시간 복잡도coins를 정렬하는데 O(n) (처음부터 내림차순 정렬이 아니라 오름차순을 단순 재배열하므로)for 루프에서 O(n).k와는 관계 없음.최종적으로 O(n)이고 최악의 경우 10이므로 충분히 가능.코드 구현import sysin..
백준 14503: 로봇 청소기 아이디어2차원 리스트로 청소 공간 표현: space[row][col]0: 청소 안된 빈 칸, 1: 벽. 추가로 2: 청소 된 칸 체크용도방향 벡터로 이동을 표현drow = [-1, 0, 1, 0], dcol = [0, 1, 0 -1]북, 동, 남, 서 순으로 정함. 이렇게 하면 drow[d] = 전진, -drow[d] = 후진으로 표현 가능!나머지 연산으로 회전을 표현90도 시계 방향 회전: 0 → 1 → 2 → 3 → 1 → 2 → …90도 반시계 방향 회전: 0 → 3 → 2 → 1 → 0 → 3 → …-1 mod 4 = 3이므로 d = (d - 1) % 4로 구현 가능!while 문으로 반복: 작동 멈출 때까지 계속 반복한다.for문으로 4방향 탐색, 0을 찾았으면 for 문 탈출찾았으면 for문 ..

티스토리툴바