여행자의 책

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 풀이 삼성 A형 기출 문제/구현과 브루트포스 반복문이 다음과 같은 방식으로 진행된다. 궁수의 배치를 바꿔가면서 아래를 진행한다. 1. 공격할 대상 찾기 2. 공격 3. 적 좌표 업데이트 4. 공격한 대상 제거 게임 맵 전체를 갖고 연산을 수행하는게 아니라 목표를 갖는 배열을 따로 만들어서 관리하는게 낫다 def calc_distance(case): #궁수별 공격가능한 좌표를 찾아서 저장해준다. poss..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1. 풀이 문제 : BOJ 9730 미확인 도착지 알고리즘 유형 : 다익스트라 시작점 A에서 T까지 가는 최단 경로중 경유지에 g,h 노드가 있는지 확인하는 문제였다. 맨 처음 풀 때는 최단경로를 지나는 경로중에 g,h가 있으면 출력하도록 했는데 최단 경로가 여러개 있는 경우를 잡지 못해 실패했다. S에 T까지 가는 최단 경로중 g,h가 포함되어 있음을 보장하기 위해선 다음을 만족해야한다. ..

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 : 1774ms BOJ 1039 교환 파이썬 BFS 문제 맨 처음에 모든 자릿수에 대해 방문여부를 확인 하는 배열을 만들려고 했지만 자꾸 시간초과가 났다. 전체 숫자 범위(1에서 1,000,000)와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열을 만든뒤 BFS를 수행한다. N, K = input().split() M = len(N) #전체 자릿수 K = int(K) #전체 숫자 범위와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열 cache =[[..

1. 상호 배타적 집합과 유니온 파인드 상호 배타적 집합이란 서로간의 교집합이 없는 부분집합을 의미한다. 이를 표현하기 위해 유니온 파인드(Union Find) 라는 자료구조를 사용한다. 상호 배타적 자료구조를 표현하기 위해선 크게 3가지 연산이 필요하다. 1. 초기화(Initialization) : n개의 원소를 n개의 집합에 포함되어 있도록 초기화 2. 합치기(Union) : 두 원소에 대해 이 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합친다. 3. 찾기(Find) : 임의의 원소가 어떤 집합에 속해 있는지 반환 => 이러한 연산을 클래스로 구현해주면 된다. 2. 구현 다음은 파이썬으로 구현한 Navie한 Union 파인드이다. class NaiveDisjointSet(): parent =..

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 1. 풀이 다이나믹 프로그래밍 문제다. 규칙 1, 2, 3에 따라 채워가면 되는 문제로 bottom up 방식을 사용했다. * 먼저 카드 개수가 N이라고 할 때 N*N을 만들고 뒤쪽에서 부터 채워간다. * i 인덱스는 left의 카드번호 j 인덱스는 right 의 카드번호를 의미한다. * left[i] > right[j] 인 경우에는 오른쪽 카드를 버리고 스코어에 버..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 풀이 전형적인 플루이드 마셜 구현 문제이다. 플루이드 마셜은 모든 노드에대한 모든 노드의 최단 거리를 구하는 알고리즘이다. 특정한 학생의 키순서를 알기 위해선 자신보다 몇 명이 큰지 그리고 몇명이 작은지 전체 학생 수에 대해서 알아야한다. 예를 들어 전체 학급 구성이 8명인 반에서 학생 A가 전체 반에서 4번째로 크다고 가정해보자. 이 학생이 4번째로 큰 학생임을 알기 위해선 위로 3명 아래로..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 전형적인 삼성 DFS/BFS + 구현 문제 였다. 규칙이 복잡하게 구성되어 있기 때문에 구조를 먼저 짠 후에 코드를 작성하도록 하자 1. 초기 상어의 위치를 알아내고 상어위치에 있는 값을 0으로 바꾸어준다. 반복문 1. 상어의 위치 주변에 먹을 수 있는 물고기가 있는지 확인한다. 2. 있으면 먹은 후 시간, 먹은 횟수, 사이즈, 상어의 위치를 업데이트 한 후 continue를 통해 1과..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 두가지 방법으로 풀 수 있다. 1. 동적 계획법 2. DFS(깊이 우선 탐색법) 1. 동적 계획법 - 메모이제이션을 i번째 상담을 수행했을 때 받을 수 있는 최대 페이를 기준으로 수행한다. - i 번째 상담을 수행하면 T[i] ( i번째 상담의 상담기간 ) 동안 상담을 하지 못하기 때문에 i부터 i +T[i] 사이에 있는 상담은 뛰어넘는다. - i 번째 상담을 수행하려면 i번째 날부터 상담기간을 더한 날이 퇴사 날(i + T[i])을 넘지 않아야한다. - i 번째 상담을 수행했을 때 퇴사날을 지나친다면 전날 값(dp[i-1]) 로 업..

boj 1261 알고스팟 문제 www.boj.kr/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 2. 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 1.속한 노래가 많이 재생된 장르를 먼저 수록합니다. 2.동일 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 3.장르 내에서 재생 횟수가 같은 노래 중에..