척척학사의 코딩 여행💻

10448 유레카 이론 문제로 이동 문제 요약 자연수 N에 대해 삼각수 $$Tn = 1 + 2 + 3 ... + n = n(n+1)/2$$ 공식이 성립된다. 모든 자연수가 최대 3개의 삼각함수의 합으로 표현될 수 있다구 증명하였는데, 몇 자연수는 정확히 3개의 삼각함수로 표현될 수 없다. 정수가 주어졌을 때, 삼각수인지 판별할 수 있는 프로그램을 작성해야한다. 알고리즘 삼각수가 모여있는 집합을 만든다. 삼각수 집합을 이용하여 순서 없이 중복 허용된 요소 3개를 뽑아 더한다. 해당 자연수는 3개로 표현할 수 있는 자연수이다. 이를 result 배열에 1로 저장한다. 입력받은 정수를 x라 할 때, result[x]를 출력한다. result 배열에는 유레카 정수인 경우만 1로 저장돼있다. 접근방법 수학적 공식..

11725 트리의 부모 찾기 문제로 이동 문제 요약 루트 노드가 1인 트리에, 각 노드의 부모 노드 번호를 찾는 문제이다. 알고리즘 입력을 기반으로 인접 리스트로 만든다. 루트 노드(1번노드)부터 BFS를 탐색한다. 부모노드를 찾아 출력한다. Queue에서 pop 된 노드가 부모 노드이고, 이 노드에서 방문가능한 노드들이 자식 노드가된다. 주어진 입력을 기반으로 인접 리스트로 만들고, BFS를 이용하여 부모 노드를 출려한다. 접근 방법 처음에는 입력받은 즉시 부모 노드를 찾을 수 있지 않나 라고 생각했다. (예제만 보면 그렇다) 더보기 처음 접근했던 방법 ( 틀렸습니다 ) 처음에는 굳이 그래프 탐색을 하지 않고 문제를 풀 수 있다고 생각했다. result라는 배열에 1만 1로 저장하고, 나머지 노드들에 ..

11403 경로 찾기 문제로 이동 문제 요약 가중치 없는 그래프 G에서, 노드 i에서 j로 가는 경로가 있는지, 없는지 인접 행렬로 표현해야하는 문제이다. 알고리즘 인접행렬을 입력받아 인접 리스트로 만든다. BFS를 이용하여 탐색하고, 인접 행렬 형태로 표현하여 출력한다. 접근방법 인접 리스트를 사용하면 단방향 간선을 표현하기 더 좋다 인접리스트로 그래프를 만들어서 방향이 있는 그래프를 표현하고, BFS로 어디를 방문할 수 있는지 계산해보아야한다. 이때, 기존 BFS처럼 자기 자신을 방문처리하면 안 된다. (내 자신을 방문할 수 있다는 것을 보장할 수 없기 때문이다.) Dictionary 초기화 꿀팁! 딕셔너리의 value가 리스트일 때, 만약 key가 처음 나오는 경우는 대입연산자를 사용해아하고, 이미..

7562 나이트의 이동 문제로 이동 문제 요약 체스 판 위에 나이트를 이동시키면서 특정 (y, x)에 도달하기 위해 몇 번 움직여야하는지 계산해야한다. 즉, (y, x)에 도달하기 위한 최단거리가 얼마인지 구하는 문제라는 것을 알 수 있다. 알고리즘 test case만큼 반복한다. 체스 판의 크기, 시작 위치, 목표 위치를 입력받는다. 체스 판의 크기만큼 visited 배열을 선언한다. BFS를 수행해서 최단거리를 계산한다. 접근방법 나이트의 이동방향을 잘 계산해야한다. (좌표를 그려서 생각해보자) 최단거리이기 때문에 visited 배열을 Int로 선언하고, 움직일 때마다 +1을 해서 depth를 구하자. 목표 지점에 닿았다면, visited[goalY][goal[X] - 1을 출력해야한다.이것이 헷갈린..

4963 섬의 개수 문제로 이동 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 요약 섬이 몇 개인지 찾는 문제이다. 즉, 주어진 인접행렬에서 그래프가 몇 개 있는지 확인해야한다. (연결된 컴포넌트가 몇개야?) 특이한 건 대각선까지 연결된 컴포넌트로 정의한다는 것이다 알고리즘 입력으로 "0 0"이 들어올 때까지 반복한다. map (지도)를 입력받는다. w, h 크기에 맞춰 visited를 초기화한다. map을 순회하며, 아직 방문하지 않았고, 섬이라면 BFS를 실행한다. BFS를 몇 번 순회했는지 ..

문제 사이트 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 요약 N개의 구로 나누어진 시가 있다. 해당 시를 두 개의 구역(선거구)으로 나누어야한다. 한 선거구에 포함된 구역은 모두 연결되어야한다. (총 2개의 그래프로 구성돼야함) 이 때, 인구 차이의 최솟값을 구해라. 접근 방법 시를 2개의 구역으로 나눈다. 나누어진 선거구가 각각 연결되어있는지 확인한다. 인구수를 계산하여 최솟 값을 구한다. 접근 방법 시를 2개의 구역으로 나눈다. 비트마스킹을 사용해서 모든 경우의 수를 구했다. 이때 n/2의 경우의 수만 계산해도 된다...

문제 사이트 2852번: NBA 농구 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1 Clock { var miniute = lhs.miniute + rhs.miniute var hour = lhs.hour + rhs.hour if miniute >= 60 { miniute -= 60 hour += 1 } return Clock(hour: hour, miniute: miniute) } static func += (lhs: inout Clock, rhs: Clock) { lhs = lhs + rhs } } 2. State 팀 1의 우승 정보이다. (무승부, 이김, 짐) 3. winnerTeam 팀 1이 골을 넣을 때마다 +1, 팀 2가 골을 넣을 때마다 -1을 한다. 그렇다면 winnerTea..

문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 알고리즘 정렬, 자료구조 1. n을 입력받는다. 2. 다음 과정을 n번 반복한다. a. 사용자에게 단어를 입력받는다. b. set에 삽입에 성공한다면 중복이 되지 않았다는 의미 -> (단어, 길이)를 배열에 저장한다. c. set 삽입 실패시 다음 반복문으로 넘어가면 된다. 3. 해당 배열을 삼항연산자를 이용해 다음과 같이 정렬하면 된다. a. 만약 단어의 길이가 같다면 단어(사전..

문제 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 알고리즘 정렬 1. n을 입력받는다. 2. 반복문을 n번 반복한다. a. 입력을 받아서 점의 위치와 색을 입력받는다. b. 색은 key, 점의 위치를 value에 저장한다. (Int 배열 -> append) 3. dictionary의 value들을 정렬하여 sumOfArrow라는 함수를 호출한다. 1. 입력받은 배열의 길이가 1 이하라면 0을 return 한다. -> (런타임에러 예..

문제 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 알고리즘 정렬, 자료구조 1. n을 입력받는다. 2. 반복문을 n번 수행한다. a. 입력된 정보를 파일명과 확장자로 분리한다. b. 딕셔너리에 저장한다. (key = 확장자, value = 횟수 3. key를 기준으로 정렬 한 후 key와 value를 출력한다. 나의 코드 let n = Int(readLine()!)! var fileSuffix = [String: Int]() for _ in 0 ...