민규의 흔적

2024년 5월 16일 0-1 냅색 문제를 풀어보며 해당 이론에 대해 알아보도록 하겠다.  문제 링크 : SWEA 3282번 - 0/1 Knapsack SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   문제 접근 제목에서 친절하게 0-1 냅색 문제임을 알려주었다. Knapsack 문제는 배낭 문제라고도 하며, 0-1 Knapsack 문제와 Fractional(분할 가능한) Knapsack 문제가 존재한다. 둘의 차이점은 다음의 예시를 보며 설명하겠다. 민규는 고향으로 내려가기 전, 배낭에 선물을 담아 가져갈 것이다.선물을 무한정 담으면 좋겠지만, 배낭의 한계 무게 W를 초과하면 배낭이 찢어진다.민규는 각각의 선물..

2024년 5월 16일문제 링크 : SWEA 5607번 -  [Professional] 조합  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근 문제 자체는 간단하다. N Combination R을 1234567891로 나눈 나머지 값을 구하면 되는 문제. N combination R을 구하는 수식은 다음과 같다. N! / R! * (N - R)! 단순히 계산을 통해 정답을 구하려하면 계산 과정에 도출되는 값들이 너무 커질 뿐더러 ( N의 최대값은 1,000,000, 1,000,000!은 상상도 하기 싫은 큰 수이다), 1234567891로 나누기 직전에 도출되는 값은 최대 1,000,000 C 500,..

2024년 5월 14일문제 링크 : [Python 파이썬] SWEA 1215번 - [S/W 문제해결 기본] 3일차 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근 전형적인 패턴매칭 알고리즘 문제이다.전체 문자열 S가 주어지고 부분 문자열 P가 주어졌을 때, S 안에 P가 몇 개 존재하는지 알아내면 되는 문제이다. 문자열 S의 맨 앞에서부터 문자를 하나씩 선택하며, 해당 문자를 시작으로 P의 길이만큼 슬라이싱하여 이 것이 패턴 P와 같은지 확인하기엔 너무 불필요한 연산이 많아진다. 그래서 나는 S의 각 문자가 P의 첫 번째 글자와 같은지 확인 후 같다면 해당 문자부터 P 길이만큼 슬라이싱하여 P와 대조해..

2024년 5월 14일문제 링크 : SWEA 11315번 - 오목 판정 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   문제 접근 N x N 사이즈의 판이 주어지고, 돌이 놓아진 곳은 o , 아닌 곳은 . 문자를 표기한다. 우리가 아는 오목과 같이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 돌이 있는지 판정하면 되는 문제이다.  먼저 가로, 세로, 대각선 방향으로 한 칸씩 전진하며 탐색해야 하기에 다음과 같이 8방향을 탐색하기 위한 두 배열을 선언해주어야 한다. # 동, 남동, 남, 남서, 서, 북서, 북, 북동d_row = [0, 1, 1, 1, 0, -1, -1, -1]d_col = [1..

2024년 5월 10일문제 링크 : SWEA 1860번 - 진기의 최고급 붕어빵 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   문제 접근 진기는 0초부터 붕어빵을 만들기 시작하며, M초마다 K개의 붕어빵을 만들 수 있다. 손님이 도착하는 시간이 각각 주어졌을 때, 모든 손님이 붕어빵을 먹을 수 있으면 Possible, 한 명이라도 못먹는다면 Impossible을 출력하는 문제이다. 여기서 우리가 조심해야 하는 점은 손님이 0초에 올 수 있다는 점이다.(마치 오픈런) 1초 단위로 시간이 흐를 때마다 갱신되는 붕어빵의 개수와 손님의 도착, 그리고 손님이 붕어빵을 먹을 수 있는지 알아야하기 때문에 단순 구현 문제라..

2024년 5월 10일문제 링크 : SWEA 1216번 - [S/W 문제해결 기본] 3일차 - 회문2 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  비슷한 문제 SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  풀이 : https://ymg5218.tistory.com/82 [Python 파이썬] SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문12024년 5월 8일문제 링크 : SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문..

2024년 5월 8일문제 링크 : SWEA 1220번 - [S/W 문제해결 기본] 5일차 - Magnetic SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근  N극과 S극을 가진 자성체 모두를 한 칸씩 옮겨보며 진행하자니 테이블의 사이즈가 너무 커(100 X 100) 시간복잡도가 말도 안 될 것이다. 일단 이 문제가 가진 조건들을 하나씩 뜯어보도록 하자. 1. 자성체끼리는 전혀 반응하지 않으며, 테이블 위아래에 존재하는 각 극에만 반응한다.2. N극 성질을 가지는 1과 S극 성질을 가지는 2가 존재하며, 0은 어느 자성체도 존재하지 않는 칸이다.3. 각 자성체는 이끌리는 방향으로 계속 끌려가다 배열의 ..

2024년 5월 8일문제 링크 : SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근 8 X 8 사이즈의 글자판에서 회문을 찾는 문제이다.회문이란, 문자열 뒤집었을 때 원래 문자열과 같은 문자열을 의미하며 예시로는 '기러기', '역삼역', 'ABCBA' 등이 있다. 또한 한 글자 또한 뒤집으면 같은 글자가 되기에 'A', 'Z' 같은 한 글자 또한 회문으로 간주한다. 입력 값으로 찾아야 하는 회문의 길이와 글자판이 주어졌을 때, 길이에 부합하는 회문이 총 몇 개 인지 찾는 문제이다.단, 회문은 가로 혹은 세로로 이어져있어야 유효하다.(대각선..