profile
반갑습니다! 알고리즘 문제 풀이 정리 블로그 입니다. 피드백은 언제나 환영입니다!

[백준] 1520번 내리막길 (파이썬)

난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/1520 문제해결 아이디어 단순 dfs만으로는 시간초과가 난다.=> dp를 활용해서 시간복잡도를 줄여야 함. 목표지점 n-1, m-1에 도달하면 시작점에서 도착점까지 성공적으로 방문한 한 가지 경우가 되므로 1을 리턴해주고, 해당 값을 지금까지 걸어온 경로에 모두 더해준다. 만약에 현재 방문중인 경로를 이미 다른 경로가 방문하여 -1이 아닌 다른 값으로 업데이트 되어있다면 (0 or n으로) 더 이상의 탐색은 진행하지 않고 해당 값을 업데이트 해준다.

2023년 4월 24일
·
0개의 댓글
·

[백준] 1937번 욕심쟁이 판다 (파이썬)

난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/1937 문제해결 아이디어 상, 하, 좌, 우로 이동해서 최대 일수를 구한다는 것에서 dfs를 바로 떠올릴 수 있었다. 경로를 반복해서 이동하는 문제를 줄이기 위해 dp를 사용하였다. dfs와 dp를 사용하는 것이 핵심인듯 하다. 소스코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] dp = [[0] * n for _ in range(n)] def dfs(x, y): if dp

2023년 4월 24일
·
0개의 댓글
·

[백준] 16637번 괄호추가하기 (파이썬)

난이도 : GOLD III > 문제링크 : https://www.acmicpc.net/problem/16637 문제해결 아이디어 리턴 조건은 인덱스가 마지막에 도착할때 까지이다. 인덱스와 인덱스 까지의 계산결과를 들고 다닌다면서 dfs 순회한다. 계산 방법은 현재 인덱스(숫자), 현재인덱스+1(기호), +현재인덱스+2 를 계산하는 경우와 현재 인덱스(숫자), 현재인덱스+1(기호), (현재인덱스+2 현재인덱스+3(기호) 현재인덱스+4) 경우이다. 소스코드

2023년 4월 24일
·
0개의 댓글
·

[프로그래머스] 양과 늑대 (파이썬)

난이도 : LV 3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92343 문제해결 아이디어 문제푸는 방법을 모르겠어서 다른사람의 풀이를 참고했다. 생각보다 코드가 간단해서 놀랬는데 핵심은 부모노드를 방문했지만 아직 방문하지 않은 자식노드들을 탐색하는것 이였다. 소스코드

2023년 4월 14일
·
0개의 댓글
·

[프로그래머스] 모두 0으로 만들기 (파이썬)

난이도 : LV 3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76503 문제해결 아이디어 0으로 만들수 없는 경우는 -1 을 리턴해야한다. sum(a) != 0 이면 -1 리턴 DFS를 이용해서 정점을 탐색하는데, 제일 끝 정점(연결된 방문하지 않은 정점이 없는 경우)부터 0으로 만든다. 0으로 만들어준다는 것은 결국 자신을 dfs로 호출한 부모 정점에 자신의 가중치를 더하는 것과 같다. 현재 정점을 0으로 만들기 위한 연산의 횟수는 정점의 가중치의 절대값. 소스코드

2023년 4월 12일
·
0개의 댓글
·

[프로그래머스] 퍼즐조각 채우기 (파이썬)

난이도 : LV3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84021 문제해결 game_board 를 순회하면서 빈공간이 있을 경우 (0,0)기준으로 빈공간 모양의 좌표를 blank 라는 리스트에 받는다. table 을 4방향으로 회전시키면서 테이블을 순회하고 순회하면서 발견된 각각의 도형들을 (0,0)을 기준으로 도형모양의 좌표를 받는다. 만약 도형의 좌표가 blank 안에 있다면 도형의 크기 만큼 정답에 더한다. (blank 안의 도형은 삭제) 소스코드

2023년 3월 30일
·
0개의 댓글
·

[프로그래머스] 미로탈출명령어 (파이썬)

난이도 : LV3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365 문제해결 일단 가독성을 높이기 위해 각각의 좌표를 -1씩 더했다. direction 리스트의 순서를 사전순 ['d', 'l', 'r', 'u'] 으로 나타냈다. dfs 탐색시 가장 빠르게 정답을 발견할수 있도록 dfs 의 리턴조건은 다음과 같다. 완성된 문자열의 길이가 조건과 같은 경우 아직 완성되지는 않았지만 현재까지 가장 작은문자열보다 큰 경우 (파이썬은 문자를 아스키 코드를 통한 크기 비교가 가능하다) 목표지점 까지의 최단거리가 남은 이동가능 횟수보다 큰 경우 목표지점 까지의 최단거리와 남은 이동가능 횟수의 2로 나눈 나머지가 다른경우 (각각 짝수와 홀수로 다르면 목표지점까지 횟수를 다사용해서 이동 불가) 소스코드 여담 아무리봐도 맞는것 같은데 자꾸

2023년 3월 30일
·
0개의 댓글
·

[프로그래머스] 양궁대회 (파이썬)

난이도 : LV2 > 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92342 문제해결 매 점수 마다 라이언은 0발을 쏴서 점수를 포기하거나 어피치보다 한발 더 많이 쏴서 최소의 화살 개수로 점수를 획득해야한다. DFS를 사용해서 10점부터 0점까지 점수를 획득, 포기 했을 경우 전체 탐색. 이때 만약 화살이 남았을 시, 남은 화살은 전부 0점에 털어야한다. 정답이 여러개일 경우, 낮은 점수를 많이 쏜 과녁을 리턴해야 하는데, 과녁 배열을 문자열로 합치고 뒤집은 다음 숫자화 하여 가장 큰수가 되면 된다. 소스코드 ans = [] maxVal = 0 def getScore(board,info): apsc = lisc = 0 for i in range(len(info)): if board[i] > info[i]:

2023년 3월 27일
·
0개의 댓글
·