1300번: K번째 수

1300번: K번째 수사용 언어: C++문제 요약세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다.풀이문제를 보고 처음 접근한 방식은 배열의 모양에서 규칙을 찾으려고 했습니다. i+j 값이 같은 대각선끼리 묶으면 뭔가 규칙이 있는 것 같아서 그런 식으로 가설을 세웠는데"i+j 값이 작은 대각선에 있는 숫자들은 i+j 값이 큰 대각선의 숫자들보다 항상 작을 것이다", 를 가정하고 예시를 보는데, 보니까 값의 크기 순서는 대각선의 순서와 전혀 상관이 없더군요. 그래서 필요한 것이 발상의 전화!배열을 직접 만들 ..

2609번: 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수사용 언어: C++문제 요약두 수의 최대공약수와 최소공배수를 출력하라!풀이문제는 브론즈 수준이지만, 일단 최대공약수와 최소공배수를 구하는 가장 효율적인 방법을 아는 것은 중요한 법!유클리드 호제법을 통해 최대공약수(GCD)를 구하고, 이를 이용해 최소공배수(LCM)를 구할 수 있다. 유클리드 호제법은 다음과 같다.두 수 a, b의 GCD는 다음 재귀 공식으로 구한다.GCD(a, b) = {a (if b =0) {GCD(b, a%b) otherwise코드로 표현하면 다음과 같다.int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b);}그리고 LCM는 GCD를 이용해서 ..

섬 연결하기

섬 연결하기사용 언어: C++문제 요약n개의 섬이 있고, 각 섬 사이를 연결하는 다리 건설 비용이 주어집니다.목표: 모든 섬이 서로 통행 가능하도록 만들면서 총 비용을 최소화조건:다리를 여러 번 건너도 통행 가능하면 됨같은 연결은 중복 없음연결할 수 없는 섬은 존재하지 않음즉, 모든 섬을 최소 비용으로 연결하는 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다.MST 문제 접근법MST 문제를 해결하는 대표 알고리즘이 두 개 정도가 있는데1. 크루스칼 알고리즘2. 프림 알고리즘여기서 어떤 알고리즘을 선택하냐? 간단하게 정리하면 간선 개수가 V, 정점 수가 E라 할 때 크루스칼 알고리즘은 시간복잡도가 O(ElogE)이다.프림 알고리즘은 시간복잡도가 O(VlogV + ElogV)인데..

1300번: K번째 수

1300번: K번째 수사용 언어: C++문제 요약세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다.풀이문제를 보고 처음 접근한 방식은 배열의 모양에서 규칙을 찾으려고 했습니다. i+j 값이 같은 대각선끼리 묶으면 뭔가 규칙이 있는 것 같아서 그런 식으로 가설을 세웠는데"i+j 값이 작은 대각선에 있는 숫자들은 i+j 값이 큰 대각선의 숫자들보다 항상 작을 것이다", 를 가정하고 예시를 보는데, 보니까 값의 크기 순서는 대각선의 순서와 전혀 상관이 없더군요. 그래서 필요한 것이 발상의 전화!배열을 직접 만들 ..

2609번: 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수사용 언어: C++문제 요약두 수의 최대공약수와 최소공배수를 출력하라!풀이문제는 브론즈 수준이지만, 일단 최대공약수와 최소공배수를 구하는 가장 효율적인 방법을 아는 것은 중요한 법!유클리드 호제법을 통해 최대공약수(GCD)를 구하고, 이를 이용해 최소공배수(LCM)를 구할 수 있다. 유클리드 호제법은 다음과 같다.두 수 a, b의 GCD는 다음 재귀 공식으로 구한다.GCD(a, b) = {a (if b =0) {GCD(b, a%b) otherwise코드로 표현하면 다음과 같다.int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b);}그리고 LCM는 GCD를 이용해서 ..

1865번: 웜홀

1865번: 웜홀사용 언어: C++문제 요약시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.벨만-포드 설명문제를 읽어보면 간단하게 정리하자면 출발점으로 돌아왔을 때 시간이 역행하는 경로가 있냐 -> 즉, 음수 사이클이 존재하는지 확인하는 문제.벨만-포드 요약1. 단일 출발점 최단 거리 계산 알고리즘2. 음수 간선 포함 가능3. 음수 사이클 탐지 가능구현 흐름1. 거리 배열 초기화vector dist(N+1, 0); // 모든 노드를 시작점처럼..