UEFI DXE 바이너리 취약점 분석기 프로젝트_5

edk2 맥북 빌드 정리 결과 Linux와 동일하되 컴파일 옵션을 gcc가 아닌 XCODE5 정도로 수정해주면 되어 이전 게시글을 참조하면 좋을 것 같다. Ghidra UEFI DXE 드라이버를 바이너리 단에서 P-Code로 올려서 취약점 분석을 하겠다는 계획에 Ghidra 공부는 필수적이였다. Ghidra는 미국 국가안보국(NSA)이 개발한 역어셈블러 프레임워크로, 위키리크스에 의해 정체가 공개되어 2019년에 오픈소스로 공개되었다. 비슷한 역할로 IDA Pro가 있고 일반적으로 IDA Pro가 업계 표준으로 꼽히지만, IDA Pro는 매우 비싼 가격을 가진 반면 Ghidra는 오픈 소스이면서 디스어셈블 및 디컴파일러 기능, 또한 java, python 등을 통한 스크립트 기능을 지원하여 분석 기능을 자동화할 수 있다. P-Code Ghidra에서 P-Code 설정을 켠 뒤 OVMF의 아무 DXE 드라이버를 열어본 화면이다. 다른 디스어셈블러와 달리 어셈블리 아래에 파란 글씨로 뭔가 잔뜩 있는 것을 볼 수 있다. 저 파란 코드들이 해당 어셈블리에 대한 P-Code다. Ghidra 공식 사이트에선 P-Code를 리버싱을 위해 디자인된 레지스터 전이 언어(출처)라고 설명하고 있다. 쉽게 설명하면 LLVM IR과 같이 고수준 언어와 기계어 사이 다리 역할을 하는 언어라고 볼 수 있다. 다만 차이점으로 P-Code는 다른 IR과 달리 기계어를 고수준 언어로 “올리는” 과정에서의 중간 언어로, 기계어가 가지는 복잡함을 걷어내고 추상화된 논리로 복원하는 것에 의의를 가진다. 사실 위 이미지만 보면 그냥 어셈블리어보다 복잡해 보이지만, 이는 해당 어셈블리어가 어떤 행동을 하는지 등을 풀어서 설명하는 것이다. 예를 들어 Call 명령어는 스택 주소를 8만큼 줄여라(INT_SUB) 돌아올 주소를 스택 메모리에 저장해라(STORE) 해당 함수로 가라(CALL) 이 세 가지 과정이 이뤄지는 것이다. 그리고 P-Code는 이를 풀어서 보여주는 것이다. 아마 우리는 여기서 실제로 오염된 데이터들을 전파시킬 수 있는 명령어들인 CALL, COPY, LOAD, STORE 등을 중점적으로 봐야하지 않을까…싶다. P-Code를 보면 (register, 0x20, 8), (const, 0x0, 1), (unique, 0x2c180, 1)과 같은 방식으로 값들이 표현이 되는 것을 볼 수 있다. 이는 (저장 방식, 오프셋, 크기)로 해석할 수 있으며, 각각 (register, 0x20, 8) : 레지스터 0x20번째 칸부터 8바이트 크기 (const, 0x0, 1) : 숫자 0(상수의 offset은 곧 값이다.) (unique, 0x2c180, 1) : Ghidra가 만든 임시변수 0x2c180번에 있는 1바이트짜리 임시 값 으로 해석할 수 있다. 그러므로 지금까지 정리한 내용 및 P-Code가 3-Address 기반의 IR을 따르고 있다는 점을 합쳐서 P-Code 몇 개를 해석해보면 (register, 0x20b, 1) = COPY (const, 0x0, 1) =>0x20b번째 레지스터에 숫자 0을 1바이트만큼 복사해라 (unique, 0x2c180, 8) = INT_AND (unique, 0x70280, 8), (const, 0xff, 8) => 0x70280번 임시변수와 0xff를 AND 연산한 결과를 0x2c180에 담아라 정도로 해석할 수 있을 것이다. 그래서 뭘 하지… 개인적으로 공부하며 5인 팀을 어떻게 나눠야할지 고민을 했다. 개인적으로 했던 생각은 취약점 분석 스크립트 개발(Using Ghidra Script)(2인) 탐지 검증을 위한 취약한 코드 생성 탐지 오판 여부 검증 결과 문서화 담당 의 역할 분담이 어떨까… 조심스레 생각해 보고 있고, 만약 이러한 형태라면 취약점 분석 로직을 스크립트화 하는 1번 역할을 담당해보고 싶다는 생각을 하고 있다. 분석 방법 고민 취약점 분석에 어떤 방법을 도입할지 고민하고 있다. 당장 생각나는 것들은 Pattern Matching, Taint Analysis, Symbolic Execution 정도가 생각나고, 해커가 공격의 진입점이 될 수 있는 부분(GetVariable() 함수를 통한 NVRAM 버퍼 오버플로우, CommBuffer 등)에 오염을 걸고 P-Code의 CALL, COPY, LOAD, STORE 등의 전파가 될 수 있는 부분들을 추적해나가며 찾아나가는 형식의 Taint Analysis를 통한 분석을 해보는 것으로 시작하는 것이 좋지 않을까 생각하고 있다. 하지만 CommBuffer 구조체가 드라이버 별로 다르게 생긴 것으로 알고 있어서 이 부분에 대한 파싱 부분에 고민을 하고 있다. 부가적으로는 WSMT가 있다 하더라도 SmmIsBufferOutsideSmmValid() 함수를 호출하는지 여부를 확인하기 위한 Pattern Matching 기능 정도를 부가적으로 가져갈 수 있지 않을까 라는 생각을 하고 있다. GetVariable() 함수 찾기 Ghidra와 친해질 겸과 동시에 실제로 Buffer Overflow를 일으킬 가능성이 높은 함수인 GetVariable() 함수의 빌드 후 올라간 주소를 직접 하나씩 들어가보며 찾아보았다. 해당 부분은 취약점 분석기 스크립트 제작에 있어 중요한 부분이 되지 않을까 싶다.. GetVariable() 함수는 NVRAM(비휘발성 메모리) 내의 원하는 데이터를 읽어 인자로 넣어준 메모리 버퍼에 값을 채워주는 함수다. 이는 gRT(Global Runtime Services Table) 내에 구현되어있는 함수로, DXE 드라이버들이 메모리 내 상태를 읽을 때 해당 함수를 호출해 사용하는 중요한 함수지만, 함수 구현 코드를 보면 EFI_STATUS EFIAPI VariableServiceGetVariable ( IN CHAR16 *VariableName, IN EFI_GUID *VendorGuid, OUT UINT32 *Attributes OPTIONAL, IN OUT UINTN *DataSize, OUT VOID *Data OPTIONAL ) { ... if (*DataSize >= VarDataSize) { if (Data == NULL) { Status = EFI_INVALID_PARAMETER; goto Done; } CopyMem (Data, GetVariableDataPtr (Variable.CurrPtr, mVariableModuleGlobal->VariableGlobal.AuthFormat), VarDataSize); ... } ... } 이 부분에서 CopyMem 함수가 문제가 된다. 해당 함수의 Data는 값을 써넣을 목적지 역할을 수행하지만 해당 목적지가 안전한 영역인지에 대한 처리를 수행하는 로직은 없는데, 예를 들어 해커가 특정 변수 크기를 키우고 그 곳에 Payload를 집어넣은 뒤 검증 절차를 밟지 않은 SMM 핸들러를 실행시켜 GetVariable() 함수를 통해 해당 Payload를 읽어오면 Payload가 리턴 주소 등을 덮어씌워버리면서 Ring -2 권한으로 실행되는 것이다. 그러므로 해당 함수를 호출하는 SMM 핸들러에 이를 처리하는 SmmIsBufferOutsideSmmValid() 함수가 없다면 문제가 발생할 수 있을 것이다. 한번 Ghidra에서 VariableSmm이란 파일에서 GetVariable() 함수를 찾아보았다. 먼저 해당 파일을 UEFITool을 통해 추출하고, 이 파일을 Ghidra를 통해 열어보았다. 잘 모르겠지만 entry라고 적혀있는 것으로 보았을 떄 시작 지점임을 알 수 있었다. 시작 지점은 edk2/MdePkg/Library/UefiApplicationEntryPoint/ApplicationEntryPoint.c 파일에 적혀 있었으며, 구조는 EFI_STATUS EFIAPI _ModuleEntryPoint ( IN EFI_HANDLE ImageHandle, IN EFI_SYSTEM_TABLE *SystemTable ) { EFI_STATUS Status; if (_gUefiDriverRevision != 0) { if (SystemTable->Hdr.Revision < _gUefiDriverRevision) { return EFI_INCOMPATIBLE_VERSION; } } ProcessLibraryConstructorList (ImageHandle, SystemTable); Status = ProcessModuleEntryPointList (ImageHandle, SystemTable); ProcessLibraryDestructorList (ImageHandle, SystemTable); return Status; } 다음과 같았다. 그러므로 ProcessModuleEntryPointList() 함수에 들어가보기로 했다. 위 함수에 해당하는 FUN_00008f6f 함수로 가보자. 해당 함수 역시 굉장히 단순한 구조로 이뤄져있었고, 그 외 특이점으로 “AutoGen.c” 라는 인자를 넣은 에러 처리 함수를 호출하는 것을 볼 수 있는데, 해당 링크에 보면 빌드 시스템이 자동으로 Wrapper로 감싼 것을 볼 수 있었다. 다시 한번 FUN_0000565d 함수로 이동해보자. FUN_0000565d 함수 역시 껍질만 있는 함수였고, 해당 함수가 FUN_000065d8을 호출하는 것을 보고 들어갔더니 드디어 무언가 코드가 잔뜩 나온 것을 볼 수 있었다. 여기부턴 Gemini의 도움을 받아서 해결해보았다. DAT_00090650이 SMM 모드 전용 시스템 테이블인 gMmst(Global SMM System Table)라 하여 Ghidra에 ghidra-firmware-utils라는 플러그인을 설치한 뒤 DAT_00090650의 이름을 gMmst, 타입을 EFI_SMM_SYSTEM_TABLE2 *로 변경한 결과 VariableSmm.c 파일의 MmVariableServiceInitialize() 함수와 동일함을 알 수 있었다. 해당 C 코드를 보면 gMmst의 SmmInstallProtocolInterface 함수의 네번째 인자가 gSmmVariable을 받는 것을 볼 수 있고, 해당 gSmmVariable의 첫 번째 인자가 GetVariable()임을 알 수 있었고, 두 번째 인자가 GUID임을 알 수 있다. 해당 논리를 따라 타고 들어가 확인해본 결과 해당 함수의 위치 및 GUID를 알아낼 수 있었다! 다음으로는 Gemini가 위 분석을 Ghidra 스크립트화도 가능하다는 이야기를 해서 한번 시도해보지 않을까…싶다

졸업프로젝트 · 2026-01-28

UEFI DXE 바이너리 취약점 분석기 프로젝트_4

