[백준/1987] 알파벳 | DFS와 백트래킹
·
PS/BOJ&Programmers
알파벳오랜만의 백준 포스팅!!코테에서 부족함을 절실히x99 느끼고 다시 알고리즘을 본격적으로 시작했다..🥲🤗 문제 바로 가기  알고리즘 말이 보드를 탐색하는 조건은 다음과 같다.① (1,1)부터 탐색한다.② 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 이동할 수 있다. 이 조건 아래에서 가능한 경로 중 최대한 큰 수를 구하는 것이 목표다.따라서, DFS를 통해 탐색하는 방법을 선택했다.  def dfs(y,x,cnt): visited[y][x] = True alphabet[ord(graph[y][x])-65] = True # print('시작점: ', graph[y][x]) # 현재 위치에서 네 방향의 위치 확인 for dy, dx in dr: ny, nx..
[python] 파이썬으로 진법변환하기
·
언어/PYTHON
개요간단한 듯하면서도 구현을 할 때마다 까먹는 부분이 생겨서 이번 포스팅을 통해 확실하게 잡아보려고 한다.   1) 파이썬 함수를 통해 진법 변환하기십진수를 이진수로, 이진수를 십진수로 파이썬 함수를 통해 변환하는 것은 상당히 간단하다. 1-1) 십진수를 이진수로 변환하기십진수를 이진수로 변환할 때는 bin이라는 함수를 사용한다. 이 함수는 정수를 "0b"가 붙은 이진수로 변환해준다. (문서 참조) Built-in FunctionsThe Python interpreter has a number of functions and types built into it that are always available. They are listed here in alphabetical order.,,,, Built-i..
[백준/1547] 공 | 두 수의 전환
·
PS/BOJ&Programmers
공알고리즘알고리즘을 공부해본 사람이라면 한 번쯤은 겪었을 법한 두 수의 전환을 이용한다.   이 문제에서 주의해야 할 점은 공의 번호와 인덱스를 달리 생각해야 한다는 것이다. 예를 들어, 1번 공과 3번 공의 위치를 바꿀 때 배열의 인덱스는 그대로고 1번 공과 3번 공의 위치만 즉, 인덱스 번호 바뀌는 것이다.   그래서 인덱스로만 다룰 순 없고 for문으로 공의 번호가 저장된 배열을 돌면서 입력으로 주어지는 x,y의 위치를 찾아야 한다. for _ in range(m): x,y=map(int,input().split()) # x 위치 먼저 찾기 for i in range(len(arr)): if arr[i]==x: # x가 있는 위치의 값을 tmp_x 변..
[백준/1063] 킹 | 구현 실수 방지를 위한 경우의 수 체크하기
·
PS/BOJ&Programmers
킹 1063번: 킹8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는www.acmicpc.net 알고리즘킹이 움직인다. 이때 체크해야할 조건은 다음과 같다.  격자 안에서만 움직여야 한다.돌이 있는 곳으로 움직일 경우, 돌과 함께 움직여야 한다.이때 돌 또한 격자 안에서 움직여야 한다.돌이 격자 밖으로 나가는 경우도 체크하되, 이때 킹이 격자 내에서 움직인다면 상관없이 움직인다 이를 코드로 나타내면 다음과 같다.# 격자 내에서 해결해야한다.if (0   돌과 킹이 함께 움직이되 킹이 우선순위다. 이 케이스들을 if로 분기해주었다.  전체 코드# 행: row, 열: c..
[백준/5671] 호텔 방 번호 | 중복값 개수 세기(딕셔너리와 SET)
·
PS/BOJ&Programmers
5671 호텔 방 번호 5671번: 호텔 방 번호선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004호와 같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지www.acmicpc.net 알고리즘범위에 해당하는 숫자들이 자릿수마다의 중복되는지 체크하면 된다. 같은 값이 있는지 확인하는 방법으로는 딕셔너리를 떠올렸고 아래와 같이 중복 체크를 해주었다.  for item in hotel: d={'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0} flag=True for s in str(item)..
[백준/1068] 트리
·
PS/BOJ&Programmers
1068 트리 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net  알고리즘1. 이 문제는 부모가 인덱스, 해당 인덱스의 자식을 리스트로 부여한다. # index: 부모, 값: 자식# 노드의 범위가 0 ~ n-1인 경우for i in range(n): # root인 경우 if tree[i] == -1 : continue else: graph[tree[i]].append(i) 이렇게 표현하는 이유는 DFS 탐색 구현을 좀 더 직관적으로 평소와 같이 할 수 있기 때문이다...
[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS
·
PS/BOJ&Programmers
바이러스 Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net  알고리즘입력에서 직접 연결되어 있는 쌍이 주어진다.더보기더보기1 22 31 55 25 64 7 1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다.이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다. 양방향 그래프를 2차원 리스트로 정의graph = [[] for _ in range(n+1)]for _ in range(m): x,y=map(int, input().split()) graph[x].append(y) graph[y].append..
[백준/22232] 가희와 파일 탐색기
·
PS/BOJ&Programmers
가희와 파일 탐색기 22232번: 가희와 파일 탐색기첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다. 2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열www.acmicpc.net  알고리즘정렬이 순서대로 이어져야 하므로 lambda를 활용하였다.또한, 2 번째 조건은 까다로워서 정렬함수 말고 직접 교체해주었다. 전체 코드import sys;input=sys.stdin.readlinen,m=map(int, input().split())jo_test = [input().rstrip() for _ in range(n)]ext = set(input().rstrip() for _ in ra..
[백준/1107] 리모컨
·
PS/BOJ&Programmers
리모컨 Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net 이 문제는 세 가지 함정이 있다ㅠㅠ  해당 블로그에서 잘 짚어주셨고, 이를 참고하여 문제해결에 반영하였다.시작값(100)에서 +, - 버튼 조작으로 타겟 채널로 이동 vs 숫자 버튼을 통해 타겟 채널로 이동 고장난 버튼이 없을 때, 입력을 받지 않음차이의 최솟값을 구하는 게 최선이 아닐 수 있음 알고리즘1. 시작값(100)에서 타겟값까지의 차이해당 문제의 예시에도 잘 나와있듯이, N = 100인 상황일 때는 당연히 리모컨을 조작하지 않아도 된다.  2. 고장난 버튼이 없을 때 입력을 받지 않음m의 범위는 0 ~ 10이므로, m = 0..
[백준/7576] 토마토
·
PS/BOJ&Programmers
토마토  7576번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토www.acmicpc.net 알고리즘 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다.시작점을 미리 queue에 넣어서 방문할 수 있도록 한다.1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다.이 부분을 print로 찍어보면 다음과 같이 나온다.일단 queue에 익은 토마토(1)의 위치를 모두 append 해두었으므로..
[백준/7785] 회사에 있는 사람 | 딕셔너리 | 코드 비교
·
PS/BOJ&Programmers
회사에 있는 사람  Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net 회사에 출입하는 사람의 기록이 남는다.이 기록을 통해 회사에 남아있는 사람의 목록을 출력한다. 알고리즘 회사에 남아있는 사람을 체킹해야 하므로 출입 카운트를 해주었다.입장 + 퇴장은 무조건 짝수이므로 홀수 카운팅이된 사람은 회사에 남아있는 사람이다.입력 받은 이름을 정답 출력에 사용해야 하고 각각의 사람마다 카운팅 기록을 남겨주어야 하기 때문에 딕셔너리를 활용했다. 전체 코드와 알게된 점import sys; input = sys.stdin.readlinen = int(input())dic = dict()least_name..
[백준/1015] 수열 정렬
·
PS/BOJ&Programmers
수열 정렬  Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net  알고리즘입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다.  일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N  같은 숫자를 어떻게 처리할 것이냐가 관건이었는데, k라는 변수를 하나 만들어서 indexing하도록 지정해주었다.  전체 코드import sys; input = sys.stdin.read..
[백준/11004] K번째 수 | Python 정렬 함수의 알고리즘
·
PS/BOJ&Programmers
K번째 수  Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net 알고리즘N(1Ai(-10**9 범위가 위와 같이 주어졌기 때문에, List를 정렬하는 sorted()나 sort()로 하면 당연히 시간 초과 코드일 줄 알았는데 의외로 정답이었다.그래서 이번 기회를 통해 python의 리스트 정렬 연산의 원리와 복잡도에 대해 알아보려한다. sort() This method sorts the list in place, using only comparisons between items. This method modifies the sequence in place for economy of space..
[백준/1032] 명령 프롬프트 | 문자열 비교
·
PS/BOJ&Programmers
명령 프롬프트 알고리즘문자열 비교 알고리즘이다.이런 문제를 풀 때는 모든 보기를 다 비교해야 할지, 일부로도 해결이 가능한지 판단한다.어차피 N의 범위가 적으니까 할 수 있는 건 다 해서 풀어낸다.전체 코드내가 작성한 코드import sys; input=sys.stdin.readlinen=int(input())file=[input() for _ in range(n)]tmp=[]for i in range(n): for j in range(i+1, n): if file[i] != file[j]: a = file[i] b = file[j] for k in range(len(a)): fo..
[백준/1009] 분산 처리 | 반복되는 숫자 어떻게 효율적으로 처리할까
·
PS/BOJ&Programmers
 분산 처리 알고리즘승수의 마지막 자리 반복001122 4 8 633 9 7 144 6556677 9 3 18 8 4 2 699 1 수의 끝자리만 가져오는 두 가지 방법문자열 활용 a = str(a) a = int(a[-1])나머지 활용(%10, %100, %1000, ....)a %= 10 # 끝 한 자리만a %= 100 # 끝에서부터 2개전체 코드import sys; input=sys.stdin.readlinet=int(input())for _ in range(t): a,b = map(int,input().split()) a = str(a) a = int(a[-1]) if a == 1 or a == 5 or a == 6: print(a) # 4 번씩 반복..
sebinChu
'Problem Solving' 태그의 글 목록
상단으로

티스토리툴바