본문 바로가기

Algorithm🐰96

[백준] 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 자물쇠와 열쇠 2020 kakao 문제 : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr swift 코드 : // // main.swift // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2022/05/12. // import Foundation func rotation(_ arr: [[Int]]) -> [[Int]] { // 시계 방향으로 90도 회전 var resultArr = Array(repeating: Array(repeating: 0, count: ar.. 2022. 5. 13.

[프로그래머스] Swift 파괴되지 않은 건물 누적합 문제 : https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 참고 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%.. 2022. 5. 2.

[프로그래머스] Swift 오픈채팅방 2019 kakao 문제 : https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 분석 : 확실히 swift는 c++보다 문자열 파싱에 있어서 유용한것 같다 ! 그래서 아이디어만 생각나면 구현하기 수월하다는 생각을 다시한번 하게 되었다. swift 짱 ..👍 이 문제는 문자열 파싱 및 구현 문제로, 오픈 채팅방에 들어왔을때, 나갔을때, 이름을 변경했을때의 명령어를 처리해주면 된다. 기존 톡방 참여자가 이름을 변경하고 다시 들어오게 되.. 2022. 5. 2.

[프로그래머스] C++ 디스크 컨트롤러 문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 : 디스크 스케줄링하는 문제였다. input으로 [[0,3], [1, 9], [2, 6]] (요청 시간, 작업 소요 시간)이 주어졌을때 이들을 가장 짧게 작업을 끝내는 시간 / 3 하여 평균 시간을 구해주는 문제였다. 우선은 작업 소요 시간이 짧은 것을 먼저 처리하기 위해서 우선순위큐를 사용했다. 작업은 요청시간이 짧은 순으로 sorting .. 2022. 4. 22.

[프로그래머스] Swift 2022 kakao 주차 요금 계산 문제 : https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 분석 : string 파싱을 이용한 구현 문제였다. C++에서는 시간을 구하는데 * 60을 하는 등 되게 복잡했는데 swift는 DateFormatter()가 있다 히히 그래서.. 2022. 4. 19.

[백준] 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.

[프로그래머스] Swift 카카오 2022 k진수에서 소수 개수 구하기 implementation 문제 : https://programmers.co.kr/learn/courses/30/lessons/92335?language=swift 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 분석 : swift에는 진수 변환을 쉽게 해주는 함수가 있다. 그래서 다른언어보다 간결하게 푼거 같다 Swift 코드 : // // main.swift // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2022/04/15. // import Found.. 2022. 4. 15.

[프로그래머스] Swift 수식 최대화 문제 : https://programmers.co.kr/learn/courses/30/lessons/67257?language=swift 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 난이도 : level2 분석 : *, -, + 3개의 연산자를 가지고 수식을 최대화 하는 연산자의 우선순위를 적용해 최대값을 리턴하는 문제다. 나는 수식이 3개밖에 없어서 (3! => 6) 가능한 경우의 수를 손코딩하였다. 그리고 연산자가 등장하는 순서대로 op배열에 담았고 가능한 우선순위를 모두 계산해 result배열에서 .. 2022. 4. 14.

[프로그래머스] Swift 튜플 2019 카카오 implementation 문제 : https://programmers.co.kr/learn/courses/30/lessons/64065?language=swift 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 분석 : string 배열을 돌며 "{" 가 나타났을때 "}"가 나타나기 전까지 원소를 하나씩 담는다. result array에 값이 없을때만 원소를 담아 리턴하도록 했는데 이 부분에서 O(n^2)을 사용해 되게 비효율적이라는 생각이 들었다. 다른 사람들 풀이를 보니 comp.. 2022. 4. 14.

[프로그래머스] Swift 2020 카카오 괄호변환 문제 : https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 난이도 : level2 분석 : 주어진 요건을 잘 읽고 요구 사항대로 구현하는 문제였다. 이런 문제일수록 설계를 잘 하지 않으면 로직이 꼬이기 쉬워 어려운거 같다(나한테만 일지도 모른다 .. ㅎ) 1,2,3,4번을 차례대로 구현해주되 필요한건 함수로 분리해 작성하는것이 좋다 판단 들었다. 따라서 1번은 isEmpty로 검사하였다. 2번은 recursive.. 2022. 4. 14.

[프로그래머스] Swift 2018 카카오 뉴스 클러스터링 implementation 문제 : https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 난이도 : level 2 분석 : 자카드 유사도를 구하는 문제로, 집합의 교집합, 합집합을 구하는 구현하는 문제였다. 다만 집합이지만 중복된 원소가 존재하는 다중 집합으로 구현해야 해서 Set 타입 대신 Array를 사용했다. Swift 코드 : // // main.swift // SOMA👩🏻‍💻 // // Created by Jo.. 2022. 4. 13.

[백준] 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.

이전 1 2 3 4 5 다음

티스토리툴바