WSMT 중첩된 포인터에 따른 SMRAM 오염을 설명하기 전 WSMT에 대해 공부를 할 필요가 있었다. WSMT는 Windows SMM Security Mitigation Table의 줄임말로써 지난 시간에 이야기했던 ACPI 테이블 중 하나다. 이는 시스템 펌웨어가 SMM 소프트웨어에서 보안이 잘 지켜졌는지를 확인하도록 OS에게 이야기하는 역할이라고 볼 수 있다. WSMT의 구조로, 총 3가지 Flag가 있는 것을 확인할 수 있고, 각 플래그들은 FIXED_COMM_BUFFERS : OS가 지정한 고정 CommBuffer만 사용하는가 COMM_BUFFER_NESTED_PTR_PROTECTION : CommBuffer의 중첩 포인터까지 검증하는가 SYSTEM_RESOURCE_PROTECTION : 시스템 주요 설정들을 잘 보호하는가 세 가지를 담고 있다. 여기서 큰 문제가 발생하는데, WSMT는 위 세가지 문제에 대해 “검증”을 하는 것이 아닌 각 제조사가 해당 플래그를 켰는지 “확인”만 한다. 즉 제조사들은 이를 준수하지 않았더라도 Flag를 True로 뒀다면 OS는 그것을 믿고 별도 검증 기능 없이 바로 해당 핸들러를 수행하게 된다. SMRAM Corruption using Nested Pointer 중첩된 포인터를 이용한 SMRAM 오염은 CommBuffer를 통해 값을 받고, 또 CommBuffer에 값을 저장할 때 이중(또는 그 이상) 포인터를 사용하는 과정에서 생기는 문제를 의미한다. 아래 예제는 CVE-2023-5058 사례로, 후지쯔 펌웨어, 또는 레노버 Yoga Slim 7 Pro에 들어간 UEFI에 발생한 취약점이다. EFI_STATUS __fastcall ChildSwSmiHandler( EFI_HANDLE DispatchHandle, const void *Context, _QWORD *CommBuffer, UINTN *CommBufferSize) { ... Ptr2 = (CommBuffer[22] + 8); for ( i = *Ptr2; i != Ptr2; i = *i ) { i[24] = 0; // unchecked write (SMRAM corruption) i[4] = 0; // unchecked write (SMRAM corruption) i[6] = 0; // unchecked write (SMRAM corruption) } ... } 코드의 일부다. 위 코드를 보면 Ptr2에 CommBuffer가, 그리고 그 안에 있는 값들을 별도 검사 없이 사용하는 모습을 볼 수 있다. 물론 CommBuffer가 SMRAM에 침범하는지 검사가 이뤄졌을 것이고, 통과가 되어 CommBuffer를 사용했을 것이다. 하지만 만약 해커가 CommBuffer 내부 24, 4, 6번 등에 악의적인 Payload를 심었다면 해당 핸들러는 CommBuffer만 검사하고 내부 요소들은 검사하지 않았으므로 해당 Payload들이 SMM 권한을 얻은 채 실행될 것이다. 본격 UEFI 개발 환경 테스트해보기 아직 앞으로 어떻게 연구가 이뤄질지 모르지만 인터넷과 제미나이 등과 함께 UEFI 개발 환경을 만들어보았다. 환경은 노트북 : MacBook M4 Pro 16 가상환경 : VirtualBox, Ubuntu 24.04.02 LTS UEFI : Tianocore edk2 기존 계획은 상대적 구형 버전으로 다운받으려고 했지만 오류가 너무나도 많이 터지는 바람에….. 일단은 최신 버전으로 만들어 보았다. (자료 참고는 여기와 여기를 참고했습니다.) 먼저 터미널에서 의존성 패키지를 설치해준다. sudo apt install build-essential uuid-dev acpica-tools git nasm python3-setuptools gcc-x86-64-linux-gnu build-essential : 빌드 도구(make 등) 모음 uuid-dev : GUID 식별 라이브러리 acpica-tools : ACPI 컴파일러 nasm : 어셈블리 컴파일러 gcc-x86-64-linux-gnu : ARM 환경에서 x86-64 버전으로 컴파일하기 위해 설치 이후 폴더를 하나 만들고 해당 폴더 안에서 edk2 파일을 clone 해준다. mkdir uefi_test cd uefi_test git clone https://github.com/tianocore/edk2.git cd edk2 이후 서브모듈을 최신화해주고 빌드 툴을 컴파일해준다. git submodule --init --recursive make -C BaseTools 이후 환경설정 파일을 생성한 뒤 빌드를 진행한다. source edksetup.sh build -p OvmfPkg/OvmfPkgX64.dsc -a X64 -t GCC5 (이 과정에서 ARM 기반이라 그런지 오류가 매우 많이 발생했습니다. 이 때 저는 Conf/target.txt를 열어 다운받았던 gcc-x86-64-linux-gnu로 사용 컴파일러들을 바꾸는 등의 작업을 통해 설치할 수 있었습니다.) 이후 빌드가 성공하면 Build/OvmfX64/DEBUG_GCC5/FV 내에 Ovmf.fd라는 파일이 생기게 된다. 이 파일을 QEMU를 통해 실행할 수 있다. qemu-system-x86_64 \ -bios Build/OvmfX64/DEBUG_GCC5/FV/OVMF.fd \ -net none 실행에 성공하면 다음과 같은 화면이 나오는 것을 볼 수 있다! 한 가지 아쉬운 점으론 취약점 분석을 할 예정인 만큼 최신 버전이 아닌 구버전을 다운받아 보려 했는데 오류가 매우 많이 발생하여 아쉬웠다. 아마 다음 주 목표는 구버전 다운로드를 목표로 하지 않을까 싶다. (2026.01.26 11시 45분. 가상환경 없이 맥 환경에서 2021년 2월 버전 EDK2 빌드 성공!) 내 UEFI에 간단한 파일 올려보기 이제 여기서 UEFI Shell 부분에 코드를 추가해서 내 맘대로 일부 수정을 해보고 빌드를 해보자. 내가 수정을 해볼 부분은 ShellPkg/Application/Shell 내의 Shell.c 파일로, 해당 파일은 UEFI의 SHell을 담당하고 있는 파일이라고 볼 수 있다. 이 파일 내의 UefiMain() 함수를 찾아준다. UefiMain 함수는 마치 C나 Rust의 main() 처럼 해당 UEFI 파일의 시작점이 되는 부분이라고 볼 수 있다. 이 부분에 Print() 함수를 통해 내가 원하는 것을 출력시킬 것이다. (Print() 함수는 C의 printf()와 비슷한 EDK2에서 제공하는 출력 함수다. 출력할 땐 L을 붙여 글자당 2바이트임을 알려준다.) 위와 같이 UefiMain 함수 내에 다음과 같이 입력한 뒤 저장하고 다시 빌드를 한 뒤 QEMU로 UEFI를 실행해보자. build -p OvmfPkg/OvmfPkgX64.dsc -a X64 -t GCC5 qemu-system-x86_64 -bios Build/OvmfX64/DEBUG_GCC5/FV/OVMF.fd -net none Shell이 시작될 때 내가 입력한 내용이 출력되는 것을 볼 수 있다!

졸업프로젝트 · 2026-01-22

러스트 표준 입출력 방법 정리

최근에 러스트를 공부하기 시작하면서 러스트로 백준을 풀어보려 하고 있다. 이 과정에서 러스트의 입출력은 다른 언어보다 조금 더 복잡하다고 느끼고 있다. 그래서 개인적인 기록 용도로 입출력 방법을 정리해두고자 한다. 입력 한 줄 입력 use std::io::{self, Read}; fn main() { let mut input = String::new(); io::stdin().read_line(&mut input).unwrap(); } String 변수를 하나 만든 뒤 해당 변수 값을 받아서 read_line으로 받은 뒤 unwrap()으로 푼다. 여러 줄 입력 use::std::io::{self, Read}; fn main() { let mut input = String::new(); io::stdin().read_line(&mut input).unwrap(); let n = input.trim().parse::<usize>().unwrap(); for _ in 0..n { input.clear(); io::stdin().read_line(&mut input).unwrap(); } } 처음에는 몇 개의 줄을 입력받을 것인지 숫자를 입력하고, 반복문으로 그 숫자만큼 줄을 입력받는 방식으로 구현했다. 여러 숫자 입력 use std::io::{stdin, Read}; fn main() { let mut input = String::new(); stdin().read_line(&mut input).unwrap(); let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>); let n = input.next().unwrap(); } 숫자를 공백 단위(1 3 4 5 6…)과 같이 입력받았을 때 사용하는 방식이다. 여기서 usize로 파싱하는 부분만 빠지면 문자열을 공백으로 입력받을 수도 있다. 출력 한 줄 출력 fn main() { let x = 3; println!("{x}"); }

Rust · 2026-01-22

UEFI DXE 바이너리 취약점 분석기 프로젝트_3

Memory Map 메모리 맵은 시스템의 RAM과 특정 영역의 분포를 나타낸 표로, OS가 메모리를 정상적으로 사용할 수 있도록 UEFI는 이 정보를 커널에 전달한다. 쉽게 생각해서 여기부터 여기까지는 중요한 부분이야!, 여기부터 여기까지는 사용해도 돼! 를 OS에게 알려주는 부분이라고 볼 수 있다. 흔히 생각하는 버퍼 오버플로우나 Null-Pointer 역참조, 또는 지난 시간에 공부했던 Callout 공격이나 CommBuffer 공격들은 대부분 결국 엉뚱한 메모리를 건들면서 생기는 문제들이라 볼 수 있다. Windows에서 vmware를 통해 직접 EFI Shell을 실행한 뒤 memmap 명령어를 통해 메모리를 관찰한 결과다. 뭔가 정말 많이 떠있어 읽기 힘든 것을 볼 수 있다. UEFI.org에서 가져온 각 영역에 대한 설명이다. 내용들이 매우 많아보이지만 차근차근 보자. 가장 먼저 Mnemonic 부분이다. 이 부분은 각 영역이 무엇인지에 대한 이름 정도라고 볼 수 있다. Type 이름 설명 0 EfiReservedMemoryType 아무튼 예약된 메모리 1 EfiLoaderCode OS 로더 코드가 올라갔던 곳 2 EfiLoaderData OS 로더가 실행중에 쓴 데이터 영역 3 EfiBootServicesCode 부팅 단계에서만 필요한 드라이버들의 코드 4 EfiBootServicesData 부팅 단계에서만 필요한 드라이버들의 데이터 5 EfiRuntimeServicesCode OS 실행 중에도 불려야하는 서비스들의 코드 6 EfiRuntimeServicesData OS 실행 중에도 불려야하는 서비스들의 데이터 7 EfiConventionalMemory 여유 공간 8 EfiUnusableMemory 메모리 테스트 중 오류가 발견된 공간 9 EfiACPIReclaimMemory ACPI 테이블의 공간 10 EfiACPIMemoryNVS ACPI NVS 메모리 11 EfiMemoryMappedIO 하드웨어 장치의 레지스터와 연결된 주소 12 EfiMemoryMappedIOPortSpace I/O 포트의 번역기 13 EfiPalCode 서버용 CPU의 펌웨어 코드 14 EfiPersistentMemory 영구 메모리 구역 (출처) 오른쪽 ACPI Address Range Type 부분은 일명 OS가 이 구간은 써도 되는지에 대해 UEFI가 OS에 알려주는 부분이다. AddressRangeReserved : UEFI가 사용하고 있는 메모리. 맘대로 수정하면 안된다 AddressRangeMemory : 부팅이 끝난 뒤 초기화되는 메모리. 마음대로 사용 가능 AddressRangeACPI : ACPI 테이블(하드웨어 정보 등에 관한 테이블). 정보를 다 가져간 뒤엔 OS 사용 가능 AddressRangeNVS : ACPI NVS 메모리(시스템 전원 관리 및 절전 모드 작동 등에 사용). 맘대로 수정 불가 AddressRangePersistentMemory : 비휘발성. 컴퓨터를 껐다 켜도 데이터가 남아있는 구역 (출처) 지난 주차에서 공부했던 내용을 생각하며 우리가 여기서 봐야 하는건 SMM 코드가 드라이버가 외부에 있는 주소를 사용하려 하는가 정도가 될 것이라 생각한다. 지난 시간에 공부했든 SMM 코드는 SMRAM 내 코드가 아니면 실행하면 안된다. 하지만 이 SMM이 BS_Code나 RT_Code를 실행한다면? 만약 해커가 악의적으로 Ring 0 권한을 탈취 후 RT_Code의 쓰기 방지를 풀고 Payload를 심었거나, 무방비 구역인 BS_Code구역에 Payload를 심었고, 이 부분을 SMM이 Call을 한다면? 이게 바로 SMM Callouts 공격이 되는 것이다. 이 링크는 AMD의 SMM Callout에 대한 실제 CVE로, 입력 버퍼에 유효성 검사가 존재하지 않아 SMM Callout 취약점이 발생할 수도 있다는 것을 의미한다. Save State 지난 시간 SMM에 대해 공부했을 때 Save State에 대한 부분을 작성하지 않았던 것 같아 추가적으로 작성하기로 하였다. Save State는 SMRAM의 일부분으로, SMRAM의 어떤 부분을 덮어쓰면 위험한데? 라는 질문의 대답이 될 수 있을 것이다. (출처) SMRAM의 구조이다. Save State는 SMI가 걸려 SMM 모드로 들어가는 순간의 레지스터 값 등을 Save State라는 곳에 저장하고, 일을 마치면 저장한 값을 다시 불러오는 데에 사용한다. Low SMRAM Corruption (출처) 지난 시간 공부했던 CommBuffer 공격이 SMM이 있는 SMRAM을 침범하는 공격이라고 하였다. 물론 CommBuffer를 SMRAM에 할당받지 못하도록 방어하는 다양한 보호 기법들이 있다. SmmIsBufferOutsideSmmValid 함수가 바로 이런 보호 기법 중 하나다. SmmIsBufferOutsideSmmValid 함수는 인텔의 표준 UEFI 레퍼런스 구현체인 EDK2에 구현되어있는 함수로, CommBuffer가 SMRAM을 침범했는지 여부를 확인해주는 함수다. 가끔 SmmIsBufferOutsideSmmValid 함수를 개발 과정에서 까먹고 넣지 않는 경우가 있거나, 또는 CommBuffer 크기를 넘겨주지 않는 경우, 또는 핸들러 자체가 너무 허술할 경우 등이 있는데, 이런 경우 공격 대상이 될 수 있다. 대표적 사례로 Low SMRAM Corruption 공격이 있다. 위 함수와 같은 핸들러가 취약한 SMI 핸들러의 예시가 될 수 있는데, 빨간 박스를 보면 CommBuffer의 범위에 따른 유효성 검사 없이 그냥 채워져만 있으면 통과를 시켜준다. 또한 노란 박스를 통해 CommBuffer의 시작 주소에 64비트, 즉 8바이트를 냅다 주는 것을 알 수 있다! 이 핸들러에 Low SMRAM 공격을 할 수 있다. 간략하게 순서는 다음과 같다. CommBuffer를 SMRAM 바로 밑에 위치시킨다.(SMRAM - 1) CommBuffer의 크기를 1바이트와 같이 작은 숫자로 설정한다. 취약한 SMI 핸들러를 작동시킨다. 그렇게 되면 위 그림과 같이 겉으로 보기엔 아무 이상 없는 것처럼 보이므로 SmmIsBufferOutsideSmmValid 함수도 통과하여 SMI 핸들러로 들어오게 될 것이다. 그런데 이 핸들러가 SMRAM 한 칸 밑에 있는 CommBuffer를 8바이트로 늘려버린다면? 위와 같이 SMRAM을 CommBuffer가 침범하게 된다. Nested Pointer를 통한 SMRAM 침범 공격 문제 공부중…

졸업프로젝트 · 2026-01-13

UEFI DXE 바이너리 취약점 분석기 프로젝트_2

SMM SMM(System Management Mode)는 x86 및 x86-64 프로세서의 작동 모드로, 해당 모드는 OS가 실행되는 동안 OS의 아래에서 저수준 시스템 관리 작업을 수행하는 데 사용된다. 초기엔 부팅 관련 Phase에서만 사용되었지만 요즘에는 하드웨어 보호 및 제어, 각 제조사별 하드웨어 기능(키보드 백라이트 조절, 배터리 수명 모드 등)과 같은 곳에서도 사용된다. SMM의 설계도를 보면 SMM은 내부에서만 사용되는 것이 아닌 일반 모드들과도 연결이 되는데, 이 일반 모드와 SMM을 연결해주는 것이 바로 SMI(System Management Interrupt)이다. SMI가 발생하면 SMRAM이라는 SMM이 있는 전용 메모리 공간으로 들어가 SMM을 불러오는 것이다. 이 때 SMM에게 이 정보를 같이 처리해주세요! 라는 정보를 함께 넘기게 되는데 이를 CommBuffer라고 한다. SMM이 이번 프로젝트에서 왜 중요하다고 생각한지 설명하기 전 CPU의 특권 레벨(Privilege Level)에 대해 설명할 필요가 있다. 특권 레벨이란 어떤 시점에서의 CPU의 권한 상태를 나타내는지, 다시 말해 CPU가 어떤 명령을 실행할 수 있는지, 메모리 어느 범위까지 도달할 수 있는지의 정도를 말한다. 특권 레벨은 Ring 0~3까지 구성되며, 더 낮은 숫자로 내려갈수록 할 수 있는 것들이 많아진다. Ring 3은 우리가 흔히 사용하는 카카오톡과 같은 응용 프로그램이 해당되며, 여기선 하드웨어 조작, 타 프로그렘 메모리 읽기 등이 금지된다. Ring 0은 커널 모드로, OS, 하드웨어 드라이버 등이 이 단계에 해당된다. 여기선 모든 메모리의 접근, 하드웨어 직접 접근, Ring 3 프로그램의 강제 종료 등의 컴퓨터 내에서의 대부분의 것들을 수행할 수 있다. (카카오톡이나 줌 등에서 웹캠 키고 마이크 킬 수 있잖아요! : 그것은 Ring 3이 Ring 0에게 켜달라고 요청을 하는 것이다.) 근데 여기서 SMM은 Ring 0인 커널보다도 더 낮은 숫자인 Ring -2에 위치한다. (Ring -1은 OS를 담당하는 가상화 하이퍼바이저를 의미한다고 한다.) Ring -2에 해당하는 SMM이 실행되면 OS 마저도 멈추고 SMM에 해당하는 작업을 처리하게 된다. 이는 메모리 및 장치 리소스에 대한 제한 없는 접근 권한을 가지므로 이 부분이 악성 코드들의 공격 경로로 자주 사용된다. (출처) CommBuffer 공격 다시 SMM으로 돌아와보자. SMM이 존재하는 SMRAM은 물리적으론 RAM에 존재하지만 논리적으로는 격리가 되어 만약 이 공간에 Ring -2보다 높은 숫자를 가진 레벨으로 접근하려 하면 쓰레기 값만 보여주거나 칩셋에서 자체 차단을 하게 된다. 그런데 만약 해커가 악의적 목적으로 CommBuffer에 덮어씌울 주소로 SMRAM 내부 주소를 입력한다면? 그리고 SMM이 해당 주소에 대한 검사를 하지 않고 바로 받아드린다면? 외부 오염된 데이터가 SMRAM으로 들어오면서 해커가 Ring -2의 권한을 탈취할 수도 있는 것이다. SMM Callouts SMM Callouts 공격은 위 CommBuffer 공격과 반대로 SMM Code가 SMRAM 경계 밖에 있는 함수를 호출할 때 발생한다. 원래 SMM Code는 SMRAM 내에서만 실행이 되어야 한다. 하지만 SMM Code가 외부에 있는 함수를 호출한다면? 그리고 그 외부 함수 주소를 타고 가보니 해커가 심어둔 악성코드의 주소라면? 악성 코드가 Ring -2라는 최상위 권한으로 실행되게 되는 것이다. 악성코드가 Ring -2로 실행되게 된다면 OS보다 더 높은 권한으로 실행됨으로써 해당 악성코드는 OS를 아무리 포맷해도 하드디스크가 아닌 메인보드 펌웨어 칩에 실리게 되어 치료가 불가능해질 수도 있다. 또한 악성코드를 탐지하는 백신들 역시 Ring 0에서 실행되므로 Ring -2에 실린 악성코드를 탐지할 수도 없게 된다. 그리고 이를 방지하기 위해 우리가 만들 분석기의 역할은 두가지. 1. 들어온 CommBuffer에 대한 검사를 수행하는가? 2. SMM Code가 외부 함수를 호출하려고 하는가? 를 감지할 수 있다면 훌륭한 분석기가 되지 않을까 생각하고 있다. PE UEFI의 분석을 위해서는 PE에 대한 공부가 필수적이라 생각한다. 지난번에 뜯어본 .efi 파일의 맨 처음 부분을 보면 MZ라는 것이 적혀있는 것을 볼 수 있는데, MZ가 바로 PE파일임을 나타내는 signature이다. 이를 통해 UEFI의 DXE 드라이버들이나 SMM 모듈들은 PE의 구조를 따르는 것을 알 수 있다. PE를 통해서 알 수 있는 정보들이 매우 많은데, 1. 섹션의 구분을 알 수 있다. 몇번지부터 code인지, 몇번지부터 data인지 등을 여기서 알 수 있다. 2. 해당 코드의 진짜 시작점(AddressOfEntryPoint)을 알아낼 수 있다. 3. 주소 재배치 계산 정보가 여기에 담겨있다. 이 부분이 틀리면 메모리 번지수 계산이 전부 망가지게 된다. PE 헤더에 어떤 내용들이 담겨있는지를 여기서 전부 다 다루진 않지만, UEFI뿐 아니라 PE 전반적으로 중요한 부분들을 위주로 다뤄보겠다. IMAGE_DOS_HEADER 이곳은 DOS 파일과의 하위 호환성을 위한 공간이다. Signature(e_magic) : “MZ”가 아닐 경우 해당 파일을 실행하지 않는다. Offset to New EXE Header : 실제 PE 헤더의 시작 Offset이 담겨있다. IMAGE_FILE_HEADER 여기엔 해당 PE 파일의 기본적인 정보들이 담겨있다. Machine : 컴퓨터 아키텍처의 유형이 적혀있다. x64인지, x86인지, ARM인지 등이 담겨있다. Number Of Sections : .text, .data, .reloc와 같은 섹션이 몇 개 있는지를 알려준다. Size of Optional Header : 다음에 나올 IMAGE_OPTIONAL_HEADER의 크기를 나타낸다. Characterstics : 해당 파일의 속성값이 담겨있다. IMAGE_OPTIONAL_HEADER 여기엔 해당 PE 파일의 부가적이지만 분석에 필수적인 정보들이 담겨있다. Magic : 32비트인지(0x10B), 64비트인지(0x20B)가 적혀있다. Size of Code : 코드의 크기를 나타낸다. AddressOfEntryPoint : 실제 파일이 메모리에서 시작되는 지점을 나타낸다. BaseOfCode : 실제 코드가 시작되는 번지수를 나타낸다. ImageBase : 실제 가상 메모리에 올라가는 번지수를 나타낸다. Section Alignment : 섹션 및 파일의 정렬을 위한 최소 단위를 나타낸다. Size of Image : 해당 파일이 메모리에 로딩된 순간의 전체 크기를 나타낸다. SubSystem : 해당 파일이 GUI인지, 드라이버인지, CLI 등인지를 나타낸다. Number of Data Directiory : DataDirectory의 개수를 나타낸다. 이 때 BaseOfCode, AddressOfEntryPoint, ImageBase의 차이가 처음에 헷갈렸는데, ImageBase : 실제 가상 메모리에 올라가는 번지수를, BaseOfCode : ImageBase에서 코드부분 시작 지점까지 얼마나 떨어져 있는지를, AddressOfEntryPoint : 실제 프로그램을 실행할 때 제일 처음 시작되는 부분(Main함수)이 얼마나 떨어져 있는지를 나타낸다. IMAGE_SECTION_HEADER 여기선 각 Section들의 속성들을 나타낸다. Virtual Size : 메모리 내에서 해당 섹션이 차지하는 크기를 나타낸다. RVA : 메모리에서 해당 섹션의 시작 주소의 offset을 나타낸다.(RVA : Relative Virtual Address) Size of Raw Data : 파일에서의 섹션의 크기를 나타낸다. Pointer to Raw data : 파일에서의 해당 섹션의 offset을 나타낸다. Characteristics : 해당 섹션의 속성(읽기 전용인지, 읽고 쓰기 전부 가능한지 등)을 나타낸다. 이 때 Section으론 .text : 프로그램의 실행 코드가 담겨있음. .data : 읽고 쓰기 모두 가능한 Data Section. 초기화된 전역변수 및 static 변수 위치. .rdata : 읽기 전용 Data Section. const 및 문자열 상수 등이 위치. .bss : 초기화되지 않은 전역변수가 담겨있음. .idata : Import할 DLL 및 API 관련 정보가 담긴 Section. IAT가 여기에 위치한다. .didat : DLL 단위 지연 로딩을 위한 Section. .edata : Export할 API가 담긴 Section. .rsrc : 리소스 관련 Data가 담긴 Section(아이콘, 커서 등). .reloc : 기본 재배치 정보들을 담고 있는 Section. 주소 계산법 PE에 적혀있는 주소들은 가상 주소에 해당된다. 해당 주소는 실제 메모리에 올라가면 주소가 바뀌게 되므로, 적혀있는 주소를 그대로 참조하는 것이 아닌 실제 주소와 가상 주소 사이 Offset을 계산해준 뒤 해당 Offset만큼 더해준 위치에 접근을 해주면 된다. 해당 Offset의 계산은 다음과 같다. Offset = Load Address - ImageBase 하지만 이 Offset을 무작정 써먹을 순 없고, 약간의 계산을 추가적으로 해줘야 한다. 일반적으로 DataDirectory의 6번째(DataDirectory[5])에 재배치에 관한 테이블이 존재한다. 위 그림이 바로 재배치 테이블이다. 해당 테이블의 data에 있는 값들이 바로 재배치를 해야 할 RVA 주소들로, 이 주소를 파일 위치(RAW)로 바꾼 뒤 해당 주소가 가르키는 값에 Offset을 더하는 과정을 반복해줘야 한다. 이 때 RVA를 RAW로 바꾸는 공식은 아래와 같다. RAW = RVA - VA + PTRD 이 때 VA는 해당 RVA가 속한 Section 헤더의 RVA를, PTRD는 해당 Section 헤더의 Pointer To Raw Data를 뜻한다.

졸업프로젝트 · 2026-01-02

UEFI DXE 바이너리 취약점 분석기 프로젝트_1

UEFI란 UEFI(Unified Extensible Firmware Interface, 통일 확장 펌웨어 인터페이스)란 기존 BIOS를 대체하기 위해 나온 규격이다. 기존 Legacy BIOS는 CPI 실행 과정에서 16비트 모드(키보드 탐색만 지원)에서만 실행이 될 수 있었다. 이는 메모리 주소 공간이 1MB로 제한되므로 CPU의 속도가 아무리 빨라져도 부팅 초기화 단계에서 구식 CPU의 수준에서만 동작할 수 있었다. 구형 BIOS의 모습이다. 마우스 등의 장치로는 불가능하고 오직 키보드로만 탐색할 수 있었다. 또한 BIOS가 사용하는 MBR 방식은 주소를 32비트로 관리함에 따라 최대 2TB 용량의 저장 장치만 사용할 수 있었다. 이런 문제를 해결하기 위해 UEFI가 등장했다고 보면 될 것 같다. 내용은 이 링크를 통해 많이 공부하였다. UEFI 부팅 순서 (BIOS의 부팅 순서는 따로 설명하지 않겠다.) UEFI 부팅 순서를 나타낸 그림이다. 1. SEC(Security) 단계 시스템 전원이 켜지자마자 가장 먼저 실행되는 단계. CPU가 전원을 받아 reset vector에 처음으로 명령어를 받아온다. 이 과정은 16비트 real mode의 instruction을 실행하는데, 이 작업은 프로세서를 보호 모드로 전환한다. 또한 갓 컴퓨터에 전원이 들어온 상태이므로 메인 메모리가 아직 초기화되지 않았으므로 CPU의 L1/L2 캐시를 임시 RAM으로 사용해 C 코드를 실행할 준비를 하며, 그리고 초기 펌웨어 코드가 변조되지 않았는지 검증하는 Pre-Verifier 단계를 수행한다. 2. PEI(Pre-EFI Initialization) 단계 이 단계에서 메인 메모리를 포함한 칩셋들을 초기화한다. 3. DXE(Driver Execution Enviroment) 단계 우리가 중점적으로 볼 부분이다. PEI 단계에서 메모리가 초기화되어 사용할 수 있는 상태가 되었으므로 본격적으로 드라이버들을 Load한다. 실행 파일은 PE32, PE32+(64비트) 파일이 사용된다. 이 단계에서 각 모듈들을 열거하고 실행하는 Dispatcher가 존재하는데, 각 모듈들은 USB, 그래픽, 네트워크, 파일 시스템 등 기능들을 불러오게 된다. (*HOB(Hand-Off Block) : PEI에서 DXE로 넘어갈 때 전달되는 구조체로, 이 안에 메모리 유효 범위, 부팅 볼륨 등의 정보가 담겨있으므로 이 부분을 분석하는 것이 시작점이 되지 않을까… 싶다) 4. BDS(Boot Device Selection) 단계 부팅 정책에 따라 GPT 디스크 및 EFI 시스템 파티션(OS 부트로더)을 찾는다. 이 때 윈도우라면 bootmgfw.efi, 리눅스라면 grub.efi 등 각 운영체제별 부트로더 정보들이 있고, 이를 찾아 메모리에 로드하는 단계가 된다. 우리가 컴퓨터를 켜서 BIOS 설정 환경으로 넘어가기 위해 F2나 Del키를 연타하게 되는데 이 설정 환경이 여기서 실행되게 된다. 5. TSL(Transient System Load) 단계 OS 부트로더는 이미 실행중이지만, 이 단계까지 아직 UEFI의 Boot Services를 이용할 수 있다. 부트로더가 최종적으로 커널 메모리에 올라가 실행 환경이 구축되었다면 ExitBootServices() 함수를 호출하여 제어권을 OS에 완벽히 넘기고 UEFI는 부트 프로세스를 종료한다. 6. RT(Run Time) 단계 여기부턴 OS가 완전히 컴퓨터의 제어권을 잡고 실행하게 된다. UEFI는 이 때 시스템 시간 가져오기, 시스템 리셋, 디바이스 드라이버 로드 등 일부 Runtime Service들만 사용하게 된다. 7. AL(After Life) 단계 시스템이 종료되는 시점이다. 간단히 실제 DXE 살펴보기 제미나이와 함께 간단하게 DXE .efi 파일이 어떻게 되어있는지 살펴보았다. 사용 모델은 DELL XPS 15 9560의 UEFI를 여기서 다운받았다. 다운을 받으면 .exe 형태의 파일이 다운받아진다. 이를 추출하기 위해 깃허브에 올라와있는 추출기를 다운받아 실행하였다. 추출이 완료되면 폴더가 하나 생기고 폴더 안에는 위 이미지와 같이 추출된 펌웨어들이 .bin의 형태로 저장되어 있는 것을 볼 수 있다. 이 중 “System BIOS with BIOS Guard v1.24.0.bin” 이란 파일이 분석 대상이라고 판단. 이 파일을 UEFITool을 통해 열어보았다. 해당 파일을 UEFITool을 통해 열었을 때 위와 같은 화면이 나옴을 알 수 있었다. 앞으로 이 부분들을 우리가 분석해나가야 할 것들이 될 것이다.

졸업프로젝트 · 2025-12-31

[백준, python] 14502번 - 연구소

백준 문제풀이 시작 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다. 2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다. 2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 바이러스가 퍼진 뒤의 모습은 아래와 같다. 2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. 빈 칸의 개수는 3개 이상이다. 출력 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다. 풀이 풀이 확인하기 해당 문제는 DFS를 통해 풀 수 있다. 문제에서 제시한 지도의 넓이가 넓지 않으므로 벽을 세울 수 있는 모든 경우에 대해 바이러스를 DFS를 통해 퍼트리고 각 경우에 안전 영역이 얼마나 남는가를 계산해 가장 많이 안전 영역이 확보된 경우를 계산하여 출력하면 된다. import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) lis = [] after = [[0] * m for _ in range(n)] for _ in range(n): lis.append(list(map(int, input().rstrip().split()))) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] result = 0 def virus(x, y): for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx >= 0 and nx < n and ny >= 0 and ny < m: if(after[nx][ny] == 0): after[nx][ny] = 2 virus(nx, ny) def get_score(): score = 0 for i in range(n): for j in range(m): if(after[i][j] == 0): score += 1 return score def dfs(count): global result if count == 3: for i in range(n): for j in range(m): after[i][j] = lis[i][j] for i in range(n): for j in range(m): if after[i][j] == 2: virus(i, j) result = max(result, get_score()) return result for i in range(n): for j in range(m): if lis[i][j] == 0: lis[i][j] = 1 count += 1 dfs(count) lis[i][j] = 0 count -= 1 dfs(0) print(result)

