코테용 문제풀이/백준

섬의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/4963 백준 알고리즘 기초 2/2 600에서 6번째 - 4963번 섬의 개수를 풀어보았다. 풀이: https://aigong.tistory.com/513 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(a,b,c,d): inp[a][b]=2 for i in range(8): na,nb=a+dx[i],b+dy[i] if 0

단지번호붙이기 풀이

문제 링크: https://www.acmicpc.net/problem/2667 백준 알고리즘 기초 2/2 600에서 5번째 - 2667번 단지번호붙이기를 풀어보았다. 풀이: https://ji-gwang.tistory.com/294 를 참고했다. C++ Python from collections import deque def bfs(g,a,b): q=deque() q.append([a,b]) g[a][b]=0 cnt=1 while q: x,y=q.popleft() g[x][y]=0 for i in range(4): nx=x+dx[i] ny=y+dy[i] if nx=len(g) or ny=len(g): continue if g[nx][ny]==1: g[nx][ny]=0 q.append([nx,ny]) cn..

이분 그래프 풀이

문제 링크: https://www.acmicpc.net/problem/1707 백준 알고리즘 기초 2/2 600에서 4번째 - 1707번 이분 그래프를 풀어보았다. 풀이: https://ji-gwang.tistory.com/293 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(v,a): global res if res: return visit[v]=a for i in mat[v]: if not visit[i]: dfs(i,-a) elif visit[v]==visit[i]: res=True return k=int(input()) for _ in range(k): v,e=map(int,sys.stdin.readline().split(..

연결 요소의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/11724 백준 알고리즘 기초 2/2 600에서 3번째 - 11724번 연결 요소의 개수를 풀어보았다. 풀이: 재귀허용 범위를 넓혀주고, dfs로 탐색한다. https://yuna0125.tistory.com/66 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(v): visit[v]=True for i in mat[v]: if not visit[i]: visit[i]=True dfs(i) n,m=map(int,input().split()) mat=[[] for i in range(n+1)] cnt=0 for i in range(m): a,b=map(int,sys..

DFS와 BFS 풀이

문제 링크: https://www.acmicpc.net/problem/1260 백준 알고리즘 기초 2/2 600에서 2번째 - 1260번 DFS와 BFS를 풀어보았다. 풀이: deque를 이용해 bfs를 구현했다. 코드는 https://ji-gwang.tistory.com/291 를 참고했다. C++ Python from collections import deque def dfs(v): dvisit[v]=True print(v,end=' ') for i in range(1,n+1): if not dvisit[i] and mat[v][i]: dfs(i) def bfs(v): q=deque([v]) bvisit[v]=True while q: v=q.popleft() print(v,end=' ') for i ..

ABCDE 풀이

문제 링크: https://www.acmicpc.net/problem/13023 백준 알고리즘 기초 2/2 600에서 1번째 - 13023번 ABCDE를 풀어보았다. 풀이: dfs를 이용해 깊이가 5인지를 보는 문제이다. C++ Python def dfs(depth,idx): global res if depth==4: res=True return for i in connect[idx]: if not visit[i]: visit[i]=True dfs(depth+1,i) visit[i]=False n,m=map(int,input().split()) connect=[[] for i in range(n)] visit=[False]*n res=False for i in range(m): a,b=map(int,in..

종이 조각 풀이

문제 링크: https://www.acmicpc.net/problem/14391 백준 알고리즘 기초 2/2 540에서 4번째 - 14391번 종이 조각을 풀어보았다. 풀이: 비트마스크를 이용해 푸는 문제이다. https://velog.io/@imnotmoon/Python-%EB%B0%B1%EC%A4%80-14391.-%EC%A2%85%EC%9D%B4-%EC%A1%B0%EA%B0%81 를 참고했다. C++ Python n,m=map(int,input().split()) inp=[list(map(int,input())) for i in range(n)] def sol(): res=0 for i in range(1

부분수열의 합 풀이

문제 링크: https://www.acmicpc.net/problem/1182 백준 알고리즘 기초 2/2 540에서 2번째 - 1182번 부분수열의 합을 풀어보았다. 풀이: 파이썬은 combinations를 썼다. C++ Python from itertools import combinations n,s=map(int,input().split()) inp=list(map(int,input().split())) cnt=0 for i in range(1,n+1): a=combinations(inp,i) for b in a: if sum(b)==s: cnt+=1 print(cnt) Java

집합 풀이

문제 링크: https://www.acmicpc.net/problem/11723 백준 알고리즘 기초 2/2 540에서 1번째 - 11723번 집합을 풀어보았다. 풀이: 명령어를 적절하게 구현하면 된다. C++ Python import sys m=int(sys.stdin.readline()) s=set() for _ in range(m): inp=list(sys.stdin.readline().split()) if len(inp)!=2: if inp[0]=="all": s=set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]) else: s=set() else: ord,num=inp[0],int(inp[1]) if ord=="add": s.add(num) el..

맞춰봐 풀이

문제 링크: https://www.acmicpc.net/problem/1248 백준 알고리즘 기초 2/2 530에서 7번째 - 1248번 맞춰봐를 풀어보았다. 풀이: https://gksdudrb922.tistory.com/238 C++ Python n = int(input()) data = input() k = 0 s = [[0] * n for _ in range(n)] for i in range(n): for j in range(i, n): if data[k] == '0': s[i][j] = 0 elif data[k] == '-': s[i][j] = -1 else: s[i][j] = 1 k += 1 def check(index): total = 0 for i in range(index, -1, -1)..