알고리즘 이론 & 풀이/백준(BOJ)

[백준] 1026번 - 보물 (nodejs)

1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 결과만 놓고 보자면 A는 오름차, B는 내림차로 정렬해서 곱하면 간단하게 풀리겠지만, 나는 문제에서 제시한대로 정직하게 B는 냅두고 A만 재배열하는 방법을 고안해 풀어보았다. 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의..

[백준] 2178번 - 미로 탐색

문제 https://www.acmicpc.net/problem/2178 // 입력 4 6 101111 101010 101011 111011 // 출력 15 풀이 BFS로 최단거리 찾기 문제. 맨 처음에 풀 때는 백트래킹을 안해줘서 시간제한에 걸렸는데, visitied로 방문했던 곳을 관리해 한번 갔던 곳은 다시 안 가게 했더니 통과했다. const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); const [N, M] = input[0].trim().split(' ').map(Number); const maps = []; for (let i = 1; i < input.length; i..

[백준] 1260번 - DFS와 BFS (js)

문제 https://www.acmicpc.net/problem/1260 풀이 4 5 1 1 2 1 3 1 4 2 4 3 4 이걸 아래와 같이 정리한다. [ [], [ 2, 3, 4 ], [ 1, 4 ], [ 1, 4 ], [ 1, 2, 3 ] ] 1번 인덱스에 [2, 3, 4]가 있다는 것은 1과 2, 3, 4번 노드가 연결되어 있다는 뜻이다. 그리고 visited 배열을 둬서 갔던 곳을 다시 방문하지 않도록 true/false로 관리한다. graph와 visited 배열 모두 0번 인덱스는 비워두고 시작해서 직관적으로 1번 인덱스가 1번 노드라는 것을 알 수 있게 한다. dfs는 깊이 우선 탐색이기 때문에 for문과 재귀호출을 이용해서 구현한다. 아래로 파고들었다가 빠져나오면 for문을 이용해 형제 노..

[백준] 1158번: 요세푸스 문제 (Python)

문제 📄 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 내 풀이 💻 N, K = map(int, input().split()) arr = [i for i in range(1,N+1)] result = [] index = 0 while len(arr)>0: index += K-1 index %= len(arr) result.append(arr[index]) del arr[index] print("") 문제에 주어진 것처럼 (N, K)가 (7, 3)일 때를 가정하고 문제를 풀어보자. 주어진 수의 배열이 1부터 7일 때 3번째 숫자를 제거하는 과정은 다음과 같다. 1 2 3 4 5 6 7 (3 제거할 차..

[백준] 5598번: 카이사르 암호 (Python)

문제 📄 5598번: 카이사르 암호 가이우스 율리우스 카이사르(Gaius Julius Caesar)는 고대 로마 군인이자 정치가였다. 카이사르는 비밀스럽게 편지를 쓸 때, 'A'를 'D로', 'B'를 'E'로, 'C'를 'F'로... 이런 식으로 알파벳 문자를 3개씩 건 www.acmicpc.net 내 풀이 💻 word = input() orgin = [] for w in word: ascii_num = ord(w) if ascii_num >= 68: orgin.append(chr(ascii_num-3)) else: orgin.append(chr(ascii_num + 23)) print(''.join(orgin)) 설명 🔑 ord(문자) - 문자를 ASCII number로 바꾸기 (ord는 ordinal..

[백준] 2444번: 별 찍기 - 7 (Python)

문제 📄 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 내 풀이 💻 N = int(input()) for i in range(1,N+1): for _ in range(N-i): print(" ",end='') for _ in range(2*i-1): print("*",end='') print() for i in range(1,N): for _ in range(i): print(" ",end='') for _ in range(2*(N-i)-1): # (2*N-1)-2*i print("*",end='') print() Review 🙋‍♀️ 파이썬 내의 문자열 반복 기능을 이용하면 for 문을 여러 개 돌리지 않아도 될 뻔했다. N = in..