백준 문제풀이 · 2023-05-29

[백준, python] 11404번 - 플로이드

백준 문제풀이 시작 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 출력 n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. 풀이 풀이 확인하기 해당 문제는 전형적인 플로이드-와셜 알고리즘 문제로, 입력을 받은 뒤 플로이드-와셜 알고리즘을 그대로 수행해주면 된다. 단, 입력에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 점을 생각하여 가장 짧은 간선의 정보만 기록할 수 있도록 한다. INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF for _ in range(n+1)] for _ in range(n+1)] for i in range(1, n+1): graph[i][i] = 0 for _ in range(m): a, b, c = map(int, input().split()) if graph[a][b] > c: graph[a][b] = c for k in range(1, n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) for i in range(1, n+1): for j in range(1, n+1): if graph[i][j] == INF: print(0, end=" ") else: print(graph[i][j], end=" ") print()

백준 문제풀이 · 2023-05-06

[백준, python] 2887번 - 행성 터널

백준 문제풀이 시작 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 $A(x_A, y_A, z_A)$와 $B(x_B, y_B, z_B)$를 터널로 연결할 때 드는 비용은 $\min($|$x_A-x_B$|$, $|$y_A-y_B$|$,$ |$z_A-z_B$|$)$이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 출력 첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다. 풀이 풀이 확인하기 해당 문제를 푸는 과정에서 모든 점에서 각 점까지의 거리를 구하게 되면 메모리 초과가 발생한다. 이를 줄이기 위해 약간의 스킬이 필요한데, 바로 정렬이다. 문제에서 터널의 비용이 각 방향으로의 거리들 중 가장 작은 값이므로 약간의 정렬 스킬을 이용하면 풀 수 있는 것이다. 먼저 X축 방향으로 각 행성들을 정렬한다. 그렇게 되면 각 행성 사이간의 거리들, 즉 행성의 수가 N이라고 한다면 N-1개의 간선만 고려를 하면 되는 것이다. 같은 방식으로 Y, Z 방향도 간선을 뽑아내면 고려해야할 간선의 수가 확 줄어들게 되는 것이다. def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b num = int(input()) parent = [0] * (num + 1) edges = [] result = 0 planet = [] for i in range(1, num+1): parent[i] = i x = [] y = [] z = [] for i in range(num): a, b, c = map(int, input().split()) x.append((a, i)) y.append((b, i)) z.append((c, i)) x.sort() y.sort() z.sort() for i in range(num-1): edges.append((x[i+1][0] - x[i][0], x[i][1], x[i+1][1])) edges.append((y[i+1][0] - y[i][0], y[i][1], y[i+1][1])) edges.append((z[i+1][0] - z[i][0], z[i][1], z[i+1][1])) edges.sort() for edge in edges: cost, a, b = edge if find_parent(parent, a) != find_parent(parent, b): union_parent(parent, a, b) result += cost print(result)

