티스토리

개발하는 악몽
검색하기

블로그 홈

개발하는 악몽

akmong.tistory.com/m

아크몽 님의 블로그입니다.

구독자
0
방명록 방문하기
공지 블로그 주인에 대해서 모두보기

주요 글 목록

  • 백준 1931 회의실 배정 Python 그리디 실버 1 틀렸던 이유 1. while True문으로 한 칸씩 더해나가면서 해결하려 했음 => 시간 오류로 20% 2. sort를 끝나는 시간만 하는게 아닌 시작하는 시간에도 적용해야함: 85% 오류 반례 모음 https://www.acmicpc.net/board/view/122182 import sys input = sys.stdin.readline # 1931 회의실 배정 실버 1 n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int,input().split()))) arr.sort(key=lambda x : (x[1], x[0])) # arr.sort(key=lambda x : x[1]) print(arr) cnt = 0 prevEnd = .. 공감수 0 댓글수 0 2024. 4. 4.
  • 백준 4964 섬의 개수 Python BFS 실버 2 # 4964 섬의 개수 실버 2 import sys from collections import deque input = sys.stdin.readline di = [0,0,1,-1,-1,1,-1,1] dj = [1,-1,0,0,1,1,-1,-1] while True: w, h = map(int, input().split()) if w == 0 and h == 0: break maps = [list(map(int,input().split())) for _ in range(h)] visited = [[0] * (w+1) for _ in range(h)] cnt = 0 # for p in maps: # print(p) def bfs(): global cnt for i in range(h): for j in r.. 공감수 0 댓글수 0 2024. 4. 4.
  • 백준 7569 토마토 Python 그래프 BFS 골드 5 첫 골드 5 문제 3차원 + 6방향 탐색 기본 BFS 풀이를 조금 어렵게 응용만 문제같다. 풀이시간 : 1시간 정도 한번에 통과함 import sys from collections import deque sys.stdin =open('input.txt') # 7569 토마토 골드 5 from collections import deque dy = [1,-1,0,0,0,0] dx = [0,0,1,-1,0,0] dz = [0,0,0,0,1,-1] def bfs(): global flag deq = deque() for k in range(h): for i in range(n): for j in range(m): if arr[k][i][j] == 1 and visited[k][i][j] == -1: # 익은 토.. 공감수 0 댓글수 0 2024. 3. 31.
  • 백준 1991 트리 순회 Python 트리 DFS 실버 1 # 1991 트리 순회 실버 1 n = int(input()) dicts = {} for i in range(n): node, p_l, p_r = map(str,input().split()) dicts[node] =[p_l,p_r] # print(dicts) visited = [0] * (n+1) def preorder(v): if v == '.':return print(v,end='') preorder(dicts.get(v)[0]) preorder(dicts.get(v)[1]) preorder('A') print() def inorder(v): if v == '.':return inorder(dicts.get(v)[0]) print(v,end='') inorder(dicts.get(v)[1]) inor.. 공감수 0 댓글수 0 2024. 3. 31.
  • 백준 2606 바이러스 Python BFS 실버3 BFS 기본적인 문제인듯 하다. # 2606 바이러스 실버3 from collections import deque computer = int(input()) network = int(input()) adjl = [[] for _ in range(computer+1)] for _ in range(network): s,e = map(int,input().split()) adjl[s].append(e) adjl[e].append(s) def bfs(v): deq = deque() deq.append(v) visited = [0] * (computer + 1) visited[v] = 1 cnt = 0 while deq: value = deq.popleft() for i in range(1,computer+1):.. 공감수 0 댓글수 0 2024. 3. 31.
  • 백준 5014 스타트링크 Python BFS 실버 1 가고 안가고를 통해 결정된다고 생각 -> 부분집합문제인가? -> DFS로 해보자 하지만 예외처리를 하기 어렵다 -> BFS로 전환 BFS에서 어떻게 부분집합을 결정할 수 있을까 고민 for _ in "Iterable" 을 쓸 생각을 할 수 있냐 없냐가 이 문제의 해결 요소라고 생각한다. 평소에 range()랑 같이 쓰면서 해당 사용법에 대해서 생각치 못한게 이 문제를 자력으로 해결못했었던 요소라고 생각한다. # 5014 스타트링크 실버 1 from collections import deque f,s,g,u,d = map(int,input().split()) # 10층 건물로 이루어졌고 현재 1층이고 회사는 10층 한번에 2층 올라가고 1층 내려온다 # print(f,s,g,u,d) flag = 0 vis.. 공감수 0 댓글수 2 2024. 3. 31.
  • 백준 1193 분수 찾기 Python 수학 실버 5 1/1 1/2 2/1 3/1 2/2 1/3 1/4 2/3 3/2 4/1 이런식으로 진행됨을 알았음 홀수줄은 -1/+1 짝수 줄은 +1/-1 이 되기 때문에 몇번째 줄인지 구하고 , 차이만큼 더 가면 해결가능했다. # 1193 분수 찾기 실버5 num = int(input()) line = 1 while num > line: num -= line line += 1 if line %2: # 라인이 홀수 라면 a = line -num + 1 b = num else: a = num b = line -num + 1 print(f'{a}/{b}') 공감수 0 댓글수 0 2024. 3. 29.
  • 백준 1920 수 찾기 Python 이진탐색 실버 4 파이썬은 in 이 있어서 만약 썼다면 set으로 바꿔서 중복값을 없앤 후 찾았다면 실행시간이 조금 더 빨랐을 것같다. # 수 찾기 실버 4 1920 def find_num(v): s = 0 e = n if v arr[e-1]: return 0 while s 공감수 0 댓글수 0 2024. 3. 29.
  • 백준 1260 DFS 와 BFS Python 실버 2 틀린 코드 5% 1. 인접리스트를 만들었었음 = 오름차순 정리를 위해 반복문 + 리스트를 반복해서 사용함 => 시간낭비 => 인접행렬로 변경해서 해결 2. 예제 케이스는 다 맞았었음 하지만 dfs코드가 불안정했음 => 바꿨음에도 문제 발생 def dfs(v): visited_d[v] = 1 path.append(v) for i in adjl[v]: if visited_d[i]: continue dfs(i) # 1260 DFS 와 BFS 실버2 from collections import deque def dfs(v): if len(path) == m+1: return for i in adjl[v]: if visited_d[i]: continue visited_d[i] = 1 path.append(i) df.. 공감수 0 댓글수 0 2024. 3. 28.
  • 백준 15657 N과 M (8) Python 백트래킹 실버 3 조건 : 1. 중복 가능 2. 오름차순 # 15657 N 과 M (8) # 중복 순열, 오름차순 def perm(x): if len(path) == m: print(*path) return for i in range(x,n): path.append(arr[i]) perm(i) path.pop() n,m = map(int,input().split()) arr = list(map(int,input().split())) arr.sort() path = [] perm(0) 공감수 0 댓글수 1 2024. 3. 27.
  • 백준 1009 분산처리 Python 브론즈2 import sys # 1009 분산처리 브2 t = int(sys.stdin.readline()) for _ in range(t): a,b = map(int,sys.stdin.readline().split()) n = pow(a, b) % 10 a = a % 10 if a == 0: print(10) elif a == 1 or a== 5 or a == 6: print(a) elif a == 4 or a == 9: b %= 2 if b == 1: print(a) else: print(a**2 % 10) else: # 2,3,7,8 b %= 4 if b ==0: print(a ** 4 % 10) else: print(a ** (b%4) % 10) 공감수 0 댓글수 0 2024. 3. 27.
  • 백준 1966 프린터 큐 Python 자료 구조 큐 실버 3 큐의 자료구조형에 대한 이해 + 문제 풀이 방법 큐의 자료구조형에 대해서는 이해했으나, 문제풀이에 어려움이 있었음 16퍼 짜리 오답 # 1966 프린터 큐 실버3 from collections import deque t = int(input()) for _ in range(t): n,m = map(int,input().split()) prioritys = list(map(int,input().split())) priority = deque() for i in range(len(prioritys)): priority.append((i,prioritys[i])) want = priority[m] cnt = 1 while priority: if max(priority, key=lambda x:x[1]) > p.. 공감수 0 댓글수 1 2024. 3. 27.
  • 백준 18115 카드 놓기 Python 자료구조 덱 실버 3 덱을 사용하는 문제 간단한 문제였지만, 문제를 읽고 이해 하지 못해서 오래 걸렸다 # 18115 카드 놓기 실버3 from collections import deque n = int(input()) skill = list(map(int,input().split())) skill.reverse() new_arr = deque() for i in range(1,n+1): if skill[i-1] ==1: new_arr.appendleft(i) elif skill[i-1] ==2: new_arr.insert(1,i) elif skill[i-1] ==3: new_arr.append(i) print(*new_arr) 공감수 0 댓글수 0 2024. 3. 26.
  • 백준 9012 괄호 Python 스택 실버4 더보기 정답코드 import sys; # 9012 괄호 t = int(sys.stdin.readline().strip()) for tc in range(t): arr = list(sys.stdin.readline().strip()) # print(arr) stack = [] flag = 'YES' for i in arr: if i == '(': stack.append(i) else: if stack: stack.pop() else: flag = 'NO' break if stack: flag = 'NO' print(flag) 공감수 0 댓글수 0 2024. 3. 26.
  • 백준 18917 수열과 쿼리 38 Python 수학 구현 실버3 시간초과가 문제다. 값만 이용한 풀이 : 시간초과 5% # 18917 수열과 쿼리 38 실버3 n = int(input()) results = 0 results4 = 0 for i in range(n): arr = list(map(int,input().split())) method = arr[0] if arr[0] in [1,2]: x = arr[1] if method == 1: results += x results4 ^= x elif method == 2: results -= x results4 ^= x elif method ==3: print(results) elif method == 4: print(results4) 리스트 활용한 풀이 2% -> 시간초과 # 18917 수열과 쿼리 38 실버3 n .. 공감수 0 댓글수 0 2024. 3. 26.
  • 백준15654 N과M (5) Python 백트래킹 실버 3 # 15654 n과m (5) 실버 3 def perm(level): if level == m: print(*path) return for i in range(n): if visited[i]:continue visited[i] = 1 path.append(arr[i]) perm(level+1) path.pop() visited[i] = 0 n,m = map(int,input().split()) arr = list(map(int,input().split())) arr.sort() path = [] visited = [0] * n perm(0) 공감수 0 댓글수 0 2024. 3. 25.
  • 백준 2164 카드 2 Python 자료구조 큐 실버4 자료형에 큐 쓰는것은 알 수 있었지만, pop(0)하기엔 시간이 2초긴 하지만, 시간복잡도를 위해서 deque을 쓰는 방향으로 처리했음 from collections import deque # 2164 카드 2 실버4 n = int(input()) arr = deque() for i in range(1,n+1): arr.append(i) while len(arr) > 1: arr.popleft() a =arr.popleft() arr.append(a) print(*arr) 공감수 0 댓글수 0 2024. 3. 24.
  • 백준 16953 A -> B Python 그래프 BFS 실버2 실수 한 점: 1. 10의 9승까지 값을 받을 수 있기 때문에, 일반적인 bfs 풀이를 사용할 경우 메모리 오류가 뜬다. 2. 부분집합을 이용한 DFS 풀이처럼 문제를 풀이할 수 있다면 풀 수 있음을 인지했음, 하지만 이를 활용할 방법을 유연하게 생각하지 못함, => 인자로 cnt를 받아서 활용했으면 바로 풀이가 가능한 단계까지 풀이했었음 메모리 초과 풀이 from collections import deque def bfs(n,m): Q = deque() Q.append(n) visited[n] = 1 while Q: v = Q.popleft() if v > m: continue if v==m: return visited[m] for w in [v*2,int(str(v)+'1')]: if 0< w m: .. 공감수 0 댓글수 0 2024. 3. 23.
  • 백준 2178 미로 탐색 Python 실버 1 그래프, BFS # 2178 미로 탐색 실1 from collections import deque di = [1,-1,0,0] # 상하좌우 dj = [0,0,-1,1] n, m = map(int,input().split()) arr = [list(map(int,input())) for _ in range(n)] visited = [[0] * m for _ in range(n)] path = [] cnt = 0 que = deque() que.append((0,0)) visited[0][0] = 1 # 붕문처리 while que: y,x = que.popleft() # if visited[y][x]: continue for k in range(4): ni = y + di[k] nj = x + dj[k] if 0 공감수 1 댓글수 1 2024. 3. 22.
  • 백준 2667 단지번호 붙이기 Python 실버1 그래프 BFS 정답 코드 1 # 2667 단지번호 붙이기 from collections import deque def bfs(y,x): global cnt num = 0 if arr[y][x] ==0: return if visited[y][x]: return Q = deque() Q.append((y,x)) while Q: y,x = Q.popleft() num += 1 visited[y][x] = 1 if arr[y][x] == 1: arr[y][x] += cnt for direct in dij: # 4방향 di = y + direct[0] dj = x + direct[1] if 0 공감수 0 댓글수 0 2024. 3. 22.
  • 백준 15650. N과 M (2) Python 백트래킹 실버3 리스트 path에 저장시키면서, 일정 깊이에 도달했을 때, path를 출력하는 순열 코드에서 얕은 복사를 이용해 path를 paths로 복사한 후, paths를 정렬 후 리스트path_wrap와 비교해서 존재하지 않는 다면 추가하고, 출력할때 for문을 이용해서 출력하는 방식을 사용했다. n,m = map(int,input().split()) path = [] path_wrap = [] visited = [False] * (n+1) def perm(level): if level ==m: paths = path[:] paths.sort() if paths not in path_wrap: path_wrap.append(paths) return for i in range(1,n+1): if visited[i].. 공감수 0 댓글수 0 2024. 3. 21.
  • Swea D3_11780. 그룹 나누기 Python DFS def find(x): # 기저 조건 # 재귀함수 호출 전 # 재귀함수 호출 for to in adj_lst[x]: if visited[to]: continue visited[to] = True find(to) t = int(input()) for tc in range(1,t+1): V,E = map(int,input().split()) arr = list(map(int,input().split())) adj_lst = {x:[] for x in range(1,V+1)} for i in range(0,E): # 무향 그래프 adj_lst[arr[2*i]].append(arr[2*i+1]) adj_lst[arr[2*i+1]].append(arr[2*i]) # print(adj_lst) visited = [.. 공감수 0 댓글수 0 2024. 3. 20.
  • 백준 15649. N과 M (1) Python 백트래킹 실버3 백트래킹 공부를 위해 풀이함 순열 풀이를 그대로 사용했더니 나왔음... n,m = map(int,input().split()) def find(level): if level == m: print(*path) return for i in range(1,n+1): if visited[i]: continue visited[i] = 1 path.append(i) find(level+1) visited[i] = 0 path.pop() path = [] visited = [0] * (n+1) find(0) 공감수 0 댓글수 0 2024. 3. 20.
  • 백준 2941 크로아티아 알파벳 Python 구현 문자열실버5 시간 초과 날까봐 input() 이 아니라 sys를 썼었는데, 입력할때 `\n`가 같이 들어가서, rstip()를 넣어서 해결함 import sys; # 2941 크로아티아 알파벳 실버5 croal_alphabet = ['c=','c-','dz=','d-','lj','nj','s=','z='] str_v = sys.stdin.readline().rstrip() cnt = 0 for i in croal_alphabet: if i in str_v: cnt += str_v.count(i) str_v = str_v.replace(i,'8') str_v = str_v.replace('8','') cnt += len(str_v) print(cnt) 공감수 0 댓글수 0 2024. 3. 19.
  • 백준 1316 그룹 단어 체커 Python 정렬 문자열 실버5 틀린 코드 원인: 딕셔너리와 리스트 만드는 것을 한번에 하려고 하면서 cnt가 제대로 더해지지 않았음 중간에 문자가 하나만 존재할 경우 cnt가 하나가 더해지지 않기 때문에 return 하면서 result 카운팅이 이루어지지 않음 반례 : input: 2 ccazzzzbb abbbc output: 0 answer: 2 def check_word(word): global result dicts = {} cnt = 0 for i in range(len(word)): if dicts.get(word[i]): # 딕셔너리 값이 있따면 dicts[word[i]] += 1 else: # 값이 없다면 dicts[word[i]] = 1 # 전 인덱스와 비교해서 다를 때 if i > 0 and word[i] != wor.. 공감수 0 댓글수 0 2024. 3. 19.
  • 백준 1049 기타줄 Python 수학 그리디 실버4 오답 코드 6 묶음을 하나 사는 것보다 낱개 6개를 사는게 더 싼 경우를 고려하지 않았음 if arr_6[0] >= (n % 6) * arr_1[0]: sum_v = (n//6) * arr_6[0] + (n % 6) * arr_1[0] else: sum_v = (n//6 +1) * arr_6[0] print(sum_v)if arr_6[0] >= 6 *arr_1[0] 룰 추가해야 했다. 정답 코드 # 1049 기타줄 실버4 n, m = map(int,input().split()) arr_6 = [] arr_1 = [] for _ in range(m): x,y = map(int,input().split()) arr_6.append(x) # 6개짜리 arr_1.append(y) # 1개 짜리 # print(a.. 공감수 0 댓글수 0 2024. 3. 18.
  • 백준 1026 보물 Python 수학 그리디 정렬 실버4 문제에서 B를 정렬하지 말라는 말이 없었다면, A는 오름차순으로 B는 내림차순으로 정렬 후 같은 인덱스끼리 곱했다면 정답이었겠지만, 조건이 있었기 때문에, B의 맥스값을 뽑아내는 방법을 사용했다. 풀이 후 다른 사람들의 풀이도 비교해보고 싶었는데, 전부 이 알고리즘에서 파생된 방법을 채택했는것을 알 수 있었다. # 1026 보물 실4 n = int(input()) arr_a = list(map(int,input().split())) arr_b = list(map(int,input().split())) arr_a.sort() sum_v = 0 i = 0 while arr_b: sum_v += max(arr_b) * arr_a[i] arr_b.remove(max(arr_b)) i += 1 print(sum_v) 공감수 0 댓글수 0 2024. 3. 18.
  • 백준 1476 날짜계산 Python 수학 브루트포스실버5 실수한 부분 if jun_e == e and jun_s==s and jun_m==m: break 나머지가 0이 나올 때 :15 28 19 일 경우 jun_e 가 0 이되서 15랑 같지 않다고 나옴 정답코드 # 1476 날짜계산 실5 ''' 지구 e 15 태양 s 28 달 m 19 ''' e,s,m = map(int,input().split()) i = 0 # 초기화 jun_e = 0 jun_s = 0 jun_m = 0 while True: i += 1 # 1년씩 늘어남 jun_e = i % 15 jun_s = i % 28 jun_m = i % 19 if jun_e == e%15 and jun_s==s%28 and jun_m==m%19: break print(i) 공감수 0 댓글수 1 2024. 3. 17.
  • 백준 10814 나이순정렬 Python 정렬 실버5 정답 풀이 n = int(input()) member = [] for i in range(1,n+1): age, name = map(str,input().split()) age = int(age) member_one = [age,name,i] member.append(member_one) member.sort(key=lambda x: (x[0],x[2])) # print(member) for j in member: print(*j[:2]) 틀린 풀이 : age를 int로 하지 않았기 때문에, 10 20 100 이 있다면, 10 100 20 으로 정렬이 이루어지고있었음 ''' 나이 오름차순 + 나이가 같아면 입력된 순서''' n = int(input()) member = [] for i in range(1.. 공감수 0 댓글수 0 2024. 3. 17.
  • 백준 9613 GCD 합 Python 유클리드 호제법 실버4 알아야 했던 것 1. 유클리드 호제법 # 반복문 def find_GCD(b,a): while b != 0: a,b = b , a%b return a\ # 재귀문 def find_GCD(a,b): r = a%b if r == 0: return b else: return find_GCD(b,r) 2. 두 항을 어떻게 비교해 나갈 지 실수한점 : 전체의 경우의 수를 구해놓고, 그걸 활용하려 하는 과정에서 어려움이 있어 해결하지 못함 2개의 인덱스를 가지고 처리하는것이였기 때문에 => 선택 정렬 알고리즘을 수정해 기준 인덱스와 선택인덱스를 비교해 나가는 방식으로 풀이하면 됐었음 정답코드 t = int(input()) def find_GCD(a,b): r = a%b if r == 0: return b else: .. 공감수 1 댓글수 2 2024. 3. 16.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.