포렌식 & 개발 이야기 - Forensics & Development

이번 회차에 정보보안기사 필기와 실기 모두 한 번에 합격했습니다.짧게나마 제 공부 방법과 느낀 점, 그리고 소소한 팁들을 기록용으로 남겨봅니다.앞으로 준비하시는 분들께 조금이나마 도움이 되길 바랍니다1.시험 개요정보보안기사는 한국인터넷진흥원(KISA) 주관 자격증으로, 정보보안 실무 지식 + 보안관리 능력을 두루 평가합니다.필기 : 객관식 4지선다, 과목별 20문항씩 총 100문항 (과락 있음)실기 : 필답형 (보안 관련 실무 지식 + 상황 대응)시험 일정은 상·하반기로 연 3회 진행되며, 제가 응시한 회차는 2025년 1회차였습니다.2. 필기 공부법✅ 공부 기간: 약 2~3주저는 짧게 집중해서 준비하는 스타일이라, 기본 이론 + 기출 반복 중심으로 공부했습니다.이때 BOB랑 일정이 겹쳐서 책만 사두고 ..

본 글은 언제든지 비공개 되거나, 삭제될수 있음을 미리 알려드립니다. (뭐,, 카카오톡 본사에서 글 내려라 하지 않는 이상 없어지진 않지 않을까...?) 이 글은 여러 논문을 참조하여 분석 및 구현한것이며, 참고 문헌은 아래에서 확인 할 수 있다. 분석 환경 및 도구 : MacBook Air M2, Python 3.9, DB Browser for SQLite, HxD,, 등등등등 먼저 윈도우용 카카오톡 데이터베이스 복호화를 하는 이유가 무엇인가 ? 직관적인 주제이며, 가장 결과물이 잘 나올수 있는 복호화 솔루션이 아닌가! 상용 포렌식 도구들에서도 카카오톡 복호화는 어려움을 겪는 부분이라, 쉽고, 빠르게 복호화 할수 있는 방법이 뭐가 있나 고민하다 분석하게 되었음. (사실 이렇게 퍼블릭하게 코드도 공개해도..

Puzzle #1: Ann’s Bad AIM SEPTEMBER 25, 2009 / ADMIN / 5 COMMENTS Anarchy-R-Us, Inc. suspects that one of their employees, Ann Dercover, is really a secret agent working for their competitor. Ann has access to the company’s prize asset, the secret recipe. Security staff are worried that Ann may try to leak the company’s secret recipe. Security staff have been monitoring Ann’s activity for some ti..

오늘은 Pyinstaller를 통해서 암호화된 바이너리 디컴파일을 해보도록하겠습니다. 먼저 아래 사진은 그냥 심심해서 만들어 놓은 트위터 자동 글쓰기 프로그램입니다. 하지만 Pyinstaller을 통해서 암호화 키를 탑재해서 컴파일을 했었지만, 암호가 기억이 안나 리버싱(?)을 통해서 디컴파일을 성공했습니다. 먼저 파일을 분해하기 위해서 pyinstallerextractor 을 사용하도록 하겠습니다. 다운로드 링크는 아래와 같습니다. https://sourceforge.net/projects/pyinstallerextractor/ PyInstaller Extractor Download PyInstaller Extractor for free. Extract contents of a Windows execu..

먼저 본 글을 통해서 악의적이나 불법적으로 이용할 경우, 어떠한 책임도 지지 않음을 알려드립니다. 본 글을 쓴 목적은, 예전부터 흥미를 가졌던 FaceSwap과 VoiceSwap 두개중 먼저 FaceSwap(얼굴 교체)에 대해 포스팅을 해보려고 합니다. 먼저 필자의 환경은 다음과 같습니다. OS Windows 11 x64 CPU AMD Ryzen 3700X 8-Core Processor RAM 32GB VGA NVIDIA GeForce GTX 1660 SUPER 먼저 FaceSwap 즉, Deepfake를 구현하기 위해서는 VGA와 CPU의 성능이 좋아야합니다. 딥페이크를 구현하기 이전, CUDA와 tensorflow를 설치해보도록 하겠습니다. 먼저 CUDA를 설치해줍니다. https://develope..

무려 에어팟 프로를 산지 4년을 훌쩍 넘고 쓴지 벌써 5년 가까이 되고 있다..5년가까이 써서 그런지 유닛과 본체 사이의 충전 접점이 밀려서 들어가버렸다는점,,,접점이 안으로 들어가서 오른쪽 유닛만 충전이 잘 되지 않았다는 점,,나랑 비슷한 사람이 있었다,, 더군다나 충전 접점 불량 수리에 대한 포스팅은 별로 없었다..https://m.blog.naver.com/icaner/223137477475 에어팟 프로 충전 접촉불량 자가 수리 후기(그나마 이쁘게 뚜따하는 법)1. 이번 블로깅 내용은 에어팟프로 이어폰 충전불량 현상을 자가수리 한 내용 2. 나는 일기를 기록하듯이 ...blog.naver.com방법을 알려준 공돌아재님께 감사의 말씀을 올립니다..필자는 충전이 한 2년전부터 잘 안되서 핀셋으로 들어 ..

#1 에서는 윈도우 카카오톡 데이터 베이스 복호화 분석을 진행했다. #2 에서는 자동화 하는 기능을 소개하려고 한다. 일단 Pragma를 생성하기 위해서 레지스트리에 접근해야하지 않는가? def get_pragma() : DeviceInfo_Path = "Software\Kakao\KakaoTalk\DeviceInfo" keypath = winreg.OpenKey(winreg.HKEY_CURRENT_USER, DeviceInfo_Path, 0, winreg.KEY_READ) reg_path = winreg.QueryValueEx(keypath, "Last")[0] DeviceInfo_Key_Path = DeviceInfo_Path +"\\" + reg_path keypath = winreg.OpenKey..

본 글은 언제든지 비공개 되거나, 삭제될수 있음을 미리 알려드립니다. (뭐,, 카카오톡 본사에서 글 내려라 하지 않는 이상 없어지진 않지 않을까...?)모바일 메신저는 디지털 포렌식에서 핵심적인 증거원이지만, 대부분의 앱은 사용자 프라이버시 보호를 위해 메시지 데이터베이스에 암호화를 적용한다. 본 분석에서는 iOS 기반 카카오톡 앱에서의 암호화 방식과 그 복호화 가능성에 대해 다룬다. Message.sqlite 파일을 중심으로 접근하며, 관련 선행 사례 및 실험 결과를 종합하였다.아이폰 카카오톡 포렌식의 경우 이미 많은 상용도구에서 진행되고 있다. 예를 들어 MD-RED, Magnet Axiom, BelkaSoft Evidence X 등,, 하지만 아래 논문에서와 같이, 일부 상용도구에서는 데이터의 양이..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다.2024년 디지털 범인을 찾아라 경진대회가 열렸다.한국포렌식학회(회장 김영대)와 한국저작권보호원은 올해로 10회를 맞이하는 ‘2024 디지털 범인을 찾아라 경진대회’를 공동으로 개최한다고 밝혔다.‘디지털 범인을 찾아라 경진대회’는 디지털 포렌식 기술을 활용하여 첨단범죄 수사 역량을 강화하고, 디지털 포렌식 분야의 발전을 도모하는 것을 목적으로 한다. 이번 경진대회는 주니어 부문과 시니어 부문으로 나뉘어 진행되며, 주니어 부문은 전국 대학생 이하 학생들을 대상으로, 시니어 부문은 일반인 및 대학원생 이상 전문가를 대상으로 한다.대회 접수는 2024년 ..

오늘은 아이폰 기본 기능 중 "가리기" 기능을 통해서 가려진 사진도 포렌식이 되는지 확인해 보도록 하겠습니다. 가리기 기능은 갤러리에서 사진을 선택후 옵션 버튼을 통해서 가리기를 사용할 수 있습니다. 먼저 저는 6개의 사진을 가려보았습니다. 이제 분석을 진행해 보도록 하겠습니다. 먼저 Axiom을 실행시켜주고, 새로운 케이스 생성을 클릭해줍니다. 케이스 번호와, 케이스 유형, 파일 경로, 스캔한 사람에 대해서 작성해 주고, 증거 소스로 이동해 줍니다. 저는 미리 이미징을 떠두지 않고, 이미징과 동시에 분석을 진행해 보려고 합니다. 아이폰을 연결하고, 위 사진과 같이 증거를 탑재합니다. 아이폰이 탈옥이 되어 있다면, 전체 이미징 기능이 활성화 되있을 것입니다. 하지만 탈옥이 되어 있지 않다면, 빠른 이미징..

오랜만에 블로그에 글을 작성하는것 같네요,,아마 전체적으로 만드는데 1년 정도 걸린것 같은데, 개발된 프로그램에 대해 살짝 소개해보려고 합니다.먼저 목적은 아직 상용 포렌식 도구에서 안드로이드, 윈도우, 아이폰, 맥북을 통합적으로 지원하는 도구를 확인하지 못했습니다.(혹시라도 알고 계시다면,, 댓글로 알려주세요)그래서 통합 플랫폼 카카오톡 디비 복호화 도구를 제작해 보는건 어떨까 싶어서 한번 간단하게 제작해본 프로그램입니다.일단 시연 영상먼저,,,  먼저 주요 기능은 다음과 같습니다.1. 윈도우 PC에서 물리 기기 / 논리 폴더 설정 등을 통해 카카오톡 데이터 복호화2. 안드로이드 기기 연결 및 즉시 복호화 / 또는 백업 파일로 카카오톡 데이터 복호화3. 아아폰 기기 연결 및 즉시 복호화 / 또는 백업 ..

https://school.programmers.co.kr/learn/courses/30/lessons/389478?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이다른 사람 풀이를 보고 한숨을 쉬었던 문제이다..def solution(n, w, num): m1 = num%(w*2) m2 = ((w*2+1) - m1)%(w*2) # num 이상 n 이하의 수들 중 2*w로 나눈 나머지가 m1,m2인 것들의 수를 세면 된다. return len(range(num,n+1,w*2)) + len(range(num + (m2-m1)%(w*2), n+1, w*2..

본 글은 언제든지 비공개 되거나, 삭제될수 있음을 미리 알려드립니다. (뭐,, 카카오톡 본사에서 글 내려라 하지 않는 이상 없어지진 않지 않을까...?)모바일 메신저는 디지털 포렌식에서 핵심적인 증거원이지만, 대부분의 앱은 사용자 프라이버시 보호를 위해 메시지 데이터베이스에 암호화를 적용한다. 본 분석에서는 iOS 기반 카카오톡 앱에서의 암호화 방식과 그 복호화 가능성에 대해 다룬다. Message.sqlite 파일을 중심으로 접근하며, 관련 선행 사례 및 실험 결과를 종합하였다.아이폰 카카오톡 포렌식의 경우 이미 많은 상용도구에서 진행되고 있다. 예를 들어 MD-RED, Magnet Axiom, BelkaSoft Evidence X 등,, 하지만 아래 논문에서와 같이, 일부 상용도구에서는 데이터의 양이..

안녕하세요, 이번에는 1년전 저에게 맡기셨던 의뢰자분이 다시한번 연락을 주셨습니다.최근 새로운 기술 도입으로 복구률이 매우 증가하였고,이전에 의뢰하신분도 생각이 나서 바로 의뢰에 착수하였습니다.이 글은, 실제 데이터 복구 요청을 받아 작업을 진행하였습니다.해당 의뢰를 원하신다면 하단의 연락쳐로 연락주세요! 한달에는 많게는 4~5건, 여러건에 대해서 문의가 들어오고 있습니다.애플 공식 서비스센터에서는 1110 에러에 대해서는 초기화 밖에 답이 없다고 하지만,저는 의뢰자 분들의 소중한 데이터를 위해서 항상 연구 하고 있습니다.택배로 의뢰자 분의 기기를 받아보았으며, 2025년 5월 22일에 보내주셔서 5월 23일에 받아보게 되었습니다.택배가 오는 과정에서 손상이 없도록 뽁뽁이로 잘 감싸주셨습니다.외관상으로 ..

안녕하세요, 오랜만에 아이폰 1110 오류에 관해서 블로그 포스팅을 하게 되었습니다.그동안 수많은 복구 작업을 진행했는데, 오랜만에 생각나서 포스팅을 하게 되었습니다.이 글은, 실제 데이터 복구 요청을 받아 작업을 진행하였습니다. 해당 의뢰를 원하신다면 하단에 연락쳐로 연락주세요!최대한의 합리적인 금액으로 복구 및 수리를 도와드리고 있습니다.2025년 5월 11일 기준으로 현재, 1110오류에 대해서는 대략 70~80% 복구 성공률을 장담하고 있습니다.한달에는 많게는 4~5건, 여러건에 대해서 문의가 들어오고 있습니다. 애플 공식 서비스센터에서는 1110 에러에 대해서는 초기화 밖에 답이 없다고 하지만, 저는 의뢰자 분들의 소중한 데이터를 위해서 항상 연구 하고 있습니다.택배로 의뢰자 분의 기기를 받아보..

https://pental.notion.site/2-1a095991283980ae844cf0896916ac12?pvs=74 디지털포렌식 전문가 2급 실기 대비 | Notion본 자료는 2022년에 디지털 포렌식 전문가 2급 자격을 취득한 후, 향후 수험생분들에게 도움이 되고자 직접 제작한 것입니다.pental.notion.site 노션에서도 열심히 작업중입니다.해당 게시물은 디지털 포렌식 전문가 2급 자격증 취득을 도전하시는 분들의 공부에 도움이 되도록 작성한 게시물입니다.많은 관심 부탁드리겠습니다.다운로드 링크FAT32_MBR_RECOVERY.zip먼저 주어진 ZIP 파일에서는 FAT32_MBR_RECOVERY.001 이라는 파일이 존재한다.해당 파일의 정보는 다음과 같다.FILE NAME FAT32_..

https://pental.notion.site/2-1a095991283980ae844cf0896916ac12?pvs=74 디지털포렌식 전문가 2급 실기 대비 | Notion본 자료는 2022년에 디지털 포렌식 전문가 2급 자격을 취득한 후, 향후 수험생분들에게 도움이 되고자 직접 제작한 것입니다.pental.notion.site노션에서도 열심히 작업중입니다.해당 게시물은 디지털 포렌식 전문가 2급 자격증 취득을 도전하시는 분들의 공부에 도움이 되도록 작성한 게시물입니다.많은 관심 부탁드리겠습니다.다운로드 링크NTFS_MBR_RECOVERY.zip먼저 주어진 ZIP 파일에서는 NTFS_MBR_RECOVERY.001 이라는 파일이 존재한다.해당 파일의 정보는 다음과 같다.FILE NAME NTFS_MBR_..

https://pental.notion.site/2-1a095991283980ae844cf0896916ac12?pvs=74 디지털포렌식 전문가 2급 실기 대비 | Notion본 자료는 2022년에 디지털 포렌식 전문가 2급 자격을 취득한 후, 향후 수험생분들에게 도움이 되고자 직접 제작한 것입니다.pental.notion.site노션에서도 작업중입니다. 많은 관심 부탁드리겠습니다.디지털포렌식 전문가 2급 자격증은?자격증 개요자격증 명칭: 디지털 포렌식 전문가 2급주관 기관: 한국포렌식학회(Korean Society of Forensic Science)목적: 디지털 증거의 수집, 분석, 보존 및 법적 절차에 대한 전문성을 검증하기 위한 자격증대상: 법률, 수사기관, IT 보안, 기업 감사, 법무 분야 종사..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

본 글은 요청시 풀이 보고서가 내려갈 수 있으며,만약 저작권 등에 위반된다면, 지체없이 댓글 또는 pental@kakao.com 으로 연락주시길 바라겠습니다. 해당 블로그에서는 총 6개의 분석 섹션으로 나눠 포스팅을 할 예정이다. 각각 섹션은 다음과 같다. 현재 세션은 굵은 글씨로 표시되어 있다.1. 이미징 작업2. 손상된 파티션 복구3. 파티션 목록4. 아티팩트 분석    1. 운영체제 분석      1.1. PC 정보 분석      1.2. PC 사용자 분석      1.3. 설치된 프로그램 분석    2. 웹 아티팩트 분석      2.1. Chrome 분석      2.2. Edge 분석      2.3. Firefox 분석    3. Email 분석    4. 메신저 분석      4.1. Te..

# 백준 11723 - 집합import sysinput = lambda: sys.stdin.readline().rstrip()S = []M = int(input())for _ in range(M) : line = input().split() if len(line) > 1 : op = line[0] num = int(line[1]) if op == "add" : if num not in S : S.append(num) elif op == "remove" : if num in S : S.remove(num) elif op == "check" :..

# 백준 5522 - 카드 게임A = [int(input()) for _ in range(5)]print(sum(A))# 백준 10178 - 할로윈의 사탕T = int(input())for _ in range(T) : c, v = map(int, input().split()) print(f"You get {c // v} piece(s) and your dad gets {c % v} piece(s).")# 백준 9295 - 주사위T = int(input())for i in range(T) : a, b = map(int, input().split()) print(f"Case {i + 1}: {a + b}")# 백준 10569 - 다면체T = int(input())for _ in rang..

분류 : 구현링크 : https://www.acmicpc.net/problem/6666풀이문제집에서 이거 안풀면 꿈에서 나온다는 말이 있어서 찾아보게된 문제이며, 문제 번호부터가 6666으로 예사롭지가 않다.근데 진짜 문제도 예사롭지 않다.입력을 한번 봐보자+---+---+---+---+---+---+---+---+|.r.|:::|.b.|:q:|.k.|:::|.n.|:r:|+---+---+---+---+---+---+---+---+|:p:|.p.|:p:|.p.|:p:|.p.|:::|.p.|+---+---+---+---+---+---+---+---+|...|:::|.n.|:::|...|:::|...|:p:|+---+---+---+---+---+---+---+---+|:::|...|:::|...|:::|....

분류 : 백트래킹링크 : https://www.acmicpc.net/problem/2661풀이이 문제는 숫자 1, 2, 3 으로만 이루어지는 수열이 있으며, 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열은 나쁜 수열이라고 한다.좋은 수열은 인접한 두 개의 부분 수열이 동일하면 안된다. 즉 1212는 마지막 두자리 12가 반복되므로 나쁜 수열이다.길이 N의 좋은 수열 중 사전순으로 가장 앞서는 수열을 찾아야한다.def is_good(seq) : length = len(seq) for i in range(1, length // 2 + 1) : if seq[-i:] == seq[-2 * i : -i] : return False retu..

분류 : 자료구조링크 : https://www.acmicpc.net/problem/11279풀이백준 1927과 비슷한 문제이다. 1927 최소 힙 문제에서는 정석대로 heap에 값을 양수로 넣었지만, 이번 문제는 최대 힙을 구하는 문제이기에, -를 붙여서 음수로 넣어주면 힙에서는 최대 힙으로 정렬되게 된다.이때 문제점은 pop 할때도 음수로 나오기에, 다시한번 -를 붙여주면, 최대 힙으로 출력 할 수 있다.코드# 백준 11729 - 최대 힙import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = []for i in range(N) : x = int(input()) if x == 0 : if len(heap) > ..

분류 : 자료구조링크 : https://www.acmicpc.net/problem/1927풀이힙의 기초적인 문제이다. 사실 시간초과가 나긴했는데, sys.stdin.readline을 고려하지 못했다.문제에서는 N이 최대 10만개이기 때문에 단순히 input()으로만으로는 당연히 시간 초과가 날 수 밖에 없다.문제에서 N을 입력받고, 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 X가 주어진다고 한다.X가 0이 아닌 경우에는 배열에 자연수 X를 넣고, 0이라면 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하면 된다.이에 적합한 자료구조는 heap이기에 아래와 같은 코드로 작성하였다.코드# 백준 1927 - 최소 힙import heapqimport sysinput = sys.stdin.r..

분류 : DFS링크 : https://www.acmicpc.net/problem/16957풀이각 공이 어디로 떨어지는가가 아니라 각 골짜기로 얼마나 많은 공이 모이는가를 역방향으로 계산한다.각 칸에서 인접한 8방향 중 가장 낮은 칸으로 공이 흘러간다.그 흐름을 역방향 그래프로 만들어 두고, 실제로 공이 도달할 수 있는 최종 지점부터 시작해서, 역으로 DFS를 돌며 얼마나 많은 공이 이 칸으로 오는지 세는 방식이다.입력 처리R, C = map(int, input().split())B = [list(map(int, input().split())) for _ in range(R)]dr = [0, 0, 1, 1, 1, -1, -1, -1]dc = [1, -1, -1, 0, 1, -1, 0, 1]B[r][c]는 ..

분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/25214풀이각 인덱스 i에 대해, D[i]는 A[0]부터 A[i]까지의 최솟값, E[i]는 E[i-1]과 (A[i] - D[i]) 중 더 큰 값이다.즉, E[i]는 앞에서부터 지금까지의 최댓값을 유지하면서, A[i]에서 이전까지의 최솟값을 뺀 값 중 최대를 갱신한다.D = [0] * NE = [0] * ND[i]는 A[0] ~ A[i] 중 최솟값을 나타내고, E[i]는 지금까지의 A[i] - D[i] 중 최대를 나타낸다.D[0] = A[0]for i in range(1, N) : D[i] = min(D[i - 1], A[i])최솟값 갱신은 위와 같이 작성하며, D[i]는 A[0] ~ A[i]에서의 최솟값을..

분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/1311풀이이 문제는 N * N 크기의 비용 행렬 D가 주어지고, 사람 N명에게 각각 하나의 일을 배정하는데, 각 사람마다 각 일에 대한 비용이 다르다.각 사람에게 정확히 하나의 일만, 각 일도 정확히 한 사람에게만 배정되도록 하면서 총 비용의 합을 최소화 해야한다.초기 설정cache = [[-1] * (2 ** N) for _ in range(N)]cache[x][mask]는 x번째 사람까지 할당했을 때, mask 상태에서의 최소 비용을 저장한다.기저 조건if x == 0: for i in range(N): if mask == (2 ** i): cache[x][mask] =..

분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/7579풀이메모리 확보를 위해서 필요한 최소 비용을 구하는 문제다.앱 N개가 있고, 각각 메모리 m[i], 비용 c[i]를 가진다.총 확보해야 할 메모리는 M보다 크거나 같으며, 비용의 합이 최소가 되도록 하는 앱을 선택한다.DP 테이블은 다음과 같이 정의한다.D = [[0] * 10001 for _ in range(N)]D[i][j]는 i번 앱까지 고려했을 때, 비용 j 이하로 확보 가능한 최대 메모리를 나타내며, 비용 최대치가 10000이므로 열 크기를 10001로 설정한다.# D[0][i] : 첫 번째 앱만 사용할 때의 최대 메모리for i in range(c[0], 10001) : D[0][i] = ..

분류 : 브루트포스 + 자료구조링크 : https://www.acmicpc.net/problem/11578풀이1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.A = [list(map(int, input().split()))[1:] for _ in range(M)]A = [set(a) for a in A]각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.set(a)로 변환해서 나중에 합집한 연산을 쉽게 ..

분류 : 브루트포스링크 : https://www.acmicpc.net/problem/2450풀이배열 A에는 1, 2, 3이 섞여있으면서, 각각 모양을 나타낸다.이 배열을 구간 3개로 나누어서, 각 구간에는 한 가지 모양이 있도록 정렬해야 한다.예를 들어서 [2, 2, 1, 1, 3, 3] 과 같은 형태이다.단, 숫자들을 바꾸는 횟수를 최소화 해아한다.입력 처리는 다음과 같다.N = int(input())A = list(map(int, input().split()))A = [x - 1 for x in A] # 0, 1, 2 로 바꿈입력 배열을 x - 1을 통해서 0, 1, 2로 정규화한다.그후 각 숫자의 개수를 센다.count = [0] * 3for x in A : count[x] += 1예를 들어..

분류 : 이분 탐색 + BFS링크 : https://www.acmicpc.net/problem/1981풀이N x N 크기의 정수 배열 A가 주어짐(0, 0) → (N-1, N-1)까지 상하좌우로 이동 가능단, 이동하는 칸의 숫자는 어떤 [min, max] 구간에 속해야 함이때 max - min 의 최소값을 구하는 것이 목적문제 풀이 아이디어는 다음과 같다.배열의 값은 최대 200이므로 min ~ max 범위가 0~200 사이임max - min mid 값을 이분 탐색으로 줄여나가며 최소값을 찾는 방식초기 설정은 다음과 같이 진행한다.low, high = 0, 200answer = -1mid = max_val - min_val 을 이분 탐색으로 줄여 나갈 범위이다.이분 탐색을 시작한다.while low 현재..

분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/14567풀이총 N개의 과목이 주어지며, M개의 선수 조건이 주어진다.모든 과목에 대해 가장 빠른 이수 학기를 출력해야한다.N, M = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(M) : a, b = map(int, input().split()) a, b = a - 1, b - 1 adj[b].append(a)adj[b].append(a)는 b를 듣기 위해 a를 먼저 들어야 한다는 조건이므로, b에서 a로 역방향 간선을 저장한다.즉, b의 선수 과목들을 adj[b]에 저장한다.cache = [-1] * Ncache[i]..

https://www.acmicpc.net/problem/1719분류 : 다익스트라링크 : https://www.acmicpc.net/problem/1719풀이이 문제는 어느 경로로 가는 것이 최단 경로인지를 알아내는 문제이다.각 도시(정점) 간의 최단 경로를 찾아야하며, 단순히 최단 거리만 출력하는 것이 아니라, 어디로 먼저 가야 하는지를 출력해야한다.즉, i → j 로 갈 때 첫번째로 가야하는 도시를 출력해야하는 것ㅇ디ㅏ.from queue import PriorityQueueN, M = map(int, input().split()) # 도시 수 N, 도로 수 Madj = [[] for _ in range(N)] # 인접 리스트# 간선 정보 입력for _ in range(M): a, ..

https://www.acmicpc.net/problem/14284풀이이 문제는 조금 방향 없는 그래프, 즉 무방향 그래프가 주어지며, 정점수 N, 간선수 M이 주어진다.각 간선은 가중치를 가지며, 출발점 S에서 도착점 T까지의 최단 거리를 구하는 문제이다.이 문제에세의 핵심 알고리즘은, 단연코 다익스트라 알고리즘이라고 할 수 있다.먼저 가중치가 있는 그래프에서 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며, 이 문제에서는 특정 시작점에서 특정 도착점 까지의 거리만 구하면 된다.from queue import PriorityQueue우선순위 큐는 최소 거리 기준으로 정점을 꺼내기 위해서 위와 같이 사용한다.N, M = map(int, input().split())adj = [[]..

https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..

https://www.acmicpc.net/problem/20159풀이플레이어가 번갈아 가면서 카드를 가져간다.짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.psum0 = [0] * N # 내 차례에서의 누적합psum1 = [0] * N # 상대 차례에서의 누적합psum0[0] = A[0]psum1[0] = 0for i in range(1, N): if i % 2 == 0: # 내 차례 psum0[i] = psum0[i - 1] + A[i] psum1[i] = psum1[i - 1] else: ..

https://www.acmicpc.net/problem/29767풀이길이가 N인 정수 수열 A가 주어지며, 누적합(A[0]부터 A[i]까지의 합)을 구해 전체 N개의 누적합 중 K개를 선택해서 합을 최대로 만들어야한다.N, K = map(int, input().split())A = list(map(int, input().split()))N은 원소 개수, K는 선택할 누적합 개수를 입력 받는다.psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 A[0] + A[1] + … + A[i]를 의미하며, 즉, 누적합 배열을 만든다.psum.sort(reverse=True)print(sum(psum[:K]..

https://www.acmicpc.net/problem/1050풀이여러개의 기초 물약은 가격이 주어지고, 일부 물약은 다른 물약들로 조합하여 만들 있다.조합은 "LOVE=A+2B" 같은 형태로 주어진다.목표: 물약 “LOVE”를 만드는데 필요한 최소 비용 계산하는 것이다.N, M = map(int, input().split())stuff = {}N은 가격이 주어진 물약 수를 나타내며, M은 조합식 수를 나타낸다.for _ in range(N) : name, cost = input().split() cost = int(cost) stuff[name] = cost가격이 주어진 물약은 딕셔너리 stuff에 저장한다.formulas = [input() for _ in range(M)]LOVE ..