백준 문제풀이 · 2023-05-01

[백준, python] 1913번 - 달팽이

백준 문제풀이 시작 문제 홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다. N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다. 입력 첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N^2 이하의 자연수가 하나 주어진다. 출력 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다. 풀이 풀이 확인하기 이번 문제는 구현 문제로 문제에 주어진 조건대로만 문제를 풀면 풀 수 있다. 그래서 머릿속에 떠오르는 그대로 코드를 짰다. 그래서 코드가 상당히 길고 더러운데 이 부분은 충분히 줄일 수 있을 것 같다.. import sys input = sys.stdin.readline num = int(input()) lis = [[0 for _ in range(num)] for _ in range(num)] find = int(input()) howMany = 1 currentx = int(num/2) currenty = int(num/2) lis[currentx][currenty] = 1 wherex = currentx wherey = currenty num2 = 2 for i in range(num - int(num/2) -1): currentx -= 1 lis[currentx][currenty] = num2 if(num2 == find): wherex = currentx wherey = currenty num2 += 1 for _ in range(howMany): currenty += 1 lis[currentx][currenty] = num2 if(num2 == find): wherex = currentx wherey = currenty num2 += 1 howMany += 1 for _ in range(howMany): currentx += 1 lis[currentx][currenty] = num2 if(num2 == find): wherex = currentx wherey = currenty num2 += 1 for _ in range(howMany): currenty -= 1 lis[currentx][currenty] = num2 if(num2 == find): wherex = currentx wherey = currenty num2 += 1 for _ in range(howMany): currentx -= 1 lis[currentx][currenty] = num2 if(num2 == find): wherex = currentx wherey = currenty num2 += 1 howMany+=1 for i in lis: print(*i) print(wherex+1, end = " ") print(wherey+1)

백준 문제풀이 · 2023-02-26

[백준, python] 9536번 - 여우는 어떻게 울지?

