본문 바로가기

c++33

[백준 11728] 알고리즘 108일차 : 배열 합치기 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net C++ 투포인터 투포인터문제인데 전의 유형들과는 다른 문제 정렬되어 있는 두 배열을 하나의 정렬된 배열로 (정렬 알고리즘을 쓰지 않고) 합치는 문제 이걸 1학년때 프로그래밍 과목 과제로 나왔었다. 정말 똑같음 접근방법 두개의 배열을 합치는데 배열 당 하나씩 포인터를 갖는다. 정렬되어있는 배열이라고 했으므로 앞부터 하나씩 비교해서 작은 값을 결과 배열에 넣으면된다.. 2021. 7. 23.
[백준 1475] 알고리즘 93일차 : 방 번호 www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net C++ 구현 오늘은 2020-21 동계 알고리즘 스터디 마지막날 하지만 쉬어갑니다 :) 6과 9를 뒤집어서 이용할 수 있다는 점이 포인트인 문제 접근방법 기본적으로는 모든 숫자들이 필요한 개수를 배열에 저장하고 그 중에 가장 큰 값이 필요한 숫자 세트의 개수이다. 근데 6과 9는 예외적으로 생각해줘야하니까 마지막에 6의 개수를 저장하고 있는 곳에 9의 개수를 더하고 2로 나눈후 올림해준다. 그리고 9의 개수를 저장하고 있는 곳의 값을 0으로 바꿔준다. 그리고 나서 0부터 9까지의 숫자 개수 중 가장 .. 2021. 2. 26.
[백준 1158] 알고리즘 92일차 : 요세푸스 문제 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net C++ 큐 이번주 후반부는 쉬어갑시다 접근 방법 K번째 사람을 큐에 순서대로 넣고 마지막에 큐에서 빼면서 출력했다. 아직 큐에 넣지 않은 사람(방문하지 않은 인덱스)이 나올때마다 cnt++을 해주고 cnt가 k가 되면 그 사람을 큐에 넣고 cnt를 0으로 초기화했다 인덱스가 n의 범위를 넘어가면 안되므로 i = (i+1)%n으로 해줬다. 오답노트 i를 증가시키는 코드를 if문 안에 넣어놔서 무한루프가 돌았었다. 소스코드 #include #include using namespace std; bool vi.. 2021. 2. 25.
[백준 13305] 알고리즘 91일차 : 주유소 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net C++ 그리디 알고리즘 좀 쉬어가려고 그리디 풀었는데 그리디 무려 5개월만에 풀어서 좀 낯설었다. 접근방법 지금까지의 최저가를 갖고 가다가 그 최저가 보다 더 적은 값을 만나면 거기까지는 지금까지의 최저가로 주유해서 간 다음 그 이후부턴 그 주유소에서 주유하는 식 오답노트 거리랑 금액이 모두 최대가 int최대범위여서 total금액과 중간중간 거리를 더하는 변수는 long long 타입을 써줘야한다.. 2021. 2. 24.
[백준 1707] 알고리즘 89일차 : 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net C++ BFS 그래프 문제 접근방법 일단 정점을 담는 두 집합이 있다고 가정하고, 처음엔 그래프를 탐색하면서 인접한 노드는 다른 집합에 넣고 마지막에 두 집합의 교집합이 공집합이 아닌지 확인해서 결과를 출력했다. 근데 이렇게 하면 우선 이 문제에서 그래프는 모든 경우 연결그래프라고 가정하고 있지 않고, 무엇보다 시간초과가 났다. 그래서 갈아엎었다 ^_^ 방문여부를 저장하는 배열에 0,-1,1을 저장.. 2021. 2. 22.
반응형