본문 바로가기

Algorithm🐰/백준61

[백준] Swift AC implementation, 문자열 문제 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 : 명령어 R과 D에 대해 각각 뒤집기, 첫 문자를 버리는 것을 메소드를 적용하면 된다. 하지만 R에 대해 문자열 reverse를 적용하면 시간복잡도가 O(n)이 걸리므로 * 근데 queue 자료구조를 직접 구현할땐 reverse가 O(1)이라고 했는데 잘 모르겠다 .. R 명령어가 등장할때, isReverse.toggle()로 뒤집혔는지 아닌지를 프로퍼티로 저장한다. 그리고 D명령어를 수행할때 역시 removeFirst()는 시간복잡도가.. 2022. 5. 13.

[백준] Swift 11052 카드 구매하기 DP 문제 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 분석 : Bottom-up 방식으로 접근했다. d[n] - i개의 카드를 구매시 지불해야 하는 금액의 최대값 n = 1이라면 arr[1]값을 리턴한다. 그리고 for문을 도는데 n = 2라면 max(d[1] + arr[1], arr[2]) 1개짜리 카드팩 샀을때의 최대값에 1개짜리 카드팩을 더 사는 경우, 2개짜리 카드팩을 사는 경우 중 최대 값을 저장한다. n = 3 -> max(d[1] + .. 2022. 4. 19.

[백준] Swift 1504 특정한 최단 경로 dijkstra 문제 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 분석 : 이 문제는 거쳐야 하는 노드가 2개로 한정적이어서 start -> 거쳐야하는 노드1 -> 거쳐야하는 노드2 -> end start -> 거쳐야하는 노드2 -> 거쳐야하는 노드1 -> end 둘 중 최소값을 찾으면 된다 !! 일반적인 다익스트라를 만들고 check() 함수를 통해 비교해줬다. Swift 코드 : // // main.swi.. 2022. 4. 18.

[백준] Swift 14503 로봇 청소기 시뮬레이션, DFS 문제 : https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 : 처음에 현재 위치 표시하는데 arr에 1값을 넣어서 계속 오류가 나서 1시간동안 헤맸다 .. 그리고 동, 서 구분을 반대로 해서 또 헤맸다 .. 방향 값만 잘 넣어준다면 DFS 푸는 방식대로 풀면 될거 같다 ! 왼쪽 방향으로 회전하려면 북 -> 서 // 서 -> 남 // 남 -> 동 // 동 -> 북으로 이동하면 된다. 따라서 0 -> 3, 3 -> 2, 2-> 1, 1 -> .. 2022. 4. 18.

[백준] Swift 케빈 베이컨의 6단계 법칙 BFS 문제 : https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 분석 : 처음에는 왜 이게 BFS지 ? 깊이에 따라 내려가니까는 DFS 아닌가 싶었다. 하지만 다시 생각해보니 우리는 깊이가 낮은 친구 관계가 있다면 이 값을 반환해야 한다. 따라서 깊이가 낮은 곳에 원하는 원소가 있다면 visit를 true로 만들어 더 깊은 곳에 원하는 원소가 있어도 방문하지 않고 넘어갈수 있게된다. 또한 자기 자신을 제.. 2022. 4. 17.

[백준] Swift 2302 극장 좌석 DP 문제 : https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 분석 : 처음에는 VIP 좌석만 따로 1로 배열을 받고 1을 기준으로 나눠 배열을 칸만큼 곱하면(한칸씩 이동하는 경우) 되는거 아닌가 ? 생각했다. 하지만 제출 후 틀리고 보니 배열칸만큼은 두사람끼리만 자리를 바꿨을때더라 ㅎ 만약 이러한 배열이 있을때 1,2,3,4 중 두 수 예를 들어 1,2만 자리 바꿨을때 모든 수에 대한 경우의 수는 원소의 개수만큼 4이지만 12가 자리를 바꾸는 사이 34도 자리.. 2022. 4. 17.

[백준] Swift 1309 동물원 DP 문제 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 분석 : 처음엔 N은 주어졌는데 사자의 수가 주어지지 않아서 어떻게 푸는건지 당황했었다. 근데 동물 수와 상관없이 모든 경우의 수를 구하는 것이었다. 그래서 동물이 한마리일경우, 2마리일 경우 .. 로 생각해보았는데 규칙을 찾기 쉽지 않았다. 결국 점화식 세우는 것이 도무지 감이 잡히지 않아 다른 블로그를 보고 풀었다 ㅜ 동물의 수가 아닌 문제에 주어진 조건 N을 가지고 나눠 생각해보자 우선 동물원의 N = 1인 경우, N번째 줄에 사자는 없다, 왼쪽, 오른쪽 이 3가지 경우의 수를 지닌다. N=1 -> 3 N = 2인경.. 2022. 4. 16.

[백준] 1049 Swift 기타줄 Greedy 문제 : https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 분석 : 단순한 구현 문제였다. 모든 브랜드 중에서 패키지와 단품으로 구매했을때 가격 비교를 통해 최소값을 choose 변수와 select에 저장한 뒤, n의 값을 줄여나가며 minPrice를 업데이트 한다. Swift 코드 : // // main.swift // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2022/04/13. // import Foundat.. 2022. 4. 13.

[백준] Swift 20361 일우는 야바위꾼 implementation 문제 : https://www.acmicpc.net/problem/20361 20361번: 일우는 야바위꾼 첫째 줄에 N (3 ≤ N ≤ 200,000), X (1 ≤ X ≤ N), K (1 ≤ K ≤ 100,000)가 공백으로 구분되어 주어진다. 둘째 줄부터 K개의 줄에는 순서대로 바꾼 두 컵의 위치 Ai, Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi)가 공백 www.acmicpc.net 분석 : 구슬이 있는 위치를 true로 하는 배열을 만들까 하다가 위치를 변수로 업데이트 해줄수 있을 거 같아서 배열을 안쓰고 풀었다 ! Swift 코드 : // // main.swift // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2022/04/12. // import Founda.. 2022. 4. 12.

[백준] Swift 9466 텀 프로젝트 DFS 문제 : https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 분석 : 학생들이 cycle을 이루는지 파악하기 위해 DFS로 접근해야 한다. 처음에 접근한 방식은 while문을 통해 dfs 탐색을 하고자 했지만 visit를 검사해주지 않아서 시간초과가 났다. 그래서 블로그를 참고해 다시 풀었다 ㅠ 일반적으로 방문한 노드인지 확인을 위해 visit배열을 사용하는데 여기서는 done(팀을 이루었는지 아닌지)도 배열을 하나 새로 만든다. 같이 프로젝트 하고 싶.. 2022. 4. 12.

[백준] Swift 2529 부등호 backtracking 문제 : https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 분석 : 혼자서 풀지 못했다 .. ㅜ 부등호의 조건을 만족하는 중복 없는 조합을 구하는 문제였다. 그러한 조합들 중 최대 값, 최소 값을 구하는 게 답이였다 ! 우선 부등호 개수 + 1개만큼의 숫자를 사용한다. 조건 만족시 answer 배열에 담는다. 그리고 for 문 0 ~ 9 10개의 숫자에 대해 첫번째 숫자일 경우는 부등호 조건을 체크하지 않고 바로 숫자를 넣는다. 그 다음 index가 1이상일.. 2022. 4. 7.

[백준] Swift 1300 k번째 수 BS(Bineary Search) 문제 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 : 문제를 직접 풀진 못했지만, 신기한 풀이가 있어서 기록을 남겨보려구 한다. 문제는 2차원 N*N 배열 값을 1차원 N*N배열로 바꾸었을때 k번째 인덱스의 값(m)을 구하는 문제였다. 예를 들어서 N = 4 배열이 있을때, 이를 1차원 배열로 늘여보면 이렇게 될 것이고 그러므로 이를 이분 탐색으로 접근 할 수 있는 것이다. 사실 선형 탐색으로 찾으려 .. 2022. 3. 31.

[백준] Swift 1806 부분합 투포인터 문제 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 : 연속된 배열의 부분 배열 중 그 합이 M 이상이 되는 부분 배열 중에서 길이가 짧은 배열의 길이를 출력하는 문제다. startIndex와 endIndex를 첫 인덱스에 위치하도록 두었고, sum 값은 원소 초기값으로 설정했다. 그리고 while문을 돌때마다 endIndex값은 하나씩 증가시킨다. 그리고 sum 값이 M보다 큰 경우가 발생한다면 길이를 줄일 수 있을만.. 2022. 3. 29.

[백준] Swift 2468 안전 영역 BFS 문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 분석 : 문제의 안전 영역의 정의를 처음엔 이해하기 어려웠다. 그래서 얼만큼의 장마가 내린다구 ? 했는데 모든 장마 경우의 수를 다 검사해 안전 영역이 최대가 될때 안전 영역의 개수를 출력하라는 뜻이었다. bfs를 돌아 visit배열에 false인 영역을 true로 만들고 끝내고 오면 bfsAll 함수에서 하나씩 cnt + 1 하여 안전 영역의 개수를 구해준다. 그 전에 visit 배열을 안전 .. 2022. 3. 11.

[백준] 1516 게임 개발 문제 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 : 먼저 개발할 것이 있다는 점에서 위상 정렬 문제다. 👉🏻 위상정렬 알고리즘 자신의 노드로 향하는 다른 노드가 있을때 그 노드를 v[자신].push_back(향하는 노드)로 넣어줬다. 그리고 향하는 들어오는 노드의 값을 증가시켜줬다. (개념과 반대다) 즉 indegeree[향하는노드]++ 따라서 값을 도식화 하면 아래와 같다. 그리고 indegree가 0인 값부터 vec.. 2022. 3. 3.

[백준] 2630 색종이 만들기 문제 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 : 다음과 같이 색종이가 있을때 정사각형 크기로 나눠 색종이가 모두 파란면을 또는 하얀면을 띄게 하는 작은 정사각형 색종이로 만들고 만들어진 흰 색종이 개수, 파란 색종이 개수를 출력하는 문제다. 즉 분할 정복을 통해 탑다운 방식으로 나눠진 색종이가 조건에 맞는 색종이인지 검사하면 된다. 색종이 크기가 1x1일때까지 반복하므로 재귀를 통해 해결할수 있었다... 2022. 2. 24.

[백준] 3020 개똥벌레 prefix sum(누적합) 문제 : https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 분석 : 1. 석순과 종유석의 구분은 짝수인지 홀수인지다. 따라서 개똥벌레가 높이 1인 곳을 지난다면 종유석은 1인 높이, 석순은 H -1 인 높이를 동시에 지난다고 생각하면 된다. 2. 석순끼리의 (또는 종유석끼리의) 순서 바뀜은 상관이 없다. 개똥벌레는 N 길이를 통과하야 하기 때문이다. 석순의 길이만큼 가진 석순 개수를 배열에 저장한다. (종유석도 똑같다) 3. 높이가 H일때 개똥벌레는.. 2022. 2. 21.

[백준] 13549 숨바꼭질 3 dijkstra 문제 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 : 숨바꼭질1 문제와 달리 이벤에는 순간이동(M x 2)시 시간은 0초라는 조건이 다르다. 즉 걷기(M-1, M+1) 조건시의 가중치와 순간이동의 가중치가 달라 최소 시간을 구하기 위해선 순간이동이 우선시 되어야 했고 거리가 작은순으로 정렬해주는 우선순위큐를 사용해 다익스크라를 적용했다. 가지 않았던 위치거나 또는 전에 갔을때의 시간보다 더 적게 걸.. 2022. 2. 17.

[백준] 1018 체스판 다시 칠하기 brute force 문제 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 : 인풋으로 주어진 배열과 주어진 8x8 배열과 cnn 모델처럼 필터링하듯이 비교하는 문제였다. 따라서 브루트포스로 비교할 체스판의 범위를 먼저 정하고, 블랙으로 시작하는 체스판 or 흰색으로 시작하는 체스판 두가지 경우의 수와 대조하여 min 값을 찾아낸다. 우선 for문이 많다는 점에 시간 초과가 날까 걱정했지만 체스판의 크기 M x N 와 (50 x 50)과 만든 체스판.. 2022. 2. 17.

[백준] 1969 DNA 문제 : https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 : 감으로 열간 비교를 통해 가장 많이 나온 문자가 그 자리 인덱스라는 것을 알았지만 문자간의 거리의 차를 모두 더하는 것이 어떻게 하면 좋을지 방법이 생각나지 않았다. 그러다 https://gusdnr69.tistory.com/31 요 블로그를 참고해 문자와 달랐던 값을 열로 카운트 했다는 점이 신기했다. (아직도 배울게 너무 많다니 많.. 2022. 2. 16.

이전 1 2 3 4 다음

티스토리툴바