본문 바로가기

알고리즘

[Programmers / Java] 멀쩡한 사각형
알고리즘/Programmers 2022. 5. 7. [Programmers / Java] 멀쩡한 사각형 문제링크 코드 class Solution { public long solution(int w, int h) { long gcd_result = gcd(w,h); long w1 = Long.parseLong(String.valueOf(w)); long h1 = Long.parseLong(String.valueOf(h)); long patton = (w1 + h1) - gcd_result; long answer = (w1 * h1) - (patton); return answer; } public long gcd (long a, long b){ if((a % b) == 0) return b; return gcd(b,(a%b)); } } 이 문제를 풀면서 3시간정도 고민하고 다른 사람의 풀이를 참조해서 풀었습니..
알고리즘/Programmers 2022. 3. 4. [Programmers / Python] 메뉴 리뉴얼 문제 이해 다른 사람의 풀이를 보고 이해했습니다. 처음에 2의 대한 조합만 생각했습니다. 하나의 order에 대해서만 생각하는게 아니라 order들 전체의 조합의 수를 만들어야 합니다. 코드 from itertools import combinations def solution(orders, course): answer = [] for i in course: dict = {} jo = [] for order in orders: jo.extend(list(combinations(sorted(order), i))) for i in jo: str = ''.join(i) if(str in dict): # 조합 안에 같은 글자가 있다면 dict[str] += 1 else: dict[str] = 1 for order..
알고리즘/Programmers 2022. 3. 3. [Programmers / Python] 괄호변환 문제이해 이건 국어문제 같습니다. 이해가 너무 어려웠어요 제귀로 푸는 문제라서 코드를 보면서 이해하는게 좋을거 같습니다. 코드 먼저 check 함수는 문자열을 받아서 그 문자열이 올바른 괄호 문자열인지 확인합니다. def check(str): li =[] for i in str: if(i == '('): li.append(i) else: if(len(li) == 0): return False li.pop() if(len(li) == 0): return True else: return False 스택을 이용했습니다. '('는 넣고 ')'가 들어오면 스택(li)는 비게됩니다. 모두다 비면 True를 반환합니다. def solution(p): answer = '' left = 0 right = 0 u = ""..
[Programmers / Python] 순위검색
알고리즘/Programmers 2022. 3. 2. [Programmers / Python] 순위검색 문제이해 query를 따로 때서 info를 하나씩 돌면서 처음에는 점수를 확인하고 다음에는 '-' 표시를 확인하고 다음에는 같은 문자가 있는지 확인하면서 만약에 모든 과정을 통과하면 그 query의 성공+1 을 하는 방식을 생각했습니다.(다른사람의 풀이를 보고 알았습니다.) 하지만 이 코드는 효용성 테스트에서는 틀립니다. 모든 info를 도는것이 시간을 잡아먹는거 같습니다. 코드 def solution(info, query): answer = [] for q in query: q = (q.replace('and','').split()) # ['cpp', 'backend', 'senior', 'pizza', '260'] print(q) count = 0 for i in info: # java backend..
알고리즘/Programmers 2022. 2. 26. [Programmers / Python] 비밀지도 문제이해 2개의 지도를 2진수로 만든다. n자리를 채워야하니 빈자리에 0을 넣어준다. 각 수를 돌면서 2개가 동시에 0인 경우만 ' '(공백)을 넣어준다. 아니면 #을 넣어준다. 코드 def solution(n, arr1, arr2): gido1 = [ int(bin(arr1[i])[2:]) for i in range(n)] gido2 = [ int(bin(arr2[i])[2:]) for i in range(n)] answer = [] for j in range(n): result = '' a = (str(gido1[j]).zfill(n)) b = (str(gido2[j]).zfill(n)) for k in range(n): if(a[k] == '0' and b[k] == '0'): result += '..
[백준 알고리즘/Python] 2178 미로 탐색
알고리즘/백준알고리즘 2022. 2. 24. [백준 알고리즘/Python] 2178 미로 탐색 문제 문제 이해 처음에 dfs로 풀려다가 뭔가 이상한거 같아서 더 좋은 방법이 있겠다 생각했습니다. 가까이 있던 bfs를 생각해보았습니다. bfs로 에서 부터 1칸씩 쭉쭉 이동할 때 마다 count를 1씩 늘려주면 됩니다. 그렇다면 1번 씩 이동할 때 마다 count를 1개씩 늘려줘야 하니 queue 안에 다음 좌표값과 이동해온 크기를 집어넣습니다. 큐에 넣을때마다 크기를 증가시키는게 아니라 한 사이클마다 크기를 증가시켜줘야 합니다. 여기서 사이클은 어떤 좌표에 있을 때 주변에 1이 있다면 그곳으로 가야할 것입니다. ex) 라는 좌표가 있습니다. 까지 오는데 3번 걸린 것입니다. 만약 으로 가야한다면 를 큐에 집어넣으면 됩니다. 만약에 에도 1이 있습니다. 그러면 를 큐에 집어넣습니다. 이런식으로 큐에 ..
[백준 알고리즘/Python] 2667 단지번호 붙이기
알고리즘/백준알고리즘 2022. 2. 23. [백준 알고리즘/Python] 2667 단지번호 붙이기 문제 문제 이해 dfs로 하나의 좌표가 1이라면 다른 1을 찾아서 쭉쭉 스택을 쌓는 형식으로 풀면 됩니다. 이번에는 dfs가 스택이 쌓일 때의 수와 1개의 사이클이 끝날 때를 고려했습니다. import sys sys.setrecursionlimit(10**6) c = [] # dfs 한 사이클 돌 때 나오는 수 r = [] # 나오는 수를 오름차 순으로 def dfs(x,y,count): #주어진 범위를 벗어나면 종료 if(x = n or y = n): return False if(graph[x][y] == 0): return False #현재 노드와 연결된 다른 노드를 재귀적으로 방문 if(graph[x][y] == 1): graph[x][y] = 0 count += 1 #하나의 사이클의 호출 횟수 d..
[백준 알고리즘/Python] 4963 섬의 개수
알고리즘/백준알고리즘 2022. 2. 22. [백준 알고리즘/Python] 4963 섬의 개수 문제 문제 이해 2차원 배열에서 상하좌우, 대각선을 고려해서 1이면 다른 1을 찾을 수 있게끔 합니다. 1을 찾는다면 0으로 만들어서 다시 검색이 안되도록 만듭니다. 코드 import sys sys.setrecursionlimit(10**6) def dfs(x,y): #주어진 범위를 벗어나면 종료 if(x = h or y = w): return False if(graph[x][y] == 0): return False #현재 노드와 연결된 다른 노드를 재귀적으로 방문 if(graph[x][y] == 1): graph[x][y] = 0 dfs(x-1,y-1) #왼쪽 위 대각선 dfs(x-1,y) # 상 dfs(x-1,y+1) #오른쪽 위 대각선 dfs(x,y-1) #왼쪽 dfs(x,y+1) #오른쪽 dfs(..
[백준 알고리즘/Python] 11724 연결 요소의 개수
알고리즘/백준알고리즘 2022. 2. 21. [백준 알고리즘/Python] 11724 연결 요소의 개수 문제 문제 이해 dfs를 돌면서 쭉 깊이 들어가면 그 한번의 사이클이 연결 요소 입니다. python의 제귀 제한이 걸려 있어서 sys.setrecursionlimit(10000) 해야 런타임 에러를 해결할 수 있습니다. 그리고 input()으로 입력을 받으면 시간초과가 나기 때문에 sys.stdin.readline을 써서 입력을 받아줍시다. 코드 import sys sys.setrecursionlimit(10000) input = sys.stdin.readline #DFS 메서드 정의 def dfs(v): #현재 노드를 방문 처리 visited[v] = True #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(i) N, M =..

티스토리툴바