백준 문제풀이 시작 문제 고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다. 입력 첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 아래와 같이 구성되어 있다. 테스트케이스의 첫 줄에는 몇 개의 단어로 이루어진 녹음된 소리가 입력된다. 단어는 알파벳 소문자로만 이루어져 있으며 공백으로 구분된다. 단어의 길이는 최대 100글자이고, 단어의 개수는 최대 100개이다. 다음 줄부터는 여우를 제외한 동물들의 울음소리가 goes 의 형태로 입력된다. 최소 1마리, 최대 100마리이며, 이름은 최대 100글자이고 실제로 존재하는 동물의 이름이다. 여우를 제외한 동물의 울음소리는 한 단어이고 최대 100글자이다. 마지막 줄에는 한신이가 알고 싶어하는 질문이 주어진다. what does the fox say? 출력 각 테스트케이스마다 여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력한다. 여우의 울음소리가 녹음되어 있음이 보장된다. (알려진 것과는 달리, 여우는 모스 부호로 의사소통하지 않는다.) 풀이 풀이 확인하기 입력받은 테스트 케이스만큼 반복문을 돌리고 반복문 내에서 모든 동물들의 울음소리를 리스트화 한다. 이후 반복문으로 받으며 what does the fox say? 가 아닐 때까지 반복적으로 동물들의 울음소리를 제거한다. 이후 리스트를 출력한다. import sys input = sys.stdin.readline num = int(input()) for _ in range(num): lis = input().strip().split() while True: question = input().strip().split() if(question == ["what", "does", "the", "fox", "say?"]): break else: lis = [i for i in lis if i != question[2]] print(*lis)

백준 문제풀이 · 2023-02-24

[백준, python] 1706번 - 크로스워드

백준 문제풀이 시작 문제 동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다. 세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다. 다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다. 출력 첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다. 풀이 풀이 확인하기 이번 문제는 조건에 알맞는 문자열을 찾을 수 있도록 분기를 잘 해줘야 한다. 입력받은 크로스워드를 이차원 배열로 담고, 가로로 된 단어를 찾는 이중 반복문을 한번, 세로로 찾는 이중 반복문을 한번, 총 두번의 반복문을 돌린다. 반복문으로 순회하다가 #을 만난다면 지금까지 읽은 단어가 1글자보다 크다면 단어 리스트에 추가하고 아닐 경우 추가하지 않는다.(한글자는 단어가 아니기 때문.) 순회가 전부 끝나고 단어가 모였다면 정렬 후 첫번째 값을 출력한다. import sys input = sys.stdin.readline width, height = map(int, input().split()) lis = [[]for _ in range(width)] for i in range(width): a = list(input().strip()) lis[i] = a words = [] for i in range(width): word = "" for j in range(height): if lis[i][j] == "#": if len(word) > 1: words.append(word) word = "" elif j == height-1 and lis[i][j] != "#": word += lis[i][j] if len(word) > 1: words.append(word) else: word += lis[i][j] for i in range(height): word = "" for j in range(width): if lis[j][i] == "#": if len(word) > 1: words.append(word) word = "" elif j == width-1 and lis[j][i] != "#": word += lis[j][i] if len(word) > 1: words.append(word) else: word += lis[j][i] words.sort() print(words[0])

백준 문제풀이 · 2023-02-23

[백준, python] 4949번 - 균형잡힌 세상

백준 문제풀이 시작 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자. 입력 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호(“( )”), 대괄호(“[ ]”)로 이루어져 있으며, 온점(“.”)으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 온점 하나(“.”)가 들어온다. 출력 각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력한다. 풀이 풀이 확인하기 입력받은 문자열이 .일 경우 종료, .이 아닐 경우 반복문을 통해 순회하며 [, (, ), ]를 만날 경우 상황에 따라 조건을 처리한다. [, (를 만날 경우 각각 ), ]를 짝지어 만난다면 pop, 아닐 경우 그대로 push를 한다. 그리고 stack의 길이가 0이 아닐 경우 no, 0일 경우 yes를 출력한다. import sys from functools import cmp_to_key input = sys.stdin.readline while True: inp = list(input().rstrip()) stack = [] if(inp == ["."]): break for i in inp: if(i == "[" or i == "("): stack.append(i) elif(i == "]"): if(len(stack) != 0 and stack[-1] == "["): stack.pop() else: stack.append(i) elif(i == ")"): if(len(stack) != 0 and stack[-1] == "("): stack.pop() else: stack.append(i) if(len(stack) == 0): print("yes") else: print("no") P.S. 조건문 처리 과정에서 if(stack[-1] == "["): 와 같이 줄 경우 stack의 길이가 0일 때 indexError가 발생하므로 이에 유의하여 처리해야 한다.

백준 문제풀이 · 2023-02-22

[백준, python] 1931번 - 회의실 배정

백준 문제풀이 시작 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다. 풀이 풀이 확인하기 이 문제는 인터벌 스케줄링(Interval Scheduling)으로 유명한 알고리즘을 사용해 풀 수 있다. 회의실 배정은 종료가 빨리 되는 회의를 우선시 하여 탐색하면 최적해를 얻을 수 있다. 입력으로 들어온 리스트들을 회의가 빨리 끝나는 순으로 정렬해준 뒤 리스트 탐색을 하며 가능한 경우들을 하나씩 확인하며 가능한 최대 경우를 출력한다. import sys from functools import cmp_to_key input = sys.stdin.readline num = int(input()) lis = [] for _ in range(num): a = list(map(int, input().strip().split())) lis.append(a) def cmp(a, b): if a[1] > b[1]: return 1 elif a[1] == b[1]: if a[0] > b[0]: return 1 else: return -1 else: return -1 lis.sort(key=cmp_to_key(cmp)) ans = 1 end_time = lis[0][1] for i in range(1, num): if(lis[i][0] >= end_time): end_time = lis[i][1] ans += 1 print(ans)

백준 문제풀이 · 2023-02-21

[백준, python] 9935번 - 문자열 폭발

백준 문제풀이 시작 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, …, 9로만 이루어져 있다. 출력 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다. 풀이 풀이 확인하기 이 문제는 스택을 통해 효율적으로 문자열을 지울 수 있다. 먼저 스택을 통해 문자열을 한글자씩 push한다. 그리고 문자열의 끝 폭발 문자열의 개수만큼 비교하며 만약 문자열의 끝부분이 폭발 문자열과 동일하다면 폭발 문자열의 길이만큼 문자열에서 pop을 한 뒤, 완성된 스택을 조건에 따라 출력한다. import sys input = sys.stdin.readline lis = list(input().strip()) find = list(input().strip()) stack = [] for i in range(len(lis)): stack.append(lis[i]) if(len(stack) >= len(find)): if(stack[len(stack)-len(find):] == find): for _ in range(len(find)): stack.pop() if(len(stack) == 0): print("FRULA") else: for i in range(len(stack)): print(stack[i], end="")

백준 문제풀이 · 2023-02-17

[백준, python] 11279번 - 최대 힙

백준 문제풀이 시작 문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 1.배열에 자연수 x를 넣는다. 2.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다. 풀이 풀이 확인하기 파이썬에는 우선순위 힙을 지원하는 라이브러리가 존재한다. heapq를 import하여 사용할 것이다. 하지만 heapq는 최소 힙을 지원하므로 입맛에 맞게 최대 힙으로 바꿔야 하는데, 숫자를 push하고 pop할 때 모두 -를 붙여 입력, 출력을 해주면 최대 힙으로 바꿔줄 수 있다. import sys from heapq import * input = sys.stdin.readline num = int(input()) heap = [] len = 0 for _ in range(num): a = int(input()) if(len == 0 and a == 0): print(0) elif(a == 0): print(-heappop(heap)) len -= 1 else: heappush(heap, -a) len += 1

백준 문제풀이 · 2023-02-16

[백준, python] 10773번 - 제로

백준 문제풀이 시작 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 “0” 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 “0”일 경우에 지울 수 있는 수가 있음을 보장할 수 있다. 출력 재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다. 풀이 풀이 확인하기 이 문제는 전형적인 스택 문제이다. 파이썬은 리스트를 가지고 스택의 기능을 사용할 수 있다. 입력을 받으면서 0이면서 동시에 리스트의 길이가 0이면 continue, 리스트의 길이가 0이 아니면서 0이 입력이 되면 pop, 아닐 경우 push를 한다. 이후 리스트의 모든 값들을 더해 출력한다. import sys input = sys.stdin.readline num = int(input()) lis = [] for _ in range(num): a = int(input()) if(a == 0 and len(lis) == 0): continue elif(a == 0): lis.pop() else: lis.append(a) ans = 0 for i in lis: ans = ans + i print(ans)

백준 문제풀이 · 2023-02-15

[백준, python] 12015번 - 가장 긴 증가하는 부분 수열 2

백준 문제풀이 시작 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 풀이 확인하기 이 문제는 백준 11053번과 동일한 문제로 보이지만 똑같이 코드를 짤 경우 시간 초과가 뜰 것이다. 그래서 시간을 줄일 수 있는 방법을 생각해야 한다. 기존 문제를 푸는 과정에서 매번 max 함수를 통해 값을 비교하는 과정에서 모든 뒤 숫자들을 비교하게 된다. 이는 비효율적이므로 이분 탐색을 통해 해당 수가 뒤 어디에 들어올만한지 효율적으로 찾을 수 있다. 위치를 찾은 뒤 해당 수와 수를 교체하는 과정으로 코드를 수정해주면 O(NlogN) 시간으로 문제를 해결할 수 있다. (P.S. 해당 코드의 ans는 실제 lis가 아니다.) import sys from bisect import bisect_left, bisect_right input = sys.stdin.readline f = int(input()) line = list(map(int, input().strip().split())) ans = [] lens = 1 ans.append(line[0]) for i in range(1, len(line)): if(ans[lens-1] < line[i]): ans.append(line[i]) lens += 1 else: j = bisect_left(ans, line[i]) ans[j] = line[i] print(lens)

백준 문제풀이 · 2023-02-14

백준 풀이 주요 알고리즘 정리

백준에서 문제를 풀어보니 자주 보이는 문제 유형들에 사용되는 알고리즘을 정리할 수 있을 것 같다는 생각이 들었다. 그래서 코딩 테스트, 백준 문제풀이 등에서 자주 보이던 유형들을 정리해보려고 한다. (계속 공부해 나가는 과정에서 업데이트 할 수 있다면 할 예정.) 1. 브루트포스 알고리즘 가장 단순한 방법이다. 바로 모든 경우의 수를 다 넣어보는 단순무식한 방법이다. 4자리 숫자 자물쇠 번호를 맞추는 가장 쉬운 방법이 무엇일까? 바로 0000부터 9999까지 다 넣어보면 되는 것이다. 이 방법이 바로 브루트포스 알고리즘이다. 1059번 1233번 등 문제를 브루트포스 알고리즘으로 풀 수 있다. 2. 그리디 알고리즘 그리디 알고리즘은 브루트포스 알고리즘과 비슷한 알고리즘이다. 하지만 브루트포스 알고리즘은 모든 경우를 다 본다면 그리디 알고리즘은 매 순간마다 자기에게 가장 이득이 되는 선택을 취하게 된다. 1417번 2839번 등 문제를 그리디 알고리즘으로 풀 수 있다. 3. DFS와 BFS DFS와 BFS는 그래프 탐색 알고리즘이다. DFS는 Deep-First Search의 줄임말로 그래프의 노드와 다음 노드를 넘어갈 때 해당 노드의 하위 노드까지 완벽히 탐색한 뒤 다음 노드로 넘어가는 것이다. 그리고 BFS는 Breadth-First Search의 줄임말로 그래프의 갈림길이 발생할 때마다 모든 경우를 넓게 탐색한 뒤 다음으로 넘어가게 된다. 말로는 이해가 힘들어 실제 트리를 통해 탐색 결과를 비교해보면 해당 그래프를 DFS를 통해 탐색할 경우 2 > 7 > 2 > 6 > 5 > 11 > 5 > 9 > 4 의 순서로 탐색을 진행할 것이다. 하지만 BFS로 탐색할 경우 2 > 7 > 5 > 2 > 6 > 9 > 5 > 11 > 4 의 순서로 탐색을 한다는 차이점이 있다. DFS의 구현은 일반적으로 재귀를 통하여 구현한다. def dfs(start): visited[start] = 1 print(start, end=" ") for i in graph[start]: if not visited[i]: dfs(i) 와 같은 형태로 DFS를 구현할 수 있다. BFS의 구현은 queue 자료구조를 통해 구현한다. def bfs(start): queue = [start] visited[start] = True while queue: v = queue.pop(0) print(v, end=" ") for i in graph[v]: if not visited[i]: visited[i] = True queue.append(i) 와 같은 형태로 BFS를 구현할 수 있다. DFS는 그래프의 모든 경우를 하나하나 탐색해야할 때, BFS는 그래프 내의 최단 거리를 찾아야할 때 자주 사용된다. 2644번 1260번 등 문제를 DFS 알고리즘으로 풀 수 있다. 4. 이분 탐색 이분 탐색은 오름차순으로 정렬된 리스트에서 원하는 수를 효율적으로 찾을 수 있는 알고리즘이다. 예를 들어 2, 3, 4, 7, 9, 11, 23 이란 리스트에서 3을 찾고 싶을 경우를 예시로 들자. 이분 탐색의 시작은 중앙값을 찾는 것이다. 저 리스트에서 중앙값은 7인데, 이때 7은 3보다 큼을 알 수 있다. 찾는 수가 중앙값보다 크다면 중앙보다 더 큰 값들은 탐색할 필요가 없으므로 처음부터 중앙값 전까지만 찾으면 되는 것이다. 이 방식을 반복하여 3이 두번째에 있음을 알 수 있는 것이다. 파이썬에서는 bisect 라이브러리를 통해 쉽게 구할 수 있다. 12015번 1920번 등 문제를 이분 탐색으로 풀 수 있지만, 시간 복잡도를 줄이기 위해서도 자주 쓴다. 5. 다이나믹 프로그래밍 아마 알고리즘 공부를 입문한 뒤 가장 처음으로 어려운 부분이 아닐까 싶다. 다이나믹 프로그래밍이란 시간 복잡도를 줄이기 위해 효율적으로 알고리즘을 작성하는 방법을 의미한다. 예를 들어보자. def fib(n): if n==1 or n==2: return 1 else: return fib(n-1) + fib(n-2) 피보나치 수를 구하는 파이썬 코드이다. 쉽게 짤 수 있지만 문제가 있다. 예를 들어 fib(6)을 알기 위해선 fib(4), fib(5)를 알아야 한다. 그리고 fib(4)는 다시 fib(3), fib(2)를, fib(5)는 fib(3), fib(4)를 알아야 한다. 여기서 문제가 발생한다. fib(3), fib(4)를 중복해서 구하게 되는 문제가 발생한다. 실제로 저 코드를 돌려보면 해당 문제 때문에 30 이상의 숫자는 결과를 확인하기 힘들 정도로 오래 걸림을 알 수 있다. 하지만 만약 저 겹치는 숫자들을 저장을 해둔다면 어떨까? 굳이 계산할 필요 없이 이미 구한 수는 저장한 값을 그대로 가져오기만 하면 되는 것이다. 이를 통해 비약적으로 프로그램 실행 속도를 단축할 수 있는 것이다. 이런 식으로 중복되는 연산들을 줄이자 라는 생각에서 출발한 것이 바로 다이나믹 프로그래밍인 것이다. 다이나믹 프로그래밍 방식에는 탑다운(Top-down), 바텀업(Bottom-up), 메모이제이션(Memoization) 등의 방식이 있다. 9184번 11053번 등의 문제를 다이나믹 프로그래밍으로 풀 수 있다.

