For Programmer

간단한 BFS 구현이다. Visited 리스트를 따로 만들어 해당 위치에서 도착지까지 얼마나 걸리는지 계속해서 확인해면서 가도록 구현했다. 단 DFS의 다양한 방법으로도 구현해 보았다. 모든 코드를 제시 하겠다. 1.BFS import sys from collections import deque sys.stdin = open('input.txt', 'r') def bfs(start): queue = deque([start]) visited = [[0] * N for _ in range(N)] visited[start[0]][start[1]] = 1 dr = [-1, 0, 1, 0] # 상우하좌 dc = [0, 1, 0, -1] # 상우하좌 while queue: r, c = queue.popleft() ..

이 문제 정말 호락호락 하지 않았다. 여태까지 1차원리스트나 N-Queen과 같은 2차원같은 1차원 dfs만 풀었는데 해당문제는 2차원 dfs를 구현해야 했다. 힌트는 2차원리스트를 1차원리스트처럼 쭉 펼쳐놓고 생각하는 것이었다. 또한 7명의 여학생이 붙어있는지 확인하기 위해 재귀 혹은 bfs를 이용하였는데 두가지 다 풀어보았다. 2가지 모두 코드를 제시하겠다. 1. dfs + bfs 이용 from collections import deque # bfs로 7명의 여학생이 붙어있는지 확인한다. def bfs(arr): dr = [-1, +1, 0, 0] # 상하좌우 dc = [0, 0, -1, +1] # 상하좌우 # 7명 여학생 위치 방문처리를 위한 리스트 1로 처리 visited = [[1] * 5 fo..

N-Queen은 dfs에서 너무나 유명한 문제이므로 풀이 과정은 생략하겠다. 단, 해당 문제 시간초과코드와 통과코드가 2개있다. 둘다 존재하는데 거의 비슷한 코드인데 시간초과나는 이유를 모르겠다. 아마 in연산자가 매번 반복문을돌면서 비교하는 연산보다 더 빠르게 수행되기 때문인거 같다. 2개의 코드 모두 올려놓겠다. 1. 통과코드 def checking(r, c): for j in range(len(check)): if abs(j - r) == abs(check[j] - c): return False return True def dfs(r): global count if r == N: count += 1 return for col in range(N): if col not in check: if chec..

이 문제 정말 킹받았다.. 구현하기도 힘들었고 백트래킹을 어떻게 잡아주어야 할지도 몰랐다. 약간의 힌트를 봤더니 중요한건 0의 위치를 튜플형식으로 저장한 후 0의 위치를 dfs를 도는 것이다. 그리고 0의 위치만큼 dfs를 돌아서 (물론 돌면서 백트래킹으로 행,열,3*3 스도쿠 조건을 검증해야함) 나오는 첫번째 스도쿠를 출력하면 된다. # 행검사 def row_check(r, c, num): for x in range(9): if c != x and num == sdoku[r][x]: return False return True def col_check(r, c, num): # 열검사 for x in range(9): if r != x and num == sdoku[x][c]: return False r..

이 문제는 알면 쉽고 모르면 한없이 어렵다. 사실 스택을 사용해야 한다는 생각을 바로 하기가 쉽지 않다. 문제의 풀이는 1. 우선 숫자는 바로 출력한다. 2. 숫자가아닌 연산자를 만나면 연산자를 스택에 담으면 된다. 3. 여기서 연산자를 스택에 어떻게 담을지를 생각해야 한다. 4. 연산자 우선순위를 +,- 는 0 *,/ 는 1 , '(' 는 -1 로 둔다. 5. 스택에 현재 연산자가 존재하지 않는다면 연산자를 한개 넣어준다. 6. 스택에 이미 연산자가 있고 맨위의 연산자가 지금 들어갈 연산자보다 우선순위가 높거나 같다면 스택에 있는 연산자들을 우선순위가 낮은게 남을때까지 빼고 출력한 후 마지막에 스택에 넣어준다. 7. 열린 괄호는 무조건 연산자에 넣어준다. 8. 닫힌 괄호를 만났다면 열린괄호와 닫힌괄호 ..

간단한 구현 문제이다. 파이썬의 리스트 내장 메서드 index만 잘 활용 한다면 쉽게 해결할 수 있다. N = int(input()) vote = list(int(input()) for _ in range(N)) result = 0 while True: # 만약 최댓값의 개수가 1이고 그 최댓값의 인덱스가 0이라면 탈출 if vote.count(max(vote)) == 1 and vote.index(max(vote)) == 0: break else: # 만약 최댓값의 개수가 2이상이라면 매수시작 vote[vote.index(max(vote), 1)] -= 1 # 2번째 수부터 끝까지 중에서 최댓값 중 -1 해준다. # (만약 index인자에 1을 안주면 최댓값이 다솜이를 포함해서 동일하게 10일 경우에 ..

간단한 dfs 문제이다. 단, 조합이므로 dfs의 약간 응용버전이라고 생각하면 된다. 2가지 방식으로 풀어봤다. 1. 템플릿 def dfs(depth, start): global result # 기저 if depth == len_: # 만약 깊이가 뽑을 개수와 같다면(len_개 만큼 뽑았다면) lemon = 1 # 신맛 bad = 0 # 쓴맛 for i in arr: # 뽑은 신맛 쓴맛을 계산한다. lemon *= i[0] # 신맛 값들을 곱해준다. bad += i[1] # 쓴맛 값들을 더해준다. if abs(bad - lemon) < result: # 만약 그 차가 저장된 값보다 적다면 result = abs(bad - lemon) # 그 차를 결과에 저장 return # 그 후 재귀 종료 # 재귀 f..

조금 귀찮은 구현이다. 특히 최빈값 구하는게 가장 귀찮다. 나는 계수정렬에서 사용하는 방식인 미리 count 리스트를 8000개 만들어 놓고 개수를 추가해서 최대 개수가 있는 인덱스를 찾는 방식으로 하였다. import sys # 입력 빠르게 받기 input = sys.stdin.readline N = int(input()) sum_ = 0 # 합계저장 middle = 0 count_list = [0] * 8001 mode = 0 arr = [] for i in range(N): temp = int(input()) # 전체합 sum_ += temp # 입력받은 값을 리스트에 추가 arr.append(temp) # 최빈값 구하기 위해 count 저장(음수도 저장하기 위해 4000씩 밀어주고 출력할때 빼준다..