![[백준 16953] A->B](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FAALWK%2FbtsJbJ7Zanc%2FAAAAAAAAAAAAAAAAAAAAAPmgtV6sOooCC7CvtlWdUTi8uG4ZYtAtYJXp39ef-o3k%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1756652399%26allow_ip%3D%26allow_referer%3D%26signature%3DObc7zpWlfhf4yTwz6sWGVbXwWqQ%253D)
[백준 16953] A->B
백준 16953 A -> B접근처음에는 이진 트리로 1차원 배열에 두 연산을 저장하면서 진행하려고 했으나 메모리 초과가 발생한다는 것을 깨닫고 방향을 전환하였다.BFS 를 통해서 B까지 도달할 수 있는 가능한 연산 횟숫를 찾고자 하였다.만약 가능한 연산이 없을 경우에는 -1을 출력해야 한다.전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..
![[백준 11660] 구간 합 구하기 5](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FkySHr%2FbtsI84sgCV5%2FAAAAAAAAAAAAAAAAAAAAAL_OIbhNZPS-k22AOQn4ULAHl_RmrkjpjaGxoM2Jy2Ad%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1756652399%26allow_ip%3D%26allow_referer%3D%26signature%3DH9hO1UBXxZgL8xHq1B0g20VslDw%253D)
[백준 11660] 구간 합 구하기 5
구간 합 구하기 5참고 : https://www.acmicpc.net/problem/11660접근해당 문제는 이차원 배열에서 누적합을 구해서 주어진 구간의 합을 구해야 한다고 생각했습니다.map이라는 N * N 의 2차원 배열에 누적합을 계산해서 저장시간 복잡도 : O(N^2)(i열 , j-1행의 누적합) + (i-1열, j행의 누적합) - (i-1열, j-1행의 누적합) + (i열, j행)i 열 j 행 의 누적합은 아래 식을 통해서 구할 수 있습니다.주어진 구간에서의 합 구하기해당 과정을 통해서 점화식을 구하면 아래와 같습니다.- 코드를 구현할 때는 map, sumMap의 크기를 N+1로 해서 진행.전체 코드package baekjoon_day01;import java.io.*;import java.u..
[baekjoon] 세탁소 사장 동혁(2720)
문제문제1차 접근쿼터 : 0.25다임 : 010니켈 : 0.05페니 : 0.01** 거스름돈은 항상 $5.00 이하 **** 손님이 받는 동전의 개수 최소 **ex ) $1.24 거술러 주어야 한다면- 4 쿼터- 2 다임- 0 니켈- 4 페니그리디 알고리즘을 사용하여 우선적인 동전으로 처리하고 그 후에 나머지 동전들을 처리하는 로직으로 진행하였다.확인T = int(input())for test_case in range(1, T+1): price = int(input()) coins = [] while price > 0: for i in [25, 10, 5, 1]: a = price // i b = price % i p..
[SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호
문제접근 방법정답 여부접근 방법1. queue 자료구조를 활용해서 회전마다 popleft를 횟수마다 해주고 다시 빼낸 것을 append하여 회전 때마다의 리스트를 구한다.2. 그 후 list를 잘라서 해당 숫자를 join 해 문자열로 만들어서 set 자료구조에 넣어서 중복이 없도록 한다.3. 해당 set을 리스트로 바꾸고 16진수를 10진수로 변경한다.4. 내림차순으로 sort한 후, K번째 수를 빼낸다.코드from collections import dequeT = int(input())for test_case in range(1, T+1): N, K = map(int, input().split()) lst = list(input()) n_set = set() count = N //..
[SWEA] 2001. 파리퇴치
문제1차 접근 방법정답 여부1차 접근 방법N * N 의 사이즈에서 각 칸 마다 파리의 숫자가 있는데 M * M 사이즈의 파리채를 통해 가장 많은 수의 파리를 잡아야 하는 것이 목적이다.이를 위해 N * N 배열을 순회하면서 M * M 사이즈만큼 확인해서 각 sum 을 구하고 그 가운데 최댓값을 구하는 방법을 고안하였다.그러기 위해서는 N - M + 1 범위까지만 순회하여도 M 사이즈 만큼은 다시 순회를 할 것이기 때문에 세로, 가로는 처음에 N - M +1 만큼 순회를 2중으로 순회를 하고,그 안에서 다시 M 만큼 가로, 세로 순회를 해야한다.그리고 M만큼 순회를 하기 전에 현재 파리채의 sum을 0으로 초기화하고 계산한 다음 max_sum과 비교하면서 최댓값을 정해야한다.아래가 구현 코드이다!!for문..
[SWEA] 1954. 달팽이 숫자
문제1차 접근 방법정답 여부1차 접근 방법방향을 잘 조절해서 2차원 배열 안에 1 ~ (N * N + 1)을 넣어주자.T = int(input())for test_case in range(1, T + 1): N = int(input()) print(f'#{test_case}') answer = [[0] * N for _ in range(N)] directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] direction_index = 0 x, y = 0, 0 # 시작 위치 for i in range(1, N * N + 1): answer[x][y] = i next_x, next_y = x + directions[..
[SWEA]1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (python)
[SWEA]1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (python)문제문제 풀이1차 접근 방법정답 여부2차 접근 방법정답 여부1차 접근 방법1차로 접근 했을 때는 배열을 순회하면서 현재의 index와 value에 대해서 index도 크고 가장 value가 큰 것을 변경하는 과정을 거쳐서 총 교환 회수에서 빼주었다.또한, 교환 횟수가 배열을 다 순회하고도 남았을 경우에 짝수 개수이면 49 -> 92 -> 49 (총 2회) 다시 제자리 값으로 돌아오기 때문에 넘겨주고, 홀수인 경우에는 중복 숫자가 있으면 짝수 개수처럼 처리하고, 중복 숫자가 없는 경우에는 마지막 두 자리 수를 변경해주었다.import syssys.stdin = open("1244_D3/input.txt", "r")from c..