백준 문제풀이 · 2023-02-13

[백준, python] 11478번 - 서로 다른 부분 문자열의 개수

백준 문제풀이 시작 문제 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. 출력 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다. 풀이 풀이 확인하기 이번 문제는 set을 사용하면 쉽게 풀 수 있다. set 자료형은 중복되는 값은 자동으로 들어가지 않는데, 이를 이용해 “aaa”와 같이 겹치는 요소들을 쉽게 제거할 수 있다. 이중 반복문을 통해 가능한 경우의 수의 부분 문자열들을 전부 set에 넣고, set의 요소들의 개수만 출력하면 되는 것이다. (set 자료구조는 O(1)의 시간복잡도를 가지는 매우 빠른 자료구조인데, 이 원리에 대하여 궁금하다면 hash table을 검색해보자. 참고로 파이썬의 다른 자료구조인 dictonray 역시 비슷한 구조를 가지고 있다.) import sys input = sys.stdin.readline line = input().strip() num = set([]) for i in range(0, len(line)+1): for j in range(i+1, len(line)+1): num.add(line[i:j]) print(len(num))

백준 문제풀이 · 2023-02-10

[백준, python] 11053번 - 가장 긴 증가하는 부분 수열

백준 문제풀이 시작 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 풀이 확인하기 입력받는 리스트와 memoization을 위한 리스트를 만들어 주고, memoization용 리스트의 길이는 입력 리스트의 길이와 동일하게 만들고 1로 초기화해준다. 이후 반복문으로 돌면서 i번째에 존재하는 값이 j번째에 존재하는 값보다 더 크다면 memoization의 i번째와 j번째값 + 1 을 비교하여 더 큰 값으로 update한다. 이후 memoization용 리스트의 가장 큰 값이 lis의 길이가 된다. import sys input = sys.stdin.readline num = int(input()) lis = list(map(int, input().strip().split())) mem = [1 for _ in range(len(lis))] for i in range(1, len(lis)): for j in range(0, i): if(lis[i] > lis[j]): mem[i] = max(mem[i], mem[j]+1) print(max(mem))

백준 문제풀이 · 2023-02-09

[백준, python] 1912번 - 연속합

백준 문제풀이 시작 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 풀이 풀이 확인하기 입력받는 리스트와 memoization을 위한 리스트를 만들어 주고, memoization용 리스트의 첫번째에 입력받은 리스트의 첫번째 값을 담는다. 이후 나머지는 memoization 리스트의 현재보다 한칸 전 값에 현재 값을 더한 값과 현재 값을 비교 해 더 큰 값을 담는다. 이후 memoization 리스트에서 가장 큰 값을 출력한다. num = int(input()) arr = list(map(int, input().split(" "))) mem = [0]*num mem[0] = arr[0] for i in range(1, num): mem[i] = max(arr[i], mem[i-1] + arr[i]) print(max(mem))

백준 문제풀이 · 2023-02-08

[백준, python] 1932번 - 정수 삼각형

백준 문제풀이 시작 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 풀이 풀이 확인하기 이번 문제는 DP를 통해 풀 수 있다. 입력을 받은 뒤 두번째 줄부터 반복문을 통해 돌며 위치가 양 끝이라면 위에서 내려올 수 있는 곳은 하나밖에 없으므로 해당 값과 현재 위치를 더한 값으로 업데이트하고, 다른 수들은 위에서 내려올 수 있는 두 수 중 큰 값과 현재 위치를 더한 값으로 업데이트하는 과정을 반복해 내려온 뒤, 맨 밑 줄에 있는 수중 가장 큰 값을 출력한다. import sys input = sys.stdin.readline a = int(input()) data = [] for _ in range(a): data.append(list(map(int, input().strip().split()))) b = 0 for i in range(1, a): for j in range(0, len(data[i])): if(j == 0): data[i][j] = data[i-1][0] + data[i][j] elif(j == len(data[i])-1): data[i][j] = data[i-1][b-1] + data[i][j] else: data[i][j] = max(data[i-1][j-1], data[i-1][j]) + data[i][j] b = len(data[i]) print(max(data[a-1]))

백준 문제풀이 · 2023-02-07

[백준, python] 9184번 - 신나는 함수 실행

백준 문제풀이 시작 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오. 입력 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다. 풀이 풀이 확인하기 이번 문제는 DP를 통해 풀 수 있다. 문제에서 1부터 20까지만 필요하므로 memoization을 위한 배열은 3차원으로 1부터 20까지 적을 수 있도록 크기를 만들고, 함수를 정의한다. w 함수는 문제에서 준 sudo code와 동일하게 작성하지만 memoization이 되어있는 값이라면 재귀를 통한 연산 없이 바로 반환하고, 없다면 똑같이 연산을 진행한 뒤 배열의 해당 값에 해당하는 위치에 값을 저장해둔다. import sys input = sys.stdin.readline mem = [[[0 for _ in range(21)] for _ in range(21)]for _ in range(21)] def w(a, b, c): if a <= 0 or b <= 0 or c <= 0: return 1 if a > 20 or b > 20 or c > 20: return w(20, 20, 20) if mem[a][b][c]: return mem[a][b][c] if a < b and b < c: mem[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return mem[a][b][c] else: mem[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) return mem[a][b][c] while(True): aa, bb, cc = map(int, input().split()) if(aa == -1 and bb == -1 and cc == -1): break print("w(" + str(aa) + ", " + str(bb) + ", " + str(cc) +") = ", end="") print(w(aa, bb, cc))

백준 문제풀이 · 2023-02-06

[백준, python] 1774번 - 우주신과의 교감

백준 문제풀이 시작 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다. 또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있는 세상에 살고 있다. 통로들의 길이는 2차원 좌표계상의 거리와 같다. 이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재한다. 우리는 황선자 씨를 도와 아직 연결이 되지 않은 우주신들을 연결해 드려야 한다. 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자. 입력 첫째 줄에 우주신들의 개수(N<=1,000) 이미 연결된 신들과의 통로의 개수(M<=1,000)가 주어진다. 두 번째 줄부터 N개의 줄에는 황선자를 포함하여 우주신들의 좌표가 (0<= X<=1,000,000), (0<=Y<=1,000,000)가 주어진다. 그 밑으로 M개의 줄에는 이미 연결된 통로가 주어진다. 번호는 위의 입력받은 좌표들의 순서라고 생각하면 된다. 좌표는 정수이다. 출력 첫째 줄에 만들어야 할 최소의 통로 길이를 출력하라. 출력은 소수점 둘째짜리까지 출력하여라. 풀이 풀이 확인하기 이번 문제는 최소 스패닝 문제이지만 두가지 차이점이 존재하는데 가중치가 나와있지 않다. 이미 연결된 간선이 존재한다. 라는 문제가 존재한다. 하지만 1의 경우 두 우주신 사이의 거리가 가중치가 된다. 그러므로 두 간선 사이의 가중치를 반복문을 통해 구해 edge에 추가해주면 평범한 MST 문제가 된다. 2번 역시 그저 나온 두 우주신들을 union 연산만 해주면 된다. import sys input = sys.stdin.readline def find(p, a): if(p[a] != a): p[a] = find(p, p[a]) return p[a] def union(p, a, b): a = find(p, a) b = find(p, b) if(a < b): p[b] = a else: p[a] = b v, e = map(int, input().split()) p = [0] * (v + 1) edge = [] cost = 0.0 for i in range(1, v+1): p[i] = i data = [] for _ in range(v): a, b = map(int, input().split()) data.append([a, b]) for i in range(len(data)): for j in range(i+1, len(data)): costs = abs(((data[j][1] - data[i][1])**2 + (data[j][0] - data[i][0])**2)**(1/2)) edge.append((costs, i+1, j+1)) for _ in range(e): f, g = map(int, input().split()) union(p, f, g) edge.sort() for ed in edge: c, a, b = ed if(find(p, a) != find(p, b)): union(p, a, b) cost += c print("{:.2f}".format(cost)) P.S. 문제 내용이 정말 스펙타클하군요…

백준 문제풀이 · 2023-01-30

[백준, python] 6800번 - Huffman Encoding

백준 문제풀이 시작 문제 There is an ingenious text-compression algorithm called Huffman coding, designed by David Huffman in 1952. The basic idea is that each character is associated with a binary sequence (i.e., a sequence of 0s and 1s). These binary sequences satisfy the prefix-free property: a binary sequence for one character is never a prefix of another character’s binary sequence. It is worth noting that to construct a prefix-free binary sequence, simply put the characters as the leaves of a binary tree, and label the “left” edge as 0 and the ”right” edge as 1. The path from the root to a leaf node forms the code for the character at that leaf node. For example, the following binary tree constructs a prefix-free binary sequence for the characters {A, B, C, D, E}: That is, A is encoded as 00, B is encoded as 01, C is encoded as 10, D is encoded as 110 and E is encoded as 111. The benefit of a set of codes having the prefix-free property is that any sequence of these codes can be uniquely decoded into the original characters. Your task is to read a Huffman code (i.e., a set of characters and associated binary sequences) along with a binary sequence, and decode the binary sequence to its character representation. 입력 The first line of input will be an integer k (1 ≤ k ≤ 20), representing the number of characters and associated codes. The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10) representing the associated code of that character. You may assume that the character is an alphabet character (i.e., ‘a’…‘z’ and ‘A’..‘Z’). You may assume that the sequence of binary codes has the prefix-free property. On the k + 2nd line is the binary sequence which is to be decoded. You may assume the binary sequence contains codes associated with the given characters, and that the k + 2nd line contains no more than 250 binary digits. 출력 On one line, output the characters that correspond to the given binary sequence. 풀이 풀이 확인하기 입력을 받은 뒤 binary sequence를 key로 가지는 dictionary를 만든다. 그리고 0과 1로 이뤄진 문자열을 받아 queue로 만들어 하나씩 pop을 하면서 해당 데이터가 dictionary에 없다면 다시 pop해서 더하고, 해당 데이터가 dictionary에 있으면 변환을 하여 정답 문자열에 더한 뒤 pop한 데이터들을 전부 초기화해주는 과정을 반복한다. import sys from collections import deque input = sys.stdin.readline num = int(input()) data = {} for _ in range(num): a = input().strip().split() data[a[1]] = a[0] encode = deque(input().strip()) temp = "" ans = "" while True: temp = temp + encode.popleft() if temp in data: ans = ans + data[temp] temp = "" if(len(encode) == 0): break print(ans)

