Save my data

https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs로 풀었다. 다른 사람들의 풀이를 보니 대부분 bfs를 사용하였다. 기본 발상은 이러하다. 1. dfs 등의 탐색 알고리즘을 활용해서 각 석유 덩어리들의 크기를 먼저 구한다. 2. 해당 석유 덩어리가 걸치고 있는 수직 라인의 좌표를 기록한다. 3. 해당 좌표에서 시추할 수 있는 석유의 총량을 합한다. import sys sys.setrecursionlimit(1000000) vertical..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제만 대충 보면 어떻게든 구현할 수는 있는데 시간제한이 있고 해서 특정한 성능이 나오는 알고리즘을 적용해야 하는데, 알고리즘 분류 탭에도 설명되어 있듯 세그먼트 트리를 활용하라고 되어있다. 사실 이 문제는 예전에 알고리즘 특강을 들을 때 유튜브나 인강에서 대충 다루고 넘어갔던 기억이 있다. 위낙 DP, 그래프 위주로 출제가 되니까 그쪽으..

https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 예전에 풀었던 문제인데 그 때는 단순하게 풀었다. 두 행렬이라고 정해줬으니까 두 번에 나눠서 배열을 만들고, 각각의 원소를 돌면서 각 위치마다 더한 값을 출력하는 식으로 풀었음. import sys n, m = map(int, sys.stdin.readline().split()) a = [] b = [] for _ in range(n): a.append([*map(int, sys.s..

처음에는 아래와 같이 별 생각없이 풀긴 했다. N = int(input()) if N: for i in range(N - 1, 1, -1): N *= i N = str(N)[::-1] cnt = 0 for i in N: if not int(i): cnt += 1 else: break print(cnt) else: print(0) 다만 이것은 파이썬이라 풀리는 방법이고, 아마 다른 언어였으면 오버플로우가 발생해서 풀지 못했을 것이다. 다른 사람은 아래와 같이 풀었다. n = int(input()) def five_count(n): cnt = 0 while n != 0: n //= 5 cnt += n return cnt print(five_count(n)) 왜 5로 나눴을까? 에 대해서 생각하다보니 글이 조..

dfs 개념이 활용된 문제이다. 처음에는 아래와 같이 깊이를 의미하는 d를 추가를 안했다. 그런데 아래와 같이 하면 idx를 층으로 쓴다는 얘기인데 그렇게 되면 '층'을 의미하는 원소와, '값(크기)'을 의미하는 원소간 의미 구분이 안된다. import sys def ans(idx): if idx >= 7: print(*res) return 0 for i in range(idx, t[0] + 1): res.append(t[i]) ans(i + 1) res.pop() while 1: t = [*map(int, sys.stdin.readline().split())] res = [] if t[0]: ans(1) else: break 그래서 '값(크기)'이 커져버리면 현재 '층' 수가 높은 것으로 착각되면서 탐..

프로그래머스 문제는 정말 오랜만에 푼다. 적응의 문제인지 어떤지 확실하지는 않지만 시간이 좀 걸렸다. 다시 보니 어려운 문제인 것 같지는 않는데 당분간 문제를 많이 풀면서 지켜봐야겠다. def solution(wallpaper): x = len(wallpaper) y = len(wallpaper[0]) lx = x - 1 ly = y - 1 rx = 0 ry = 0 for i in range(x): if "#" in wallpaper[i]: lx = min(lx, i) rx = max(rx, i + 1) for i in range(x): for j in range(y): if wallpaper[i][j] == '#': ly = min(ly, j) ry = max(ry, j + 1) answer = [lx..

너무 쉬운 문제인데 생각이 마치 어딘가 막힌 것 처럼 한 30분 넘게 붙잡고 있었던 것 같다. import sys N, M = map(int, sys.stdin.readline().split()) pokemon_name = {} pokemon_num = {} for i in range(1, N + 1): name = sys.stdin.readline().strip() pokemon_name[name] = str(i) pokemon_num[str(i)] = name for _ in range(M): q = sys.stdin.readline().strip() if q in pokemon_name: print(pokemon_name[q]) else: print(pokemon_num[q]) 딕셔너리를 두 개 만..

요구하는 대로만 구현하면 답인 구현 문제였다. import sys def gen(n, arr): if sum(arr) == n: print(f"{n} =", " + ".join(map(str, arr))) else: print(f"{n} is NOT perfect.") while 1: factors = [] N = int(sys.stdin.readline()) if N == -1: break for i in range(1, (N // 2) + 1): if not N % i: factors.append(i) gen(N, factors) 며칠동안 쉬운 문제만 풀면서 포스팅 했는데 다음주부터는 다시 그래프 문제를 풀어야겠다. 사실 백준 14502 연구소 문제에서 막혀서 구글링했는데, 보니까 백트래킹이라는 기법..