민규의 흔적

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

2024년 5월 8일문제 링크 : SWEA 1289번 - 원재의 메모리 복구하기 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 접근  파이썬 기준, 10개의 테스트 케이스를 합쳐 4초의 시간 제한을 두고 있기 때문에, 시간복잡도를 고려해야겠다고 판단했다. 문제를 보면, 특정 인덱스 위치 값을 0 또는 1로 결정하면 해당 위치 이후부터 끝까지 모두 결정한 값으로 덮어 씌워지도록 설정이 되어있다. 이를 보고 " 초기 상태(모든 bit가 0)의 0번째 인덱스부터 끝까지, 원래 메모리의 인덱스 위치와 다르면 반대 값으로 치환해주어 그 뒤의 값도 계속 바꿔나가주면 되겠구나! " 라고 잠깐 생각했지만 위험한 생각이었..

2024년 4월 11일 문제 링크 : 백준 2579번 - 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이..

2024년 4월 2일 문제 링크 : 백준 1484번 - 다이어트 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 ..

2023년 11월 21일 문제 링크 : 백준 2493번 - 탑 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 ..

2023년 11월 16일 문제 링크 : 백준 9935번 - 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째..

2023년 11월 18일 문제 링크 : 백준 1181번 - 단어 정렬 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 알고리즘 분류 문자열 정렬 문제 접근 중복된 단어는 하나만 남기고 제거해야 한다는 부분에서, 나는 딕셔너리를 활용하면 되겠다라고 생각했다. 딕셔너리 선언 후, 이미 존재하는 문자..

2023년 10월 27일 플로이드-워셜(Floyd-Warshall) 플로이드-워셜 알고리즘이란, 모든 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면, 플로이드-워셜 알고리즘은 한 번의 실행으로 모든 정점 간의 최단 거리를 구할 수 있다는 차이로 구분할 수 있다. 또한 음수 가중치가 존재하는 가중치 그래프에서는 적용할 수 없는 다익스트라 알고리즘과는 다르게, 플로이드-워셜 알고리즘은 음수 가중치가 존재하는 가중치 그래프에서도 활용할 수 있다. 접근 방법 사전 준비 플로이드-워셜 알고리즘을 적용하기 위해선, 가중치 그래프가 존재해야 한다. 임의의 가중치 그래프를 예시로 들어보겠다. 정점은 1~5번까지 총 5개의 정점이 존재하고,..