알고리즘 문제풀이259 [백준 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. [백준 3085] 사탕 게임 (Swift) https://www.acmicpc.net/problem/3085 브루트포스아래와 같은 N*N 행렬에 사탕들이 종류별로 채워져 있음 -> 여기서 인접한 두개의 서로 다른 사탕을 서로 바꿨을 때,행 또는 열에(가로 혹은 세로로) 가능한 긴 연속된 사탕의 개수가 뭔지 출력하는 문제이다.CCPCCPPPC 접근방법1. 초기 상태에서 가장 긴 연속 사탕 수 구하기 (BFS로 할 수 있을 것 같긴 한데..그냥 칸마다 구했습니다! (당당))2. 바꿀 수 있는 두 캔디 찾기 (인접하면서 서로 다른 캔디 쌍)3. 두 캔디 위치를 바꿨을 때 (swap) 두 캔디를 포함하는 가장 긴 연속 캔디 수를 구하고 현재 최대 길이랑 비교해서 갱신이때, A, B 캔디라고 하면, A캔디 기준으로 가로, 세로로 가장 긴 연속 캔디 수 확.. 2025. 2. 12. [백준 2252] 줄 세우기 (Swift) https://www.acmicpc.net/problem/2252 위상정렬우선! 키 순서대로 줄을 세우는 아주 불쾌한 문제입니다!하지만 덕분에 위상정렬을 배우게 되었어요. 그나마 제 몫을 하는 문제였습니다 후키 순서대로 줄을 세우지만, 키는 알려주지 않고 두명의 학생을 비교해서 둘의 순서 만 알려주네요 그것도 몇명만어쨌든 알려진 키 순서를 어기지만 않게 1번부터 N번까지의 학생들을 차례로 나타내면 되는 문제입니다. 접근방법위상정렬을 사용해서 풀이하는 문제인데요.위상정렬은, 원소들을 정렬하는 데 순서가 있고, 이를 지켜서 정렬할 수 있도록 만들어진 알고리즘인 것 같습니다.이 문제에서 순서는 내가 줄 서기 위해서 내 앞에 먼저 서야하는 학생들이 더는 없는지. 를 확인하는 것이라고 생각하면 될 것 같습니다.무.. 2025. 2. 11. [Softeer] Hanyang Popularity Exceeding Competition (Swift) https://softeer.ai/practice/9495 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiDPN명의 유명인의 인기도(P)와 친화력(C)가 주어질 때, 철민이가 유명인을 만나면 조건에 따라 인기도가 1씩 증가한다.조건은 |유명인의 인기도 - 철민이의 인기도| 이다.철민이의 인기도가 0부터 시작할 때 어떤 유명인들을 만나야 최대 인기도를 달성할 수 있는지, 그 최댓값을 출력하는 문제유명인들을 만나는 순서를 변경하는 것은 어렵고, 만날지 안만날지만 선택할 수 있음 접근방법처음에는 유명인들을 순회하면서 만나는 경우와, 안만나는 경우를 모두 구하는 브루트포스 방식으로 DFS 처럼 풀어봤는데,중간에 시간 초과가 나서, 모두 확인하는 것 보다, 조건을 만족할 때까지는 재귀함수를.. 2025. 2. 7. [백준 16916] 부분 문자열 (Swift) https://www.acmicpc.net/problem/16916KMP 알고리즘 | 문자열(Knuth-Morris-Prett 이 만들어서 KMP 알고리즘. 이런거 보면 나도 친구들이랑 알고리즘 만들고 싶다 Sujeong-Hyein-Nawon SHN 알고리즘~ 음.. 신한은행 약자 같음) 문자열 두개가 주어진다. S, P가 주어지는데, S에 P가 속하는지, 즉 P가 S의 부분 문자열인지 판단해서 맞으면 1, 아니면 0을 출력하는 문제 접근방법contain 쓰면 되겠네~ 했는데 swift contains로 했더니 시간초과남 시간초과가 안났으면 브론즈 2가 맞을 것 같은데시간초과 때문에 KMP를 써야한다면..과연 브론즈가 맞는지..?KMP알고리즘 처음 들어보고 이번에 공부해서 풀었으요. 그치만 KMP알고리즘.. 2025. 2. 6. [백준 1197] 최소 스패닝 트리 (Swift) https://www.acmicpc.net/problem/1197크루스칼 알고리즘가중치 그래프의 간선 정보 ("노드1, 노드2, 가중치")가 배열로 주어지고, 모든 정점을 잇는 간선의 가중치 합이 최소가 되는최소 스패닝 트리의 가중치 합을 구하는 문제 접근방법처음에 다익스트라로 풀었다가 프림으로 풀었다가 안돼서 결국 크루스칼로 풀었다. 크루스칼 알고리즘의 핵심은1. 간선을 가중치 순으로 오름차순 정렬한다.2. 최소 간선 부터 살펴보면서 (담으면서) 선택된 간선에 의해 이어진 노드들의 부모노드를 통일시킨다.3. 이때, 간선을 선택할 때는 현재 이미 이어져있는 간선들에 연결된 노드들과 사이클을 형성하지 않도록 하는 조건을 건다.인데 이를 위해서는 1. [가중치, 노드1, 노드2]를 원소로 갖는 배열을 가중.. 2025. 2. 6. [Softeer] Pipelined (Swift) https://softeer.ai/practice/9496 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문자열 문제가 좀 복잡해보여서 해석하는 게 어려웠다.자동차를 만드는 데, 자동차마다 필요한 단계 개수가 배열로 주어짐, 그리고 이 단계가 의미하는 건 결국 이 자동차를 만드는데 걸리는 시간임. 자동차들이 모두 만들어지는데 걸리는 최소시간을 출력하는 문제 접근방법자동차가 생산되는데 5단계가 필요한 자동차는 1/5 만큼의 슬롯을 차지한다고 했음. 슬롯의 크기가 0-1 구간이어서, 1/5 슬롯을 차지하면 1초에 한칸씩 움직여서 이 전체 구간의 슬롯을 통과하는데 5초가 걸림. (단계 = 걸리는 시간)따라서 모든 자동차가 안기다리고 바로바로 들어갈 수 있으면, 최종적으로 걸리는 시간은 .. 2025. 2. 5. [Softeer] Yeah, but How? (Swift) https://softeer.ai/practice/9498 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문자열짝이 잘 맞는 괄호로만 구성된 문자열을 입력받아서 1과 +를 사이에 껴넣은 올바른 수식을 반환하는 문제 접근방법가능한 수식이면 아무거나 된다고 해서 조건을 아래와 같이 설정했다- 직전 문자가 "(" 일때, 다음 문자가 "("면 현재 문자열에 바로 추가, 반대로 다음 문자가 ")"면 "1)"을 현재 문자열에 추가(이러면 결론적으로 (( 혹은 (1) 이 된다)- 직전 문자가 ")"일때, 다음 문자가 "("면 현재 문자열에 "+("를 추가, 반대로 다음 문자가 ")"면 ")"만 현재 문자열에 추가(이러면 "))"혹은 ")+" 이런 모양이 된다)모든 예외 케이스를 고려했는지 확신.. 2025. 2. 4. 이전 1 ··· 3 4 5 6 7 8 9 ··· 29 다음 728x90
