본문 바로가기

백준44

[백준/5671] 호텔 방 번호 | 중복값 개수 세기(딕셔너리와 SET) 5671 호텔 방 번호 5671번: 호텔 방 번호 선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004호와 같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지 www.acmicpc.net 알고리즘 범위에 해당하는 숫자들이 자릿수마다의 중복되는지 체크하면 된다. 같은 값이 있는지 확인하는 방법으로는 딕셔너리를 떠올렸고 아래와 같이 중복 체크를 해주었다. for item in hotel: d={'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0} flag=True for s in str(item): if s in d.keys(): d[s] += 1 f.. 2024. 3. 17.
[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS 바이러스 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력에서 직접 연결되어 있는 쌍이 주어진다. 더보기 1 2 2 3 1 5 5 2 5 6 4 7 1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다. 이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다. 양방향 그래프를 2차원 리스트로 정의 graph = [[] for _ in range(n+1)] for _ in range(m): x,y=map(int, input().split()) graph[x].append(y) graph[y]... 2024. 3. 5.
[백준/22232] 가희와 파일 탐색기 가희와 파일 탐색기 22232번: 가희와 파일 탐색기 첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다. 2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열 www.acmicpc.net 알고리즘 정렬이 순서대로 이어져야 하므로 lambda를 활용하였다. 또한, 2 번째 조건은 까다로워서 정렬함수 말고 직접 교체해주었다. 전체 코드 import sys;input=sys.stdin.readline n,m=map(int, input().split()) jo_test = [input().rstrip() for _ in range(n)] ext = set(input().rstrip() for .. 2024. 2. 28.
[백준/1015] 수열 정렬 수열 정렬 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다. 처음에 문제 이해 자체가 좀 어려웠는데, 예시를 통해서 비교적 쉽게 이해할 수 있었다. 일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N 2023. 9. 30.
[백준/11004] K번째 수 | Python 정렬 함수의 알고리즘 K번째 수 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 N(1 2023. 8. 2.
[백준/1032] 명령 프롬프트 | 문자열 비교 명령 프롬프트 알고리즘 문자열 비교 알고리즘이다. 이런 문제를 풀 때는 모든 보기를 다 비교해야 할지, 일부로도 해결이 가능한지 판단한다. 어차피 N의 범위가 적으니까 할 수 있는 건 다 해서 풀어낸다. 전체 코드 내가 작성한 코드 import sys; input=sys.stdin.readline n=int(input()) file=[input() for _ in range(n)] tmp=[] for i in range(n): for j in range(i+1, n): if file[i] != file[j]: a = file[i] b = file[j] for k in range(len(a)): for l in range(len(b)): if a[k] != b[k] : tmp.append(k) break .. 2023. 7. 4.
[백준/1009] 분산 처리 | 반복되는 숫자 어떻게 효율적으로 처리할까  분산 처리 알고리즘 승수의 마지막 자리 반복 0 0 1 1 2 2 4 8 6 3 3 9 7 1 4 4 6 5 5 6 6 7 7 9 3 1 8 8 4 2 6 9 9 1 수의 끝자리만 가져오는 두 가지 방법 문자열 활용 a = str(a) a = int(a[-1]) 나머지 활용(%10, %100, %1000, ....) a %= 10 # 끝 한 자리만 a %= 100 # 끝에서부터 2개 전체 코드 import sys; input=sys.stdin.readline t=int(input()) for _ in range(t): a,b = map(int,input().split()) a = str(a) a = int(a[-1]) if a == 1 or a == 5 or a == 6: print(a) # 4 번씩.. 2023. 7. 3.
[백준/10158] 개미 | 점화식 그게 뭔데 그거 어떻게 하는 건데 10158 개미 알고리즘 t의 범위가 1 ≤ t ≤ 200,000,000이므로 완전탐색을하면 타임아웃이다. 그렇다면 어떤 점화식을 세워서 문제를 풀어야 한다는 건데 1. x와 y의 독립성 이 문제는 1초의 시간이 지날 때 x = (x+1) or (x-1)이 되고 y = (y+1) or (y-1)이 된다. 따라서 각각의 값이 독립적으로 움직인다는 결론에 도달할 수 있다. 2. 이동 횟수와 이동 거리의 관계 x좌표와 y좌표는 각각 t만큼 이동을 하게 되고, 이 이동 주기가 2*w, 2*h이다. 아래와 같은 그래프를 보면 이해가 쉽다. 따라서 이동 자체에 대한 점화식은 다음과 같다. (p+t) % 2*w (q+t) % 2*h 이제 이동 좌표에 관한 점화식을 얻었으니, 거리를 구하면 된다. 거리는 수학적으로 뺄.. 2023. 6. 29.
[백준/9251] LCS | 최장공통수열 9251 LCS LCS 문제 해결 기법 두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다. 문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자. dp table은 memoization 방식으로 이어나간다. 알고리즘 이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,, table 설명을 위해 i=6, j=4일 때를 예를 들어보자면 일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 .. 2023. 5. 12.
[백준/2178] 미로 탐색 | BFS와 최단 경로 BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아.. 2023. 5. 12.
[백준/16283] Farm https://www.acmicpc.net/problem/16283 16283번: Farm 입력은 표준입력을 사용한다. 첫 번째 줄에 네 정수 a, b, n, w가 한 줄에 주어진다. 1 ≤ a ≤ 1,000, 1 ≤ b ≤ 1,000, 2 ≤ n ≤ 1,000, 2 ≤ w ≤ 1,000,000이다. www.acmicpc.net [알고리즘] 백준 사이트에서 알고리즘 문제를 풀고 나면 다른 사람이 쓴 코드를 항상 확인해보는데, kocc10님의 코드에 배울 점이 많아서 포스팅 해본다. [내가 쓴 코드] a, v, n, w = map(int, input().split()) ans = [] for i in range(n) : for j in range(n) : if a*i + v*j == w and i+j ==.. 2023. 3. 10.
[백준/2961] 도영이가 만든 음식 | 브루트포스의 구조(조합) | 곱셈 누적 초기화는 1 | 디버깅을 열심히 하자. 내가 짠 코드를 파악하는 방법 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다. 신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 .. 2023. 3. 5.

티스토리툴바