백준 문제풀이 · 2023-01-26

[백준, python] 14621번 - 나만 안되는 연애

백준 문제풀이 시작 문제 깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다. 이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다. 만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다. 이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자. 입력 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000) 출력 깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.) 풀이 풀이 확인하기 이번 문제는 1197번 문제와 거의 동일하다. 해당 링크.를 참조하자. 여기서 다른 점은 edge 추가 과정에서 edge가 연결하는 두 vertex가 둘 다 M이거나 W일 경우 추가하지 않고, 또한 MST를 만든 뒤 edge의 수가 vertex의 수 - 1가 아닐 경우 모든 학교가 연결되어있지 않다는 뜻이므로 -1을 출력한다. import sys input = sys.stdin.readline def find(p, a): if(p[a] != a): p[a] = find(p, p[a]) return p[a] def union(p, a, b): a = find(p, a) b = find(p, b) if(a < b): p[b] = a else: p[a] = b v, e = map(int, input().split()) p = [0] * (v + 1) edge = [] cost = 0 s = 0 for i in range(1, v+1): p[i] = i lis = input().strip().split() for _ in range(e): a, b, c = map(int, input().split()) if(lis[a-1] != lis[b-1]): edge.append((c, a, b)) edge.sort() for ed in edge: c, a, b = ed if(find(p, a) != find(p, b)): union(p, a, b) cost += c s+=1 if(s != v-1): print(-1) else: print(cost)

백준 문제풀이 · 2023-01-26

[백준, python] 1197번 - 최소 스패닝 트리

백준 문제풀이 시작 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다. 출력 첫째 줄에 최소 스패닝 트리의 가중치를 출력한다. 풀이 풀이 확인하기 해당 문제는 최소 스패닝 트리(MST)인지 확인하는 문제이다. MST를 구하기 위해 사용하는 알고리즘이 크루스칼 알고리즘(Kruskal Algorithm)인데, 이는 즉 해당 문제가 크루스칼 알고리즘을 구현하는 문제라고 볼 수 있는 것이다. 크루스칼 알고리즘을 위해 cycle을 판단하는 구조인 union-find 구조를 구현하고, 형태에 맞게 입력을 받은 뒤, 입력받은 edge를 가중치를 기준으로 오름차순 정렬을 해준다. 그리고 edge를 순회하며 만약 해당 edge를 추가했을 때 cycle이 발생하지 않는다면 해당 edge를 union하며 값을 추가한다. (cycle이 발생하면 edge를 하나 삭제함으로써 가중치를 줄일 수 있기 때문.) import sys input = sys.stdin.readline def find(p, a): if(p[a] != a): p[a] = find(p, p[a]) return p[a] def union(p, a, b): a = find(p, a) b = find(p, b) if(a < b): p[b] = a else: p[a] = b v, e = map(int, input().split()) p = [0] * (v + 1) edge = [] cost = 0 for i in range(1, v+1): p[i] = i for _ in range(e): a, b, c = map(int, input().split()) edge.append((c, a, b)) edge.sort() for ed in edge: c, a, b = ed if(find(p, a) != find(p, b)): union(p, a, b) cost += c print(cost)

백준 문제풀이 · 2023-01-25

[백준, python] 1002번 - 터렛

백준 문제풀이 시작 문제 조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다. 출력 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. 풀이 풀이 확인하기 해당 문제에서 조규현과 백승환의 위치를 원의 중점, 류재명까지의 각각의 거리를 반지름, 그리고 류재명의 위치라 원의 교점이라고 바꾸면 문제가 쉽게 풀린다. 원의 교점이 발생하는 경우는 원이 같을 경우 교점은 -1 원이 외접할 경우 교점은 1 원이 내접할 경우 교점은 1 원이 밖에 떨어져 있으면 교점은 0 원이 안에 있으면 교점은 0 그 외에는 2 로 생각할 수 있다. 이를 조건에 따라 잘 분기해주면 풀 수 있다. import sys input = sys.stdin.readline num = int(input()) for _ in range(num): a = list(map(int, input().strip().split(' '))) dist = abs((((a[4]- a[1])**2) + ((a[3]- a[0])**2)) ** (1/2)) maxd = 0 mind = 0 if(a[5]>a[2]): maxd = a[5] mind = a[2] else: maxd = a[2] mind = a[5] if(dist == 0 and maxd == mind): print(-1) elif(maxd + mind == dist): print(1) elif(maxd - mind == dist): print(1) elif(maxd + mind < dist): print(0) elif(dist + mind < maxd): print(0) else: print(2)

백준 문제풀이 · 2023-01-20

[백준, python] 16139번 - 인간 - 컴퓨터 상호작용

백준 문제풀이 시작 문제 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. ‘문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.’ 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $q$번 할 것이다. 입력 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 1 $\leq q\leq$ 200,000을 만족한다. 세 번째 줄부터 ($q$+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 $\alpha_i$와 $0\leq l_i\leq r_i<|S|$를 만족하는 정수 $l_i,r_i$가 공백으로 구분되어 주어진다. 출력 각 질문마다 줄을 구분해 순서대로 답변한다. $i$번째 줄에 $S$의 $l_i$번째 문자부터 $r_i$번째 문자 사이에 $\alpha_i$가 나타나는 횟수를 출력한다. 풀이 풀이 확인하기 해당 문제를 풀면서 알파벳을 입력받았을 때 얼마나 있는지 문자열을 그때그때 전부 순회하여 찾으면 O(N)의 시간이 걸리게 된다. 그러므로 좀 더 빠르게 계산을 하는 방법이 필요한데, 누적합을 사용하면 계산을 O(1) 시간 내에 계산할 수 있다. 누적합을 구하기 위해 배열을 하나 만든다. 그리고 배열에서 문자열을 순회하며 해당 알파벳이 나올 때마다 1씩 더해 계속 append 해준다. 그러면 몇번째 글자까지 해당 알파벳이 얼마나 나왔는지 알 수 있을 것이다. 하지만 문제에서는 특정 구간을 구해야 하는데, 이때 예를 들어 A[i, j]를 구하고 싶다면 누적합 배열을 B라 가정하면 B[j+1] - B[i]를 계산해주면 바로 구할 수 있다. import sys input = sys.stdin.readline string = list(input().rstrip()) num = int(input()) ans = {} for i in range(97, 123): temp = 0 sum = [0] for j in string: if(chr(i) == j): temp += 1 sum.append(temp) ans[chr(i)] = sum for _ in range(num): inp = input().rstrip().split(' ') sys.stdout.write(str(ans[inp[0]][int(inp[2])+1] - ans[inp[0]][int(inp[1])]) + '\n')

백준 문제풀이 · 2023-01-19

[백준, python] 1629번 - 곱셈

백준 문제풀이 시작 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 풀이 풀이 확인하기 문제를 얼핏 보면 매우 쉬운 문제같지만 시간 제한에 주목하면 평범한 방식으로는 절대 통과하지 못함을 알 수 있다. 그래서 우리는 중고등학교에서 배웠던 지수법칙을 응용할 것이다. 이때 지수법칙이란 ${x^n}\times{x^m} = {x^{n+m}}$ 인데 이를 제곱 식에 맞게 잘 응용하면 \[{x^n}= \begin{cases} x^{\frac{x}{2}}\times x^{\frac{x}{2}} & \text{if } \,\, n \% 2 = 0, \\ x^{\frac{x}{2}}\times x^{\frac{x}{2}}\times {x^1} & \text{if } \,\, n \% 2 = 1 . \end{cases}\] 의 형태로 바꿀 수 있다. 이렇게 계산을 할 경우 기존 거듭제곱보다 훨씬 적은 양의 계산만 가지고도 거듭제곱을 풀 수 있다. 이를 프로그램에 옮겨 문제가 원하는 요구사항대로 출력하면 풀 수 있다. import sys input = sys.stdin.readline def mul(a, b, c): if (b == 1): return a % c else: s = mul(a, b//2, c) x = s*s if(b % 2 == 0): return x % c else: return (x * mul(a, 1, c)) % c a, b, c = map(int, input().split(" ")) print(mul(a, b, c)) P.S. 원래는 문제를 풀 때 mul 함수에선 거듭제곱만 구하고 이후 마지막 수로 나눈 나머지를 구했는데, 이렇게 할 경우 시간 초과가 발생한다. 그래서 함수 내에 옮기니까 시간 제한이 걸리지 않고 통과함을 알 수 있었다. 왜 그런지는 찾아보아야 할 듯 하다.

백준 문제풀이 · 2023-01-18

[백준, python] 5430번 - AC

백준 문제풀이 시작 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, “AB”는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, “RDD”는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. 다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000) 다음 줄에는 [x1, … ,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100) 전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다. 출력 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. 풀이 풀이 확인하기 해당 문제를 풀며 R을 만나는 순간마다 뒤집을 경우 큰 문제가 발생한다. reverse 함수를 사용하면 리스트를 새로 다시 만든다고 생각하면 된다. 이렇게 되면 만약 예를 들어 RRRRRRRRRRRRR과 같이 R을 많이 쓸 경우 엄청난 시간 문제가 발생할 것이다. 그러므로 R을 마주칠 때마다 몇번 뒤집는지 계산하고, 이후 뒤집는 수가 홀수면 뒤집고, 아니면 안뒤집으면 한번만 뒤집으면 된다. 이 과정에서 D를 만났을 때 처리가 애매해지는데, 무작정 앞에서부터 지우면 RD같은 경우에 문제가 발생할 것이다. 그러므로 뒤집는 수를 여기서 다시 확인해서 홀수면 뒤집을 것이므로 맨 뒤에서, 짝수면 안뒤집으므로 맨 앞에서 pop을 한다. 이 때문에 우린 deque을 사용할 것이다. 또한 확인해줘야하는 요소가 일부 있는데, 먼저 리스트의 0의 경우 D는 불가능하지만 R은 가능하다. 그러므로 0이라고 무작정 error를 출력하는 것이 아닌 []로 리스트를 만들어줘야 한다. 그리고 출력을 잘 봐야 하는데, [1,2]처럼 리스트 사이에 공백이 존재하지 않는다. 그러므로 바로 리스트를 int형으로 바꿔 출력하면 안되고 join 함수를 사용하여 공백을 적절히 처리해준다. import sys from collections import deque input = sys.stdin.readline num = int(input()) answer = [] for _ in range(num): is_Error = False command = input().rstrip() num1 = int(input()) lis = input().replace('[', ',').replace(']', ',').rstrip().split(',')[1:-1] if(num1 == 0): lis = [] else: lis = deque(map(int,lis)) is_reverse = 0 for i in command: if(i == "R"): is_reverse += 1 elif(i == "D"): if(len(lis) == 0): is_Error = True break else: if(is_reverse % 2 == 1): lis.pop() else: lis.popleft() if(is_Error): print('error') else: if(is_reverse % 2 == 1): lis.reverse() print('['+','.join(map(str, lis))+']')

백준 문제풀이 · 2023-01-17

[백준, python] 22233번 - 가희와 키워드

백준 문제풀이 시작 문제 가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다. 지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 N개가 존재합니다. 가희는 새로운 글을 작성할 때, 최대 10개의 키워드에 대해서 글을 작성합니다. 이 키워드들 중에 메모장에 있었던 키워드는 가희가 글을 쓴 이후, 메모장에서 지워지게 됩니다. 가희는 블로그에 글을 쓰고 나서, 메모장에 있는 키워드 개수가 몇 개인지 알고 싶습니다. 가희를 도와주세요. 입력 첫 번째 줄에 가희가 메모장에 적은 키워드 개수 N, 가희가 블로그에 쓴 글의 개수 M이 공백으로 구분해서 주어집니다. 2번째 줄부터 N+1번째 줄까지 메모장에 적은 키워드 N개가 주어집니다. N+2번째 줄부터 N+M+1번째 줄까지, 가희가 쓴 글과 관련된 키워드가 , (쉼표)로 구분해서 주어집니다. 공백으로 구분되지 않음을 유의해 주세요. 출력 x번째 줄에는 x번째 글을 쓰고 난 후에 메모장에 남아 있는 키워드의 개수를 출력해 주세요. 풀이 풀이 확인하기 입력을 받은 뒤 dictionary에 입력받은 키워드들을 담는다. 이후 사용한 키워드들이 주어질 때 요소들이 dictionary에 있다면 제거하고 남은 키워드들의 개수를 따로 담아 출력한다. import sys input = sys.stdin.readline num1, num2 = map(int, input().strip().split(' ')) line = {} answer = [] for _ in range(num1): a = input().strip() line[a] = "" for _ in range(num2): unused = 0 b = input().strip().split(',') for i in range(0, len(b)): if b[i] in line: del line[b[i]] answer.append(len(line)) for i in answer: print(i)

백준 문제풀이 · 2023-01-16

[백준, python] 9996번 - 한국이 그리울 땐 서버에 접속하지

백준 문제풀이 시작 문제 선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다. 호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. 선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다. 어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다. 패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다. 파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, “abcd”, “ad”, “anestonestod”는 모두 패턴 “a*d”와 일치한다. 하지만, “bcd”는 일치하지 않는다. 패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다. 출력 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 “DA”, 일치하지 않으면 “NE”를 출력한다. 참고로, “DA”는 크로아티어어로 “YES”를, “NE”는 “NO”를 의미한다. 풀이 풀이 확인하기 해당 문제는 정규식으로 풀면 쉽게 풀 수 있다. 입력받은 뒤 정규식으로 변환하고, 이후 입력받은 뒤 매칭을 시켜 매칭시킨 결과가 입력받은 문자와 동일하면 DA, 아니면 NE를 출력하도록 한다. import re import sys input = sys.stdin.readline num = int(input()) toFind = input().strip().split("*") reg1 = toFind[0]+".*"+toFind[1]+"+" reg = re.compile(reg1) lis = [] for _ in range(num): b = input().strip() a = reg.match(b) if(a and a.group() == b): print("DA") else: print("NE")

백준 문제풀이 · 2023-01-12

[백준, python] 18870번 - 좌표 압축

백준 문제풀이 시작 문제 수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다. 출력 첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다. 풀이 풀이 확인하기 입력을 받은 뒤 리스트를 복사하고, 해당 리스트를 set으로 바꿔 중복되는 요소를 지우고, 다시 리스트로 바꾼 뒤 해당 리스트를 정렬해서 순서를 추출했다. 이후 기존 리스트와 순서를 비교하여 출력한다. 이때 비교를 하는 과정에서 그냥 반복문으로 비교하면 시간 초과가 발생하므로 이분 탐색으로 비교한다. import sys import copy input = sys.stdin.readline num = int(input()) lis = list(map(int, input().strip().split(" "))) lis2 = copy.deepcopy(lis) lis2 = list(set(lis2)) lis2.sort() for i in range(0, len(lis)): left = 0 right = len(lis2)-1 while(left <= right): mid = (left+right)//2 if (lis2[mid] == lis[i]): print(mid) break elif (lis2[mid]>lis[i]): right = mid-1 else: left = mid+1 P.S. 지금 보니 복사 이후 set으로 바꾸고 다시 리스트로 바꾸는 과정이 매우 비효율적인 것 같다. 입력받는 과정에서 저장을 딕셔너리로 저장한 뒤 key값만 추출하면 조금 더 빠르게 할 수 있지 않을까 싶다.

백준 문제풀이 · 2023-01-12

[백준, python] 7785번 - 회사에 있는 사람

백준 문제풀이 시작 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 “enter”나 “leave”가 주어진다. “enter”인 경우는 출근, “leave”인 경우는 퇴근이다. 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다. 출력 현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다. 풀이 풀이 확인하기 파이썬에서 자체 제공하는 딕셔너리를 사용하여 문제를 해결했다. 딕셔너리의 key값에 이름, value에 enter 또는 leave를 입력받아 저장하고, 딕셔너리를 순회하며 value가 enter인 key만 리스트로 가져와 정렬하고 출력한다. import sys input = sys.stdin.readline company = {} num = int(input()) for _ in range(num): people = input().strip().split(" ") company[people[0]] = people[1] ans = [] for i in company: if(company[i] == "enter"): ans.append(i) ans.sort(reverse=True) for i in range(len(ans)): print(ans[i])

백준 문제풀이 · 2023-01-11

[백준, python] 1448번 - 삼각형 만들기

백준 문제풀이 시작 문제 세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다. 입력 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 작거나 같은 자연수이다. 각 사람의 부모는 최대 한 명만 주어진다. 출력 첫째 줄에 삼각형 세 변의 길이의 합의 최댓값을 출력한다. 만약 삼각형을 만들 수 없으면 -1을 출력한다. 풀이 풀이 확인하기 삼각형은 가장 큰 변을 제외한 두 변의 합이 가장 큰 변의 크기보다 커야 한다. 리스트를 입력받아 내림차순으로 정렬한 뒤 두번째, 세번째 요소를 더한 값이 첫번째 요소보다 작거나 같다면 다음으로, 크다면 결과를 저장한다. import sys input = sys.stdin.readline num = int(input()) lis = [] for _ in range(0, num): a = int(input()) lis.append(a) lis.sort(reverse=True) ans = -1 is_Find = False for i in range(0, len(lis)-2): if(lis[i] < (lis[i+1] + lis[i+2])): ans = lis[i] + lis[i+1] + lis[i+2] break print(ans)

백준 문제풀이 · 2023-01-10

[백준, python] 2644번 - 촌수 계산

백준 문제풀이 시작 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 한 명만 주어진다. 출력 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다. 풀이 풀이 확인하기 해당 문제는 dfs 함수 내에서 재귀적으로 연산을 하였다. 입력을 받은 뒤 정답 리스트를 만들고, 방문이 이뤄질 때마다 방문 수를 증가시키고, 사람을 찾을 경우 리스트에 방문 수를 담는다. import sys input = sys.stdin.readline vertex = int(input()) people1, people2 = map(int, input().split(' ')) edge = int(input()) graph = [[] for _ in range(vertex + 1)] visited = [0] * (vertex + 1) for _ in range(edge): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) ans = [] def dfs(start, num): num+=1 visited[start] = 1 if(people2 == start): ans.append(num) for i in graph[start]: if not visited[i]: dfs(i, num) dfs(people1, 0) if(len(ans) != 0): print(ans) else: print(-1)

