본문 바로가기

Problem Solving16

백준 2075번 - N번째 큰 수: 약간 더 빠른 코드 문제백준, 실버 3, https://www.acmicpc.net/problem/2075풀이 날짜: 2025.2.4.풀이 시간: 11:03~11:29(26분)알고리즘 분류: 정렬, 우선순위 큐사용 언어: C++문제 해설해당 문제는 상위 N번째 값을 구하는 문제이지만 두 가지 특징이 있다.메모리 제한이 걸려 있다. 12MB의 제한이 있다.모든 수는 자신의 한 칸 위의 수보다 더 크다.첫 번째 특징을 생각해보면, 해당 문제는 NN (1≤N≤1500)의 보드가 주어지고 각 값의 절댓값이 10억보다 낮으므로 자료를 모두 저장하는 데에 최소 1,5001,5004Byte=2,250,0004Byte = 9,000,000Byte, 즉 약 9MB의 메모리가 필요하다.이것만 해도 메모리 제한이 아슬아슬하므로, 만약 정렬을 .. 2025. 2. 4.
백준 1311번 - 할 일 정하기 1 문제백준, 골드 1, https://www.acmicpc.net/problem/1311풀이 날짜: 2025.1.29.풀이 시간: 15:17~16:30, 안 돼서 GPT 킴, 17:28에 DFS 방식으로 해결(총 2시간 11분)알고리즘 분류: 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설해당 문제는 비트필드를 이용한 다이나믹 프로그래밍을 활용하는 문제이다.문제의 정답을 탐색할 때 탐욕법이나 다른 방법을 사용할 수 없으므로, 완전 탐색으로 모든 경우의 수를 측정해야 한다. 그런데 4명의 사람이 순차적으로 1-2-3-4번 일을 맡는 경우와 2-1-3-4번 일을 맡는 경우, 뒤의 3-4번 일의 비용을 계산할 땐 중복 계산이 발생하게 된다.이러한 중복 계산을 피하려면 상태를 저장하는 비트필드 기.. 2025. 1. 29.
백준 1562번 - 계단 수 풀이(C++) 1562번-계단 수문제백준, 골드 1, https://www.acmicpc.net/problem/1562풀이 날짜: 2025.1.28.풀이 시간: 약 2시간알고리즘 분류: 다이나믹 프로그래밍, 비트마스킹, 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설‘1562 계단 수’는 비트필드를 이용한 다이나믹 프로그래밍을 필요로 하는 문제로, 해당 알고리즘을 활용하는 문제 중 가장 기초적인 문제이다.‘2098 외판원 순회’ 문제가 해결되지 않아 시도해보았는데, 난이도는 더 쉽지만 개념을 안다면 꽤 간단하게 해결할 수 있는 문제였다.비트필드를 이용한 다이나믹 프로그래밍은 ‘현재 상태’를 필요로 하는 문제에 유용하게 사용된다. 일반적인 다이나믹 프로그래밍에서는 정점 번호에 대한 정보나, 문자열의 인덱.. 2025. 1. 28.
백준 9252번 - LCS 2 문제백준, 골드4, https://www.acmicpc.net/problem/9252풀이 날짜: 2025.1.22., 2025.1.23풀이 시간2025.1.22: 11:34~12:31, 20:31~21:09(38분, 포기),2025.1.23: 11:19~12:58(1시간 47분)총 3시간 22분알고리즘 분류: 다이나믹 프로그래밍사용 언어: C++ 문제 해설해당 문제는 LCS(Longest Common Subsequence, 최장 길이 부분 수열) 알고리즘을 통해 문제를 풀어야 한다.LCS 알고리즘에 대해서는 전혀 몰랐는데, 이번 기회에 배우게 되어 정리해보았다.(LCS에 대한 설명은 그림으로 정말 잘 정리해주신 분이 계셔서 공유하고자 합니다. 본 글은 해당 글을 참고하여 작성하였습니다: https://v.. 2025. 1. 24.
백준 1018 체스판 다시 칠하기 문제백준, 실버4, 1018번: 체스판 다시 칠하기풀이 날짜: 2024.12.27풀이 시간: 11:37~12:07사용 언어: C++문제 해설해당 문제는 MxN 보드에서 조건을 만족하는 8x8 부분 보드를 찾는 문제이다.이때, 체크무늬 형태로 보드를 색칠해야 하는데, 체스판 보드의 색상은 잘못 칠해져 있을 수도 있으므로 체크무늬 형태로 칠해야 한다. 색은 하양, 검정 두 개가 있는데, 좌측 상단이 검정으로 시작할 수도 있고 하양으로 시작할 수도 있으므로 두 케이스를 모두 검사해야 한다.해당 문제를 브루트포스 방식으로 접근하는 사람들이 굉장히 많고, 해당 방식으로 해도 이 문제를 푸는 데에는 충분하다.다만 컴퓨터비전 시간에 적분 영상 알고리즘에 대해 듣게 되어서, 한번 적용해볼 수 있지 않을까 해서 적용해보.. 2024. 12. 27.
프로그래머스 - 수식 최대화 수식 최대화 코딩테스트 연습 - 수식 최대화 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 조건 expression은 길이가 3 이상 100 이하인 문자열입니다. expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다. 즉, "402+-561*"처럼 잘못된 수식은 올바.. 2022. 2. 14.
백준 2922 즐거운 단어 오늘의 문제: 2922번: 즐거운 단어 (acmicpc.net) 2922번: 즐거운 단어 상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 www.acmicpc.net 도무지 풀리지 않아서 일주일 가까이를 붙잡고 있었던 문제. 오랜만에 코딩 문제를 풀어서 그런가 정말 풀리지가 않았다... 결국 구글링 찬스를 써서 약간의 힌트를 봤더니 해결되었다; 조건에서 (1) 자음이나 (2) 모음이 연속으로 세 개가 나오면 안 되고 (3) L을 반드시 포함해야 한다고 했으므로 문자를 자음, 모음, L 세 개로 나누어서 단순화할 수 있겠다. 다른 글에서도 찾을 수 있지만, 즐거운 단어.. 2021. 2. 16.

티스토리툴바