본문 바로가기

코딩테스트 문제풀이/beakjoon64

[백준] 1453 1로 만들기 백준 1453번 1로 만들기 DP [문제] 기본적인 DP(동적계획법) 문제 오랜만에 풀게되서 dp를 생각하지 못했고 dp개념을 다시 공부한 후 풀었다. 핵심은 1,2,3번으로 나온 연산의 최소횟수를 구하는 것 [과정] dp - BottomUp 풀이 / for문 사용 다른 하나는 재귀를 사용하는 TopDown 풀이가 있는데 이 문제에서는 BottomUp풀이를 사용했다. n에 변수 입력받기 dp배열을 0이 (x+1)개 있는 리스트로 초기화 dp[1]은 0이고 1이 1로 되는데 필요한 연산은 0회라는 뜻 즉, 이후에 dp[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것 2부터 n+1까지 반복 dp[i]=dp[i-1]+1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장 i에.. 2023. 5. 12.
[백준] 9251 LCS 백준 9251번 LCS 다이나믹 프로그래밍 / 문자열 [문제] 저번에 '이코테'책에서 풀었던 '편집거리'문제와 아주 유사함 [과정] 다이나믹 점화식을 사용한 2차원 배열의 동적 계획법으로 푼 문제 2차원 배열(dp)를 만들어 현재 위치에서 비교해서 갱신하는 원리 문자열의 알파벳을 순회할 때 같은 알파벳인 경우 해당 위치의 전의 dp값 +1을 현재 위치에 저장 알파벳이 다른 경우 이전까지 비교한 값 중 최대값을 현재 위치에 저장 [소스코드] # 9251 LCS def LCS(n,m): h,w = len(n), len(m) dp = [[0] * (w+1) for _ in range(h+1)] for i in range(1,h+1): for j in range(1,w+1): if n[i-1] == m[j-1].. 2022. 8. 22.
[백준] 7795 먹을 것인가 먹힐 것인가 백준 7795번 먹을 것인가 먹힐 것인가 정렬 / 이분탐색 / 투 포인터 [문제] [과정] 단순 2중 for문을 사용하면 시간초과가 발생 bisect를 사용해서 풀면 시간초과 해결! [소스코드] # 7795 먹을 것인가 먹힐 것인가 import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right for _ in range(int(input())): n,m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) ans = 0 a.sort(reverse=True) b.sort() for i in a: t.. 2022. 8. 19.
[백준] 2910 빈도 정렬 백준 2910번 빈도 정렬 자료구조 / 정렬 / 해시를 사용한 집합과 맵 / 트리를 사용한 집합과 맵 [문제] [과정] 입력받은 데이터를 [데이터, 순서, 빈도]의 형태의 리스트로 만듬 lambda sort를 통해 (빈도,순서)의 순번으로 리스트 정렬 정렬된 리스트를 반복문을 통해서 빈도의 개수만큼 데이터를 출력 [소스코드] # 2910 빈도 정렬 n,c = map(int, input().split()) arr = list(map(int, input().split())) data = [] # 데이터, 순서, 빈도 cnt = 1 tmp_data = [] for a in arr: if not a in tmp_data: tmp_data.append(a) data.append([a,cnt,1]) cnt += 1.. 2022. 8. 18.
[백준] 5430 AC 백준 5430번 AC 구현 / 자료구조 / 문자열 / 파싱 / 큐 [문제] [과정] 골드치고 많이 쉬운 문제다 싶었는데 시간초과랑 출력형식이 잘못되서 계속 오류가 났던.. 문제 ※ 기본 로직 1) 데큐에 형식에 맞도록 변형해서 숫자 데이터를 넣어 줌 (리스트 입력 -> deque() 형변환) 빈 배열이 들어올 경우 인덱싱을 할 시에 오류가 나므로 예외처리 대체 왜 입력을 저렇게 리스트로 주는거지.. 그냥 전처럼 숫자를 주지 이게 젤 까다로움.. ㅡㅡ 2) R이 나온 경우 저장 이 부분에서 그냥 R일 경우 reverse()를 사용하게 되면 시간초과가 발생 (나의 첫번째 경우) 따라서 R이 나온 횟수를 저장하고 R의 횟수를 저장한 변수의 홀짝 여부를 판단해 q에서 데이터를 앞에서 뺄건지 뒤에서 뺄건지 정하면.. 2022. 8. 12.
[백준] 1021 회전하는 큐 백준 1021번 회전하는 큐 자료구조 / 덱 [문제] [과정] 데큐가 기본 리스트보다 속도면에서 우위가 있음 리스트: O(N) 데큐: O(1) ※ deque 함수 정리 q.appendleft(v) : 왼쪽에 개체v를 추가 q.append(v) : 오른쪽에 개체v를 추가 q.index(v) : q에서 v가 있는 인덱스 반환 q.popleft() : 큐의 맨 왼쪽에 있는 개체를 반환 후 삭제 q.pop() : 큐의 오른쪽에 있는 개체를 반환 후 삭제 q.rotate(-v) : 큐를 오른쪽으로 v만큼 회전 # 숫자가 -2라면 오른쪽으로 2만큼 회전 q.rotate(v) : 큐를 왼쪽으로 v만큼 회전 q.reverse() : 큐 뒤집기 ※ 핵심 풀이 찾으려는 데이터의 큐의 인덱스와 (큐의 크기 / 2)를 비교 .. 2022. 8. 12.
[백준] 10866 덱 백준 10866번 덱 자료구조 / 덱 [문제] [과정] 큐 문제와 같음 차이점은 pop과 push를 앞,뒤에 나눠서 구현한다는 것 [소스코드] # 10866 덱 from collections import deque import sys input = sys.stdin.readline q = deque() for i in range(int(input())): data = input().split() if data[0] == 'push_front': q.appendleft(data[1]) elif data[0] == 'push_back': q.append(data[1]) elif data[0] == 'pop_front': if len(q) == 0: print(-1) else: n = q.popleft() p.. 2022. 8. 12.
[백준] 14503 로봇 청소기 백준 14503번 로봇 청소기 구현 / 시뮬레이션 [문제] 구현 + bfs 느낌? [과정] 기본적으로 bfs를 사용해서 로봇 청소기를 이동시켰음 현재 방향(d)가 0,1,2,3으로 들어오는데 각각 북,동,남,서 방향이므로 dx,dy 좌표를 해당 순서에 맞게 배치 함 방향변수 d를 갱신하고 계속 사용하기 위해 (cnt-1) % 4 로 계속 왼쪽방향으로 돌려주었음 ※ 기본 로직 현재 위치에서 bfs 실행 ---------------- 1 큐에 들어있는 좌표를 방문처리하고 이동횟수를 1증가 시켜줌 ---------------- 1 현재 좌표에서 북동남서 방향이 이동가능한지 비교 ---------------- 2 만약 이동 할 위치가 아직 방문한 적이 없고 벽이 아니라면 큐에 넣어주고 반복문 종료 -------.. 2022. 8. 12.
반응형

티스토리툴바