본문 바로가기
반응형

분류 전체보기163

for else / while else 사용 방법 알고리즘 문제를 풀다보면 이런 형태의 문제를 보게 됩니다. 정답이 있으면 정답을 출력하고, 답이 없다면 "No"를 출력하시오. 즉 답의 출력을 요구하면서 답이 없는 경우에 특정한 값을 출력하는 경우 입니다. 문제 예 입력값 리스트에 1, 9, 25, 49, 81의 숫자가 있습니다. 7의 배수가 있으면 해당 값을 출력하고, 없으면 No를 출력하세요. 아주 간단한 문제 예 입니다. 이 문제를 풀기 위해서 이렇게 답을 작성할 수 있습니다. a = [1, 9, 25, 49, 81] check = True for i in a: if i % 7 == 0: print(i) check = False break if check: print("No") 리스트 a에 있는 값들을 확인하여 출력을 합니다. 문제는 답이 없을 경.. 2023. 10. 16.
[백준 4195] 친구 네트워크 문제 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 간단한 유니온 파인드 문제 입니다. 기존의 유니온 파인드와 다른 두 가지 때문에 쉽게 문제를 풀 수 없습니다. 그럼 문제점을 파악해보고 문제를 풀어보도록 하겠습니다. 문제점 이 문제의 가장 큰 문제는 노드가 숫자가 아닌 친구 이름이라는 것입니다. 해결할 수 있는 여러가지 방법이 있겠지만 저는 딕셔너리를 이용하여 해결하였습니다. 다음으로 친구가 몇명이 있는지 알아야 합니다... 2023. 10. 13.
[백준 25405] 2022년 정보 올림피아드 2차 "레벨 업" 문제 출처 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 이 문제는 2022년 정보올림피아드 2차 중등부 4번, 고등부 3번 문제로 출제되었습니다. 레벨의 균형을 맞춰가며 올리는 문제 입니다. 매번 트레이닝 할 때마다 레벨이 낮은 K개의 캐릭터의 레벨을 1씩 M번 올리면 해결 되는 간단한 문제 입니다. 문제는 캐릭터가 총 10만이고, K값의 최대값도 10만이며 올려야하는 레벨의 최대값은 10억이라는 것입니다. 따라서 .. 2023. 10. 11.
[백준 11437] LCA 문제 출처 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 가장 기본적인 형태의 LCA 문제 입니다. LCA 알고리즘의 설명은 이전에 게시한 알고리즘 설명으로 대신하겠습니다. 2023.10.06 - [알고리즘 설명] - 최소공통조상(LCA) 최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리.. 2023. 10. 10.
최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리즘 입니다. 위와 같은 그래프가 있을 때 6번 정점과 9번 정점의 최소 공통 조상은 3번 입니다. 우리는 눈으로 바로 3번이 최소 공통 조상이라는 것을 찾을 수 있지만 알고리즘으로 이를 찾으려면 쉽지 않습니다. 어떻게 찾을 수 있을지 한번 생각해 보고 다음을 읽어보시기 바랍니다. 알고리즘 이해하기 최소 공통 조상을 찾는 방법은 하나씩 자신의 부모를 타고 올라가다가 공통으로 만나는 첫 번째 정점을 찾는 것입니다. 8번과 9번의 최소 공통 조상을 찾는다고 해보겠습니다. 두 정점의 부모를 찾아 올라갑니다. 먼저 8의 부모인 5와 9의 부.. 2023. 10. 9.
[백준 9465] 스티커 문제 출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 간단한 DP 문제 입니다. DP에 대해 잘 모른다면 어렵게 느껴질 수 있습니다. 스티커의 품질이 좋지 않기 때문에 어떤 스티커를 떼면 그 스티커의 상, 하, 좌, 우에 있는 스티커는 사용할 수 없습니다. 따라서 왼쪽부터 첫 번째 줄의 스티커를 떼었을 때, 두 번째 줄의 스티커를 떼었을 때, 아무것도 떼지 않았을 때, 이렇게 세가지의 경우를 생각해서 문제를 해결해야 합니다... 2023. 10. 5.
[백준 1976] 여행 가자 문제 출처 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행을 갈 수 있는지, 없는지 확인하는 문제 입니다. 문제를 보면 쉽게 도시들을 DFS를 통해 방문이 가능한지 불가능한지 따지면 해결될 것으로 보입니다. 하지만 이렇게 문제를 풀게 되면 시간초과가 발생할 수 있습니다. 왜냐하면 의도적으로 끝에서 끝으로 이동하는 경로만 입력이 들어온다면 방문하는데 시간이 오래걸릴 수 있습니다. 따라서 이 문제는 DFS가 아니라 유니온 파인드, 즉 분리.. 2023. 10. 4.
[백준 15686] 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다. 알고리즘 지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루.. 2023. 9. 27.
[알고리즘]Merge Sort 병합 정렬이라고 불리는 머지 소트(Merge Sort)에 대해 알아보겠습니다. 다양한 정렬 알고리즘이 있지만 다빈치코딩 알고리즘에는 이분 정렬에 대해서만 소개했었습니다. 이유는 어짜피 시간복잡도가 비슷하고 이분 탐색만 알아도 정렬에 관한 문제를 푸는데 큰 어려움이 없기 때문입니다. 하지만 Inversion Counting 에 대해 소개하고 세그먼트 트리로 푸는 방법만 알려주고, 정작 Inversion Counting 으로 풀 수 있는 문제 버블 소트를 풀 때에는 Merge sort 로 해결하였던 것이 생각나 merge sort에 대해서도 설명해야 겠다는 생각을 하였습니다. Merge Sort 란? 위키피디아에 있는 merge sort의 설명 이미지 입니다. 분할 정복과 비슷한 형태로 진행되는 것을 알 수.. 2023. 9. 26.
반응형

티스토리툴바