potato's devlog

문제링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제풀이 해당 문제를 풀기 위해서는 완전탐색으로 풀거나, 백트래킹이라는 개념을 이용하는 방법이 있다고 한다. 완전탐색은 말그대로 그래프 전체를 탐색해서 팀원이 됐는지, 안됐는지 판단하는 방법이고, 백트래킹은 "DFS 방법이지만, 어느정도의 depth에 도달하게 되면 탐색중지"하는 알고리즘이다. 백트래킹에 대한 개념을 잘 모르니, 이 문제를 포스팅한 후 백트래킹과 관련한 알고리즘 포스팅을 할 예정이다. 우선 나..

문제링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 풀이 나는 아직 graph를 입력받는게 힘들다. 이번에 사용한 방식은, 다음과 같다. graph라는 2차원 배열을 만들고, 그 안에 연결된 노드들로 채워주었다. 그리고 하나의 노드를 선택하고, 그 깊이를 전체 다 탐색한 한다음, 연결이 끊기면!! 새로운 그래프를 탐색해야하는 것이기 때문에 DFS 알고리즘을 사용했다. 마지..

문제링크 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 내가 푼 코드 var n = Int(readLine()!)! var tp: [[Int]] = [] var dp = Array(repeating: 0, count: 100) for i in 0..

문제 링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 https://didu-story.tistory.com/98 [알고리즘] 탐색 알고리즘 DFS, BFS -- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다. 1. DFS Depth First Search, 깊이 우선 탐색 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 주로 스 didu-sto..

문제링크 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 내가 푼 풀이 모음과 자음을 모두 배열로 만들어준 뒤, 여기에 모음이 한개 이상 포함되는지와 자음의 개수를 따져주었다. dfs를 이용해서 풀었다. 중복이 허용되지 않기 때문에, 방문체크를 해가면서 풀었다. let LC = readLine()!.split(separator: " ").map{ Int(String($0))! } let l = LC[0] let c = LC[1] var charLis..

문제링크 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제풀이 지난번에 팀원 한분이 말씀해주셨던 꿀팁이 생각났다. 출력되는 순열에서, [ 1 1 ] [ 2 2 ] 와 같이 중복되는 값이 안들어있지 않은가? 그렇다면 visited 체크를 한다는 뜻이다! 이 말을 기억하면서 차근차근 dfs로 구현했다. dfs로 구현한 이유는? 순열에 담기 위해서 모든 수를 탐색해야하기 때문이다! 리스트로 담은 것을 출력하는 것이 정말 어려웠다. 팀원들..

문제 링크 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 내가 푼 풀이 permutation 으로 진행하면 될 줄 알았는데 이렇게 하면 같은 수 반복이 안됐다. 같은수를 반복해서 출력해주고, permutation 결과들을 출력하려고 했는데 생각처럼 잘 되지 않았다. func solution() { let arr = readLine()!.split(separator: " ").map{Int(String($0))!} let n = arr[0] ..

문제링크 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 문제 풀이 (첫번째 시도) 한자리수, 두자리수, 세자리수 로 나누어서 아래와 같이 풀이방법을 생각했다. (두번째 시도) - 맞았습니다! 위와 같은 방식으로 생각하니 9, 99, 120 이걸 설정할 방법을 못찾았다. 입력 가능한 숫자가 8자리..? 인데 이걸 다 if문으로 작성할 수도 없는 노릇이고, 그래서 비슷하지만 다른 방식으로 생각해보았다. 한 자리 수, 두 자리 수,,,, 가 아니라 일의 자리, 십의 자리, 백의 자리 이렇게!! 이렇게 하게 되면, 자리의 수가 변하는 거기 때문에 * 10 을 이용해서 설..

문제링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 좌우/상하 로 인접한 사탕을 바꿀 수 있다. 표[1]과 같이 사탕이 주어졌다. 여기서 [0][0] 사탕과 [0][1] 사탕을 바꾸어보자. 표[2] 와 같은 결과가 나온다. 이렇게 되면 행끼리 인접한 사탕의 최고 개수는 2, 열끼리 인접한 사탕의 개수는 3이 된다. 다시 표[1]로 돌아가서 표[1]에서 [0][0] 사탕과 [1][0] 사탕을 바꾸어보자. 표3을 보면, 행끼리 인접한 사탕 최고 개수는 2개, 열끼리 인접한 사탕 최고 개수는 1개 이다. 이 위의 과정을 for 문을 통해서 반복해주었다. 그..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 나의 풀이 먼저 규칙을 찾는데 시간이 조금 걸렷다. 과연 이렇게 푸는게 앞에꺼가 세개 반복되지 않고 구하는게 맞나? 싶었던 의심이 들었었다. 하지만 점화식을 생성하면서, 두번 연속 나온건 제외하고 점화식을 세워주면 되는 거였다. (이게무슨말이지,, 말로표현이 안되네 ㅠㅠ) 어쨋든 풀이는 아래와 같다. 예시로 준것 처럼, 포도주가 6개 주어졌따면, 위와 같이 구할 수 있다. 최대가 될 수 ..