알고리즘 문제풀이230 [백준 16197] 두 동전 (Swift) https://www.acmicpc.net/problem/16197 DFS BFS아래와 같은 보드에 #은 벽, . 은 빈칸, o는 동전이다. 동전은 2개만 존재함6 2.#.#.#o#o###네 방향키를 누를 수 있고, 누를 때 마다 두 동전이 그 방향으로 한칸씩 동시에 이동한다. 벽이 있는 칸으로는 이동할 수 없음 (단 이동 카운트는 체크) 이동하려는 칸에 다른 동전이 있어도 이동할 수 있음 이때, 두 동전 중 하나만 떨어지는 최소 횟수를 출력하는 문제, 단, 10번 보다 버튼을 더 많이 눌러야 하거나 두 동전을 떨어뜨릴 수 없는 경우 -1을 출력한다. 접근방법BFS를 곁들인..DFS식으로 구현하되 모든 경우를 고려하는게 관건이었던 문제였다.dfs 함수 인자로 두 동전의 현 위치와 현재까지 누른 버튼 횟수.. 2025. 2. 26. [백준 1890] 점프 (Swift) https://www.acmicpc.net/problem/1890 DP42 3 3 11 2 1 31 2 3 13 1 1 0 현재 칸에서 우측 or 아래측으로 이동할 수 있는 칸 수가 각 칸에 명시되어 있는 위의 표를 보고1,1칸에서 N,N칸에 도달할 수 있는 경우를 출력하는 문제 접근방법DP 배열에 해당 칸까지 오는 경우의 수를 저장한다. 0,0 칸에서 시작하므로 이 칸은 1로 시작해서 맨 위칸 부터 왼쪽에서 오른쪽으로 순회하면서 각 칸에 올 수 있는 경우의 수를 더해가면 된다. 처음에는 BFS로 했었는데 그러면 이미 방문한 노드를 다시 방문할 수 있어서 시간복잡도가 더 올라가는 듯 오답노트마지막 칸에 갔을 때는 중복되니까 반복문 돌지 않고 종료해야한다. 소스코드import Foundationfunc s.. 2025. 2. 26. [백준 1303] 전쟁 - 전투 (Swift) https://www.acmicpc.net/problem/1303 완전탐색 (BFS)5 5WBWWWWWWWWBBBBBBBBWWWWWWW 위 처럼 가로, 세로 칸 수와 병사들의 배열이 이차원배열 형태로 주어지면, 상하좌우로 인접한 각 팀의 병사들 그룹 별로 그들의 위력(N(인접한 병사들의 수)^2)을 계산한 총합을 차례로 출력하는 문제 접근방법BFS(Breadth First Search) 알고리즘으로 풀이했다. 2차원배열을 전체적으로 순회하면서 visit 배열과 queue를 가지고 W(아군)의 인접 그룹 인원수 체크, B(적군)의 인접 그룹 인원수 체크 -> 큐가 비면 그룹이 끝났다는 뜻이므로 cnt (병사수) 제곱해서 각 팀의 위력을 저장하는 변수 Strength에 더하기 오답노트"가로가 N이고, 세로가.. 2025. 2. 24. [프로그래머스] 파일 정렬 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문자열파일명이 담긴 배열이 주어지고, 이를 일정한 규칙에 따라 정렬하면 되는데, 규칙은 아래와 같다.["img12.png", "img10.png", "img2.png", "img1.png"]우선 이런 파일명들이 주어졌을 때, 파일명을 세 파트로 나눈다. HEAD : 파일명의 앞부분에서 숫자가 아닌 부분. 즉 img-12sd.png라면 img- 까지가 HEAD이다. 숫자가 나타난 이후에 나타나는 문자는 포함하지 않음 (영문 알파벳(대소문자)과 특수.. 2025. 2. 21. [프로그래머스] 압축 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/17684?language=swift 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr구현 (투포인터..?)대문자 영어로 구성된 문자열이 주어지면, 그 문자열을 LZW(Lempel–Ziv–Welch) 압축 방법을 사용해서 압축하는 건데LZW 방법이 참..우선 A~Z까지 1~26 번호로 매핑된 맵이 있다고 한다. 문자열을 왼쪽에서부터 보면서 맵에 해당 문자열이 있으면 우선 맵에 없는 문자열 구간이 나올 때 까지 오른쪽으로 간 다음, 맵에 없는 문자열을 맵의 제일 끝에 추가한다 인덱스 번호는 맵에서 최대 인.. 2025. 2. 21. [백준 3568] iSharp (Swift) https://www.acmicpc.net/problem/3568 문자열, 파싱한줄에 기본 타입과 변수들이 주어지는데, 이 변수들이름 오른쪽에 추가적인 자료형이 붙어있을 수 있다.이때 각 변수들을 한줄에 하나씩 출력하는데 "기본타입+추가적인 자료형의 역순 변수이름;" 이렇게 출력해야 하는 문제변수형에는 [], &, * 가 올 수 있고, 변수 이름은 알파벳 소문자 혹은 대문자로 구성 접근방법1. 우선 첫번째 기본 자료형을 defaultType이라는 변수에 저장해두고,2. 변수들을 하나씩 보면서 isLetter 메서드를 사용해서 이름만 분리했다.3. 이제 추가적인 자료형을 역순으로 배치하기 위해서, 각 변수에서 isLetter가 아닌 문자들만 필터링했고, 이 문자열을 역순으로 순회하면서 "&" 혹은 "*"인.. 2025. 2. 20. [백준 2023] 신기한 소수 (Swift) https://www.acmicpc.net/problem/2023 소수N (1~8사이의 정수)가 주어지면 N자리 수 중 신기한 소수 조건을 만족하는 수를 모두 출력하는 문제신기한 소수 조건 : prefix 모든 접두어(?..수?)가 소수인 수예) 7331 : 7도 소수, 73도 소수, 733도 소수, 7331도 소수 접근방법1) 에라토스테네스의 체를 사용해서 N자리 수까지의 모든 수의 소수 여부를 저장한 배열을 만든 뒤, N자리 수를 하나씩 살펴보면서 그게 신기한 소수 조건을 만족하는지 확인한다 -> 시간초과2) 에라토스테네스의 체로 소수 여부를 저장한 배열을 만든 뒤, N자리 수를 하나씩 살펴보는데, 이때 접두어가 소수가 아니면 그 접두어로 시작하는 수는 건너뛰기 -> 시간초과3) 에라토스테네스의 체.. 2025. 2. 19. [백준 15486] 퇴사 2 (Swift) https://www.acmicpc.net/problem/15486 DP 동적프로그래밍그림의 표처럼 날짜 별로 할 수 있는 상담의 걸리는 일수와 얻을 수 있는 금액이 주어진다.상담을 하고 있는 동안 다른 상담을 할 수는 없기 때문에 최대 이익을 얻기 위해 몇개만 골라서 상담해야한다.얻을 수 있는 최대 수익을 출력하는 문제 접근방법처음엔 dp 배열에 해당일에 상담을 하는 경우 얻을 수 있는 최대 이익, 상담을 하지 않는 경우 얻을 수 있는 최대 이익을 계산해서 저장해두는 식으로 했는데, 남은 일수를 함께 저장하다보니 결정적이지 못한 문제가 있었다 (테스트케이스는 무리없이 돌아갔지만 통과되진 않음) 질문 게시판 보니까 엄청 간단하게 푸셔서 당황..;포인트는 해당 일에 저장하는 게 아니라 해당일의 상담이 끝나.. 2025. 2. 18. [백준 1260] DFS와 BFS (Swift) https://www.acmicpc.net/problem/1260 DFS & BFS4 5 11 21 31 42 43 4 노드수, 간선수, 처음 방문해야하는 노드 번호간선이 잇고 있는 두 노드 (양방향) 리스트가 좍 주어지고DFS로 방문하는 순서BFS로 방문하는 순서 를 출력하는 문제 접근방법DFS는 재귀함수를 정의해서, 방문 여부를 확인해가면서 인접 행렬을 통해 현재 노드와 연결되어 있지만, 아직 방문하지 않은 노드들을 차례로 순회하면서 풀이했고,BFS는 큐와 방문여부를 저장하는 배열을 사용해서, V부터 큐에 넣고, V에 연결되어 있는 노드 중 아직 방문하지 않은 노드를 큐에 넣고,큐에서 노드를 하나씩 빼면서 순서를 매기는 식으로 큐가 다 빌때까지 진행했다. 오답노트DFS에서 스위프트가 배열을 값 타입으.. 2025. 2. 17. 이전 1 2 3 4 5 ··· 26 다음 728x90
