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)인데..

1865번: 웜홀

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

배달

배달사용 언어: C++문제 요약한 마을에 N개의 마을(지점)이 있고, 도로(양방향, 이동 시간)가 존재합니다.각 마을에서 배달을 하려고 할 때, 제한 시간 K 안에 도달 가능한 마을 수를 구하는 문제입니다.핵심: 최단 거리 계산 후, 거리 ≤ K인 마을 수를 세기.다익스트라 설명시작 지점인 첫 번째 노드에서 도달 가능한 모든 마을을 구하려는 문제이므로, 다익스트라로 풀어야한다.다익스트라는 다음과 같이 간단하게 요약할 수 있다.다익스트라 요약1. 단일 출발점 최단 거리 알고리즘2. 가중치가 양수인 경우 사용 가능 (음수는 벨만포드)3. 우선순위 큐 활용 -> 최소 거리 노드부터 처리다익스트라 구현 흐름1. 거리 배열 초기화vector dist(N+1, INF); // INF or 1e9 같은 큰 숫자dis..

트라이 : Trie

트라이 : Trie사용 언어: C++트라이란?트라이(Trie)는 문자열을 효율적으로 저장하고 탐색하기 위한 트리 기반 자료구조다.특히 문자열 집합에서 접두어(prefix) 관계를 다루는 문제에 적합하다. 예를 들어 "119", "97674233", "1195524421" 같은 전화번호가 있을 때,트라이는 각 번호를 글자 단위로 쪼개어 루트에서 차례대로 연결하는 방식으로 저장한다.root └── '1' └── '1' └── '9' (끝 표시, isEnd = true) └── '5' └── '5' ...이 구조 덕분에 특정 문자열이 다른 문자열의 접두어인지 빠르게 판별할 수 있다.기본 구조 (node)트라이는 각 노드에..

전화번호 목록

전화번호 목록사용 언어: C++문제 요약전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119박준영 : 97 674 223지영석 : 11 9552 4421전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항phone_book의 길이는 1 이상 1,000,000 이하입니다.각 전화번호의 길이는 1 이상 20 이하입니다.같은 전화번호가 중복해서 들어있지 않습니다.입..

17070번: 파이프 옮기기 1

17070번: 파이프 옮기기 1사용 언어: C++문제 요약문제 요약이 어려우므로 문제 확인 요망풀이DP로 테이블을 채우면서 파이프를 옮기면 해당 칸 업데이트.dp[r][c][dir]: 파이프 끝이 (r, c)에 있고, dir 방향일 때의 경우의 수. (dir 0 : 가로, 1 : 세로, 2 : 대각선)예를 들어 시작이 (1,1), (1,2)에 파이프가 하나 있으니까 dp[1][2][0] = 1;로 초기화하는 것.또한, 이 문제는 오른쪽과 아래, or 오른쪽-아래로만 움직이니까 dp[1][2]면 자동으로 (1,1)에 다른 쪽 파이프가 있다고 가정 가능.답#include #include using namespace std;int N;int house[17][17];int dp[17][17][3];int ma..