척척학사의 코딩 여행💻

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..

문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 고정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오 코드 (반복문 사용) 더보기 // 반복문 사용 import Foundation let input = readLine()!.split(separator: " ").m..

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고, 룰은 다음과 같다. 숫자가 쓰인 카드들이 N * M 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 예를 들어 3 * 3 형태로 카드르이 다음과 같이 놓여 있다고 가정하자. 3 1 2 4 1 4 2 2 2 여기..

문제 ‘큰 수의 법칙’은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순..