티스토리

케굴 코딩

검색하기

블로그 홈

케굴 코딩

kerryfrog.tistory.com/m

케굴 님의 블로그입니다.

구독자: 4

방명록 방문하기

주요 글 목록

[백준 11779] 최소비용 구하기 2 ( 다익스트라 ) 문제 요약 n개의 도시가 있을 때 출발지에서 도착지까지 가는 최소 비용과 경로를 출력해야하는 문제. 문제 입출력첫째 줄에 도시의 개수 n 이 주어짐둘째줄에 버스의 개수 m이 주어짐셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어짐마지막줄에 출발 도시의 번호와 도착지의 도시 번호가 주어짐입력 제한 크기n(1≤n≤1,000)m(1≤m≤100,000)접근 아이디어기본 다익스트라의 경우 특정 출발지로부터 모든 노드까지의 최소비용을 구할 뿐, 경로를 구하지 않는다.따라서 경로를 저장하는 배열을 만들어 경로가 업데이트 될 때 마다 변경해 준다.코드import java.awt.Point;import java.util.*;import java.io.*;public class b11779 { public sta.. 공감수 0 댓글수 0 2024. 11. 7.
[SWEA 1974] 스도쿠 검증 (java) import java.util.Scanner; import java.io.FileInputStream; import java.io.*; import java.util.*; class Solution { static int T; static int[][] arr = new int[9][9]; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); T = Integer.parseInt(br.rea.. 공감수 0 댓글수 0 2023. 7. 26.
[swea 1961] 숫자 배열 회전 (java) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /* 사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다. 이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다. */ class Solution { static int T; static int N; static int [][] arr; public static void main(String args[]) throws Exception { BufferedReader br = new B.. 공감수 0 댓글수 0 2023. 7. 26.
[백준 14719] 빗물 (python) 풀이 block을 차례로 순회하면서 첫 블록보다 크거나 같으면 첫 블록까지 쌓인 빗물을 센다. 그리고 해당 블록을 첫 블록으로 해준뒤 다시 block을 순회한다. 그런데 이 방법으로 풀면 아래의 반례를 통과하지 못한다. 3 6 5 4 1 3 1 2 answer : 3 그래서 나는 크거나, 마지막 블록인 경우에 블록을 뒤에부터 순회하며 쌓인 빗물을 셌다. 순회하다가 기준 블록보다 큰 블록을 발견하면, 그 블록을 기준으로 삼아 마저 순회한다. 코드 H, W = map(int,input().split(" ")) block = list(map(int,input().split(" "))) tmp_h = block[0] tmp_st =0 ans = 0 for i in range(1, len(block)): if t.. 공감수 0 댓글수 0 2023. 4. 28.
[백준 4485] 녹색 옷 입은 애가 젤다지? (python) 풀이 dfs 로 구현했는데 시간 초과로 틀렸다. 그래서 다익스트라로 다시 구현했다. import heapq N = 0 dx = [0, 1, 0 ,-1] dy = [1, 0, -1, 0] def dijkstra(cave, start): q = [] heapq.heappush(q, (cave[0][0], start )) distance[0][0] = cave[0][0] while q: dist, now = heapq.heappop(q) if distance[now[0]][now[1]] < dist : continue for i in range(4): new_x= dx[i]+ now[0] new_y= dy[i] + now[1] if new_x = N or new_y =N: continue cost = dist.. 공감수 0 댓글수 1 2023. 4. 20.
python 코테에 유용한 문법 정리 1. 배열 index 구하기 1-1 최대값이 중복인 경우 맨 앞의 인덱스를 반환한다. score = [10,2,4,5,9, 10]print(score.index(max(score)))#출력 : 0 1-2 배열의 최대값의 인덱스 다중으로 구하기 score = [10,2,4,5,9, 10]answer = list(filter(lambda x: score[x] == max(score), range(len(score))))print(answer)# 출력: [0, 5] 1-3 배열 맨 마지막 indextest = [1,4,5,6]print(test[-1])# 출력 : 6 2. 배열에 추가2-1 맨 뒤에 삽입list = [2, 9, 3]list.append(7)print(list)# 출력 : [2, 9, .. 공감수 2 댓글수 0 2023. 4. 12.
[백준 1806] 부분합 (python) 풀이 시간제한이 무척 짧으므로 시간 복잡도가 O(N)인 투포인터 알고리즘을 사용하여 풀어야 한다. # 부분 합 N, S = map(int, input().split(" ")) num = list(map(int,input().split(" "))) start=0 end = 0 part_sum = num[0] ans = 100001 cnt = 1 while start < N and end < N: if S cnt : ans = cnt part_sum -= num[start] cnt -= 1 start += 1 else : end += 1 cnt += 1 if end < N: part_sum += num[end] if ans == 100001: print(0) else : print(ans) 공감수 0 댓글수 0 2023. 4. 6.
[백준 1987] 알파벳 (python) 풀이 BFS로 풀게 되면 알파벳을 한번씩 방문하는 조건을 체크할 수 없다. 따라서 하나씩 가능성을 탐색하는 DFS로 풀어야 한다. 재귀를 이용하여 DFS를 구현하였다. 이미 방문한 적 있는 알파벳을 list에 append하여 저장하고 in 연산자를 사용하여 방문한적 있는지를 확인했더니 시간 초과가 났다. 그래서 알파벳을 길이가 26인 배열로 표현하여 포함 여부를 체크했더니 성공할 수 있었다. python에서는 문자를 아스키 코드에 해당하는 정수로 변환하기 위해 아래와 같이 ord 라는 연산자를 사용한다. ord('A') ord(board[new_x][new_y]) # 알파벳 # 세로: R, 가로: C # 행 : x , 열 : y dx =[1, 0, -1, 0] dy =[0, 1, 0, -1] R, C =.. 공감수 0 댓글수 0 2023. 4. 5.
[백준 25757] 임스와 함께하는 미니게임 python(시간초과) 배열의 중복을 제거하는 쉬운 문제다. 파이썬은 in 을 통해 배열속에 있는지를 체크해 주는데 편리해서 자주 사용한다. 그런데 in을 쓰면 종종 시간초과로 문제를 틀리는데 이 문제 또한 그러했다. game_dict = {'Y':2 ,'F':3, 'O':4 } people = [] N , game = input().split(" ") for i in range(int(N)): name = input() if name not in people: people.append(name) print( len(people) // (game_dict[game] -1 ) ) 그래서 배열의 중복을 set을 이용하여 제거해 주어 해결했다. game_dict = {'Y':2 ,'F':3, 'O':4 } people = [] N .. 공감수 0 댓글수 0 2023. 1. 4.
[백준 13549] 숨바꼭질 3 (python) 우선순위 큐를 이용한 구현 순간이동의 경우 시간 소모가 0초이다. 따라서 스택과 큐를 이용하여 그래프를 순회하게 될 경우에는 최단거리를 찾을 수 없게 된다. 그래서 떠올린 것이 우선순위 큐이다. 우선순위 큐를 이용하여 순간이동을 우선적으로 탐색하여 최단거리를 찾을 수 있었다. from queue import PriorityQueue N, K = map(int, input().split(" ")) def BFS(start, end): queue = PriorityQueue() queue.put((0, start)) visited = [int(0) for _ in range(100001)] while queue: cost,now = queue.get() if now == end: return cost visited[now] = 1 i.. 공감수 1 댓글수 0 2023. 1. 2.
[백준 4659] 비밀번호 발음하기 python (50%에서 틀림) 50% 가량에서 틀렸다. 나의 경우 이유는 출력 형식 이였다. if isGather and flag == True: print(" is acceptable.") else: print(" is not acceptable." ) 출력을 위와 같이 작성했더니 파이썬에서 자동으로 띄어 쓰기를 넣어 주었다. 그래서 아래와 같은 형식으로 출력이 나와서 틀렸다. is acceptable. gather = ['a', 'e', 'i', 'o', 'u'] while True: isGather = False flag = True target_txt = input() if target_txt == "end": break for i in range(len(target_txt)): if target_txt[i] in gather.. 공감수 0 댓글수 0 2023. 1. 2.
[백준 20055] 컨베이어 벨트 위의 로봇(python) deque 이용 구현 덱을 이용하여 컨베이어 벨트를 표현하였다. 덱속에 내구도와 로봇의 존재 여부를 넣어서 덱 하나로 모든 것을 관리 하였다. from collections import deque # input N, K = map(int, input().split(" ")) belt = list(map(int, input().split(" "))) belt_length = N*2 -1 queue = deque() for i in belt: queue.append([i, False]) result = 0 while True: last = queue.pop() queue.appendleft(last) queue[N-1][1] = False for i in range(N-2,-1,-1): now = queue[i] if now[1.. 공감수 0 댓글수 0 2023. 1. 1.
[백준 3190] 뱀 python (tc5 tc6 틀림) 회사 인턴분의 추천으로 BFS 다음 연습 대상으로 구현을 선택했다. 유명한 구현 문제로 구현 문제 연습을 시작했다. 회사 다녀서 맨날 코드짜서 그런지 시간이 오래 걸려도 그냥 풀면 풀린다. from collections import deque def snake(deque): direction = 0; deque.append([1,1]) for sec in range(1,10100): new_location = [deque[len(deque)-1][0] + dy[direction], deque[len(deque)-1][1] +dx[direction] ] location = deque.popleft() if new_location[0] > N or new_location[1] > N or new_locati.. 공감수 1 댓글수 3 2022. 12. 23.
[백준 9205] 맥주 마시면서 걸어가기 python from collections import deque def BFS(start, finish, shop): visited =[] queue = deque() queue.append(start) visited.append(start) while queue: n = queue.pop() if abs(n[0] - finish[0] )+ abs(n[1]-finish[1]) 공감수 0 댓글수 0 2022. 12. 21.
[백준 2468] 안전영역 (python) 시간초과 해결 https://www.acmicpc.net/problem/2468 시간초과로 정말 고생한 문제다. 기본적인 풀이는 BFS를 사용했다. 1. 시간 초과한 코드 #안전 영역 from collections import deque import sys input = sys.stdin.readline # input N = int(input()) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] board = [] for _ in range(N): board.append(list(map(int, sys.stdin.readline().split()))) #### function #### #새로운 safeZone의 시작을 찾는다. def start(visited, rain): for i in range.. 공감수 0 댓글수 0 2022. 3. 18.
[백준 1697] 숨바꼭질(python) 간단하게 BFS 방법으로 풀었는데 메모리 초과와 시간 초과가 떴다. 이유를 찾아보니 visited를 배열로 하여 if x not in visited: 조건을 사용하였더니 메모리 초과가 발생했다. 이걸 정수 배열로 고쳐주니 문제를 풀 수 있었다. #숨바꼭질 from collections import deque #BFS def BFS(start, finish): #쿠에에 ? queue = deque() queue.append([start,0]) visited = [0] * 100010 visited[start] = 1 while queue: x, cost = queue.popleft() if x == finish: return cost if x-1 >= 0 and visited[x-1] == 0: queue.. 공감수 0 댓글수 0 2022. 3. 14.
[백준 2167] 단지 번호 붙이기 (python) https://www.acmicpc.net/problem/2667 풀이 #단지 번호 붙이기 from collections import deque from importlib.resources import contents #새로운 단지를 찾아주는 함수 def findNewStart(board, visited, N): for i in range(N): for j in range(N): if [i,j] not in visited: if board[i][j] == "1": return i, j return -1,-1 def BFS(board, N): dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] village = [] visited = [] cnt = 0 x, y = 0,0 queue = d.. 공감수 0 댓글수 0 2022. 3. 12.
[백준 2178] 미로탐색(python) https://www.acmicpc.net/problem/2178 python의 입출력에 익숙해 지지가 않는다 .. 풀이 BFS 방법으로 풀었다. 큐에서 pop을 한 후, 그 위치로부터 상 하 좌 우의 좌표를 다시 큐에 넣는다. 이때 주어진 미로에서 벗어나지 않는 범위인지를 체크한다. 이때 cost를 함께 큐에다 넣어주는 방법으로 거리를 count 했다. from collections import deque def BFS(board, finish): visited = [] queue = deque() queue.append([[0,0] , 1]) while queue: n, cost = queue.popleft() #print("n and cost", n , " ", cost," board " ,boar.. 공감수 0 댓글수 0 2022. 3. 8.
[백준 2644] 촌수계산 (python) BFS DFS 문제집중 젤 쉬운거에 도전해서 쉬울줄 알았지만 .. 혼자 못풀었다 ㅋㅎㅋㅎ 촌수를 계산할 때 BFS의 흐름에 따라 촌수를 세야 했는데 큐 삽입할 때 촌수를 같이 넣어서 해결했다. 아무래도 ps를 많이 안해봐서 그런지 이런 생각은 아직 못하겠다 #촌수계산 from collections import deque def BFS(graph, start, end): visited = [] queue = deque() queue.append((start, 0)) while queue: n, x = queue.popleft() if n not in visited: visited.append(n) if n == end: return x if n in graph: tmp = list(set(graph[n]).. 공감수 1 댓글수 2 2022. 2. 18.
[백준 1260] DFS와 BFS (Python) 앞으로 코테 준비를 위해 한 종류씩 문제를 풀어보려고 한다. 우선 DFS BFS 먼저 공부하려고 한다. 1. 깊이 우선 탐색 (DFS, Depth First Search) 최대한 깊게 내려간 뒤, 더이상 깊게 갈 수 없을 때 옆으로 이동 특징 모든 노드를 방문하고자 할때 사용한다. 검색 속도는 BFS에 비해서 느리다. 구현 스택 , 재귀함수 2. 너비 우선 탐색 (BFS, Breadth-First Search) 최대한 넓게 이동한 후, 더이상 갈 수 없을 때 아래로 이동 특징 DFS에 비해서 빠르다. 구현 큐 from collections import deque # 깊이 우선 탐색 # stack 을 이용한 구현 def DFS(graph, start): visited =[] stack = [start] w.. 공감수 0 댓글수 0 2022. 2. 17.
[백준 1976] 여행가자 C++ 분리집합으로 풀리는 문제이다. 미리 구현해둔 분리집합 알고리즘으로 쉽게 풀었다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 typedef long long ll; using namespace std; int N, M; int parent[1002]; //현재에는 자기 자신이 root임 int find(int a) { //a가 root임 if (parent[a] < 0) return a; //a가 root가 아닐때 return parent[a] = find(parent[a]); } void merge(int a, int b) { a = find(a); b = find(b).. 공감수 1 댓글수 0 2021. 11. 14.
[백준 1260] DFS와 BFS(C++) #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 typedef long long ll; using namespace std; //N : vertex int N, M, V; int visited[1002] = { 0, }; int visited2[1002] = { 0, }; int adj[1002][1002]; int degree[1002] = { 0, }; queue q; // 깊이 우선 탐색 void DFS(int x) { visited[x] = 1; //방문 cout > b; adj[a][b] = 1; adj[b][a] = 1; } DFS(V); cout 공감수 1 댓글수 0 2021. 11. 6.
[백준 11660] 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. DP 배열 만들기 Dp 문제를 풀기 위해서 가장 먼저 해야할 일은 dp 배열을 정의하는 것이다. 이 문제에서는 dp[a][b]는 a,b 까지의 누적 합을 뜻한다. 예를들어 dp[2][2] 라고 하면 파란 영역의 합을 뜻한다. dp[3][4]는 위 그림의 파란 영역의 합을 뜻한다. dp문제는 점화식을 이용하여 풀어야 한다. 이 문제는 비교적 점화식이 .. 공감수 1 댓글수 0 2021. 10. 15.
[백준 1463] 1로 만들기 C++ 다이나믹 프로그래밍 문제이다. 실버 문제라서 그런지 식이 바로 떠올라서 바로 풀었다. 가장 i =1 부터 i+1 , i *2 , i*3 을 하나씩 계산해 주면 된다. 사실 3번 틀렸는데 이유가 dp[1] = 1이 아니라 dp[1] =0 이다. dp[1] =1이라고 하면 100% 까지 가서 틀렸습니다가 뜬다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 typedef long long ll; using namespace std; int num; int cnt=0; int dp[1000005]; int main() { cin >> num; for (int i = 1; i 공감수 1 댓글수 2 2021. 10. 9.
[백준 17498] 폴짝 게임 dp 로 풀리는 문제이다. [1,1] 에서 최대 이동 거리 D 이내에 갈 수 있는 곳을 모두 계산하는 방식으로 풀었다. 예를들어 아래와 같은 input이 있을 때 4 3 2 3 -5 4 2 0 0 1 -3 1 -2 9 1 [1,1]에서 갈 수 있는곳은 [2,1] [3,1] [2,2]이다. 그럼 [1,1]을 거쳐서 [2,1] [3,1] [2,2]에 갈때의 점수를 계산해서 원래의 값보다 더 크면 값을 바꿔준다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321999 typedef long long ll; using namespace std; int N, M, D; vector < .. 공감수 1 댓글수 0 2021. 10. 5.
[백준 1181] 단어 정렬 #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int N,M; vector v; bool compare(string a, string b) { if (a.length() == b.length()) { for (int i = 0; i < a.length(); i++) { if (a[i] == b[i]) continue; else return a[i] < b[i]; } return a.length() < b.length(); } else return a.length() < b.length(); } int main() { FASTIO; str.. 공감수 1 댓글수 0 2021. 10. 4.
[백준 22983 ] 조각 체스판 #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int row[3001][3001]; int col[3001][3001]; int dp[3001][3001]; int board[3001][3001]; int N, M; int main() { cin >> N >>M; FASTIO; //입력 string str =""; for (int i = 0; i > str; for (int j = 0; j < M; j++) { if (str[j] == 'B') { board[i][j] = 0; } else if(str[j].. 공감수 1 댓글수 0 2021. 10. 4.
[백준 14267] 회사문화 1 한번 틀려서 이유를 찾고자 조금 구글링을 한 문제였다. 구글링 해보니 예전에는 내리 갈굼 문제였는데, 지금은 칭찬하는걸로 내용이 바꼈다 ㅋㅋ 조금 귀엽게 바꾼것 같다 dp 를이용하여 풀었다. 그래프는 parent[] 배열을 이용하여 표현하였다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int now[100001]; int dp[100001]; int parent[100001]; int N, M; int main() { cin >> N >>M; //직원관계 받기 int a, b, c; for (int i = 0; i a; parent.. 공감수 1 댓글수 0 2021. 10. 4.
[백준 1149] RGB 거리 #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int cost[1002][3]; int dp[1002][3]; //int coin[101] = { 0, }, num_coin[10009] = { 0, }; int N; int main() { cin >> N; int a, b, c; for (int i = 1; i > a >> b >> c; cost[i][0] = a; cost[i][1] = b; cost[i][2] = c; } for (int i = 0; i < 3; i++) { dp[1][i] = cost[1][i]; } for (int.. 공감수 1 댓글수 0 2021. 10. 2.
[백준 10423] 전기가 부족해 (C++) #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; //루트 노드를 찾아주는 코드 typedef pair pii; vector city; vector gen; //발전기 있는 도시 int parent[5052]; int N,M,K; struct st { int s, e; float c; }; //간선간의 cost를 저장해 주자. st arr[100001]; bool compare(st a, st b) { return a.c < b.c; } int find(int a) { //cout 공감수 1 댓글수 0 2021. 10. 1.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.