알고리즘6 [알고리즘] 쇠막대기 문제 링크 문제명 : https://www.acmicpc.net/problem/10799 문제탐색기본 원리 탐색입력된 문자열을 순차적으로 처리하면서 정답을 도출해 내야합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.문자열 최대수 : 10만시간복잡도가 O(n²) 인 알고리즘은 약 100억회의 연산이 필요하므로 시간복잡도를 초과하게 됩니다.2중첩이상의 for문은 불가합니다. => stack을 활용하여 한번의 for문으로 "구현" 합니다. 코드설계하기라인을 입력받습니다.아래 규칙에따라 반복문을통해 문자열을 순회합니다.( 다음항목이바로 ) 일경우 레이저로 판단레이저가 아닌경우 ( 이 나오면 리스트에 값 1 하나 추가하며 정답에 +1만약 레이저로 판단될시, 리스트의 길이만큼 .. 2025. 4. 8. [알고리즘] 결혼식 문제 링크 결혼식 : https://www.acmicpc.net/problem/5567 문제탐색기본 원리 탐색상근이를 기점으로 구성된 양방향 그래프에서 거리가 2인 노드수를 구하는 문제입니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.동기의 수 : 500명거리가 2인 노드를 탐색하려면 범위탐색에 좋은 BFS를 사용할 수 있습니다. BFS의 시간복잡도는 O(N+m)으로 약 1만회로 문제없습니다. 하지만 거리가 2로 고정되어 있으므로 간단하게 그래프를 인접리스트로 구현한 뒤 상근이 친구의 친구들을 모두 집합으로 묶는 방법을 사용합니다.=> 인접리스트를 활용한 집합연산을 수행합니다. 코드설계하기입력을 인접리스트로 받습니다.집합에 상근이와 상근이 친구를 포함합니다.상근이 친.. 2025. 1. 23. [알고리즘] 도비의 난독증 테스크 문제 링크도비의 난독증 테스크 : https://www.acmicpc.net/status?user_id=dlehdql&problem_id=2204&from_mine=1 문제탐색기본 원리 탐색주어진 영단어를 사전순으로 정렬해야합니다.단, 대문자 소문자를 구분하지 않는다는것을 유의해야합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.최대 단어 수 : 1000 파이썬 정렬함수 sorted 의 시간복잡도는 O(n log n) 3000회 으로 시간복잡도상 문제는 없습니다. => sorted함수를 사용하여 정렬을 수행합니다.단, 모두 소문자로 변환하여 대소문자 구분을 없앱니다. 코드설계하기아래 과정을 n=0일때까지 반복합니다.단어를 입력받으면서 소문자로 변환한 것과 같이 리스.. 2025. 1. 22. [알고리즘] 촌수계산 - 그래프 문제 링크촌수계산: https://www.acmicpc.net/problem/2644 문제탐색기본 원리 탐색두 사람의 촌수를 구한다는 것은, 그래프에서 두개 지점의 거리를 구하는 것과 같습니다.단, 친척관계가 없다면 (그래프가 이어져있지 않다면) -1을 출력해야 합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.최대 사람 수 : 100 BFS혹은 DFS로 그래프를 탐색할때 시간복잡도는 O(N+M)이며 이 문제는 부모가 1명만 존재하므로 M은 N보다 클수 없는 트리구조를 따르고 있습니다. 그러므로 시간복잡도는 입력을 포함해 O(2N+M) = 300회 미만으로 충분합니다. => BFS,DFS모두 사용할 수 있지만, 두 지점사이 거리를 구하는 문제(최단거리) 이므로 B.. 2025. 1. 21. [스터디] 알고리즘 스터디 후기 처음 알고리즘 스터디를 시작하게된 계기는 KT 에이블스쿨에서 제공해주는 플랫폼에 "스터디그룹 모집"을 할 수 있는 게시판이 있었고, 평소에 알고리즘에 대해 모르던 내가 KT 에이블스쿨에 합격하기위해 부랴부랴 준비했었기에..ㅠㅠ 내게 부족한 부분을 채우고자 다짐했던 이번 교육기회에 알고리즘 스터디에 참여하자! 라고 생각하여 8월 초부터 6명의 팀원과 함께 시작을 하게 되었다. 첫시간에 모여서 여러가지 계획을 하였고 아래와 같이 룰도 만들었다.!(정리해주신 조장님 감사합니다) 우선 처음에는 아래와같이 계획을 짜고 전체적인 알고리즘들을 맛보는(?) 시간을 가졌고, 스터디를 위해 "이것이 코딩 테스트다" 책도 구매하였다. 최근에는 KT 에이블스쿨에서 진행하는 코딩테스트를 준비하기위해 같은 플렛폼인 "프로그래머스.. 2022. 11. 15. [교육후기]KT AIVLE School 코딩마스터스 그랜드마스터 달성! 제1회 코딩마스터스가 끝나고 점수를 결산한 결과 그랜드 마스터를 달성하였다..! 소정의 상품(치곤 비싼) 키보드 와 웹캠을 같이 선물로 주셨는데 마침 필요했던 것이여서 너무 행복했다. 코딩문제를 푸느라 밤도 새면서 했던 기억이 새록새록한데 그에 보답하는듯 뿌듯한 기분이였다. AIVLE School에서 진행하는 이벤트의 취지가 정말 좋은게, 평소에는 반 의무적으로 숙제하듯이 알고리즘 공부를 했었는데, 이런 이벤트를 진행하니 공부에 목표도 생기며 재미가 붙어서 많은 성장을 했던것 같다. 앞으로 또 코딩마스터스도 있고 다양한 이벤트들이 많이있으니 많이 참여해야겠다.! 2022. 9. 26. 이전 1 다음
