For Programmer

이 문제 정말 호락호락 하지 않았다. 여태까지 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씩 밀어주고 출력할때 빼준다..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX6PUEfaqAADFAS9 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제 상당히 어려워서 고민을 많이했다. 하루 정도 고민한 뒤에 힌트를 얻어서 풀었다. 자꾸 소인수 분해를 해서 해결할려고하였는데 약수를 구해서 해결할 수 있었다. 문제풀이 방식은 다음과 같다. 1. 문제에서 답은 입력받은 수를 오름차순 했을때 첫번째 아니면 두번째 수의 약수 중에 존재한다.(값을 교체해도 하나만 교체할 수 있기 때문에) + (최대 공약수는 가장 작은수의 크기를 넘을 수 없다.) ..