백준 문제풀이 · 2023-01-09

[백준, python] 5567번 - 결혼식

백준 문제풀이 시작 문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 출력 첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다. 풀이 풀이 확인하기 해당 문제는 1을 root로 하는 dfs 문제로 바꿔 볼 수 있다. 입력을 받은 뒤 리스트로 변환하고, 1번째 리스트를 제외한 나머지 리스트들 안에서 1이 보일 경우 1과 연결되어있단 소리이므로 리스트를 초기화해준 뒤 해당 그래프를 dfs를 돌려 결과를 얻는다. import sys input = sys.stdin.readline vertex = int(input()) edge = int(input()) graph = [[] for _ in range(vertex + 1)] for _ in range(edge): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() for i in range(2, len(graph)): is_1 = False for j in range(0, len(graph[i])): if(graph[i][j] == 1): is_1 = True break if not is_1: graph[i] = [] a = [] visited = [0] * (vertex + 1) num = 0 def dfs(start): global num visited[start] = 1 num += 1 print(start, end=" ") for i in graph[start]: if not visited[i]: dfs(i) dfs(1) print(num-1)

백준 문제풀이 · 2023-01-06

[백준, python] 4948번 - 베르트랑 공준

백준 문제풀이 시작 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다. 풀이 풀이 확인하기 해당 문제는 소수를 일일히 검사하려는 순간 시간 초과가 발생함을 확인했다. 예를 들어 10000과 10001을 입력했을 때 10000에서부터 20000까지 검사한 뒤 10001에서 20002까지 검사하는 과정에서 10000을 검사할 때 중첩된 부분이 발생하는 것이다. 그래서 n의 최대값인 123456의 2를 곱한 만큼의 값을 에라토스테네스의 체로 검사를 하여 전부 True 및 False를 미리 계산해놓고, 이후에 검사하는 과정에서는 계산 결과를 그대로 가져다 쓰기만 하였다. import math import sys input = sys.stdin.readline sieve = [True] * 246912 m = int(math.sqrt(246912)) for i in range(2, m + 1): if sieve[i] == True: for j in range(i+i, 246912, i): sieve[j] = False sieve.append(False) num = 0 answer = [] while True: is_prime = 0 num = int(input()) if(num == 0): break for i in range(num+1, (2*num)+1): if(sieve[i] == True): is_prime += 1 answer.append(is_prime) for i in range(0, len(answer)): print(answer[i])

백준 문제풀이 · 2023-01-05

[백준, python] 1735번 - 분수 합

백준 문제풀이 시작 문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 풀이 풀이 확인하기 해당 문제는 두 수의 최대공약수를 구하는 방법인 유클리드 호제법에 대한 이해가 필요하다. 유클리드 호제법이란 두 수가 나눠떨어지지 않는다면 두 수를 나눈 나머지를 구하고, 그 수와 나머지를 나누는 과정을 반복해 나가며 나누어 떨어질 때까지 계산해나가면 그 수가 최대공약수가 되는 것이다. 자세한 내용은 링크 를 참조하면 좋을 것 같다. def euc(x, y): if((y % x) == 0): return x else: return euc(y % x, x) a, b = map(int, input().split(' ')) c, d = map(int, input().split(' ')) e = a*d + c*b f = b*d g = euc(e, f) print(int(e/g), end=" ") print(int(f/g))

백준 문제풀이 · 2023-01-03

[백준, python] 1260번 - DFS와 BFS

백준 문제풀이 시작 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 풀이 풀이 확인하기 이번 문제는 그래프 순회 방식 중 dfs와 bfs를 사용하여 문제를 해결해야 한다. dfs는 재귀, bfs는 queue를 사용하여 문제를 해결하였다. 링크 를 참조하여 문제를 풀었다. import sys input = sys.stdin.readline def dfs(start): visited[start] = 1 print(start, end=" ") for i in graph[start]: if not visited[i]: dfs(i) def bfs(start): queue = [start] visited[start] = True while queue: v = queue.pop(0) print(v, end=" ") for i in graph[v]: if not visited[i]: visited[i] = True queue.append(i) vertex, edge, first = map(int, input().split()) graph = [[] for _ in range(vertex + 1)] for _ in range(edge): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() a = [] visited = [0] * (vertex + 1) dfs(first) print() visited = [0] * (vertex + 1) bfs(first) P.S. BFS 및 DFS 알고리즘은 이론으로만 공부하고 실제 코드로 짜본 적이 없어서 이번 풀이는 인터넷에 의존하여 거의 복사 붙여넣기 수준으로 이뤄졌다. 당분간 그래프 탐색을 시작으로 알고리즘 공부를 위주로 해야하지 않을까 싶다.

백준 문제풀이 · 2023-01-03

[백준, python] 1032번 - 명령 프롬프트

백준 문제풀이 시작 문제 시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다. dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. “dir 패턴”과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다. 이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 “.” 그리고 “?”만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다. 입력 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳 소문자와 ‘.’ 로만 이루어져 있다. 출력 첫째 줄에 패턴을 출력하면 된다. 풀이 풀이 확인하기 해당 문제는 입력으로 들어오는 문자열의 길이가 모두 같다는 점을 가지고 쉽게 풀 수 있다. 숫자를 입력받고 입력받은 숫자만큼 반복문을 통해 문자열을 리스트에 담는다. 그리고 들어온 문자열의 길이만큼 반복문을 돌고, 반복문 내에서 리스트를 순회하며 해당 문자열의 인덱스가 모든 문자열이 공통으로 가진 값인지 확인한 뒤, 같으면 정답 문자열에 해당 글자를, 다르면 정답 문자열에 ?를 더한다. stringList = [] num = int(input()) for i in range(0, num): string = input() stringList.append(string) answer = "" for i in range(0, len(stringList[0])): temp = True for j in range(0, len(stringList)): if(stringList[0][i] != stringList[j][i]) : temp = False break if(temp == True) : answer = answer + stringList[0][i] else: answer = answer + "?" print(answer)

백준 문제풀이 · 2023-01-02

개발하는 쿼카

Contact

All Posts