[백준/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..
[백준/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
[백준/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): if s in d.keys(): d[s] += 1 f..
[백준/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 탐색 구현을 좀 더 직관적으로 평소와 같이 할 수 있기 때문이다. 예컨대 dfs(i)로 시작해서 자식..
[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS
·
PS/BOJ&Programmers
바이러스 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 입력에서 직접 연결되어 있는 쌍이 주어진다. 더보기 1 2 2 3 1 5 5 2 5 6 4 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]...
[백준/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.readline n,m=map(int, input().split()) jo_test = [input().rstrip() for _ in range(n)] ext = set(input().rstrip() for ..
[프로그래머스] 자동차기록에서 장기/단기 대여 구분하기 | DATEDIFF, SQL IF문
·
PS/BOJ&Programmers
개요 이 문제의 핵심은 대여 시작일이 2022년 9월이어야 한다. ➡️ date_format 함수로 DATE형 원하는 형식으로 수정하기 장기/단기 기간은 30일이 기준이다. ➡️ datediff 함수와 if문 이용하기 DATEDIFF 날짜의 차이를 일(day)로 환산해주는 함수. datediff(date1, date2) 계산은 date1 - date2로 진행된다. 음수는 0으로 도출된다. IF문 if문은 SELECT와 WHERE 절에 사용할 수 있다. IF문 if(조건, 참일 때 결과, 거짓일 때 결과) if(datediff(end_date,start_date)
[프로그래머스] 자동차 종류 별 특정 옵션이 포함된 자동차 수 구하기 | LIKE 사용법
·
PS/BOJ&Programmers
개요 SQL의 LIKE문은 주로 쿼리문 WHERE와 함께 사용되며, 일치하는 컬럼을 찾을 때 사용한다. 해당 문제처럼, 컬럼에 다양한 정보가 있을 때 '통풍시트', '열선시트', '가죽시트' 등 특정 내용을 걸러내야 하는 경우에 사용하기 좋다. LIKE 사용법 -- A로 시작하는 문자 찾기 -- where 컬럼명 like 'A%' -- A로 끝나는 문자 찾기 -- where 컬럼명 like '%A' -- A를 포함하는 문자 찾기 -- where 컬럼명 like '%A%' -- A로 시작하는 두 글자의 문자 찾기 -- where 컬럼명 like 'A_' -- 첫 번째 문자가 'A'가 아닌 모든 문자열 찾기 -- where 컬럼명 like '[^A]' -- 첫 번째 문자가 'A' or 'B' or 'C'인 ..
[백준/1107] 리모컨
·
PS/BOJ&Programmers
리모컨 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 이 문제는 세 가지 함정이 있다ㅠㅠ 해당 블로그에서 잘 짚어주셨고, 이를 참고하여 문제해결에 반영하였다. 시작값(100)에서 +, - 버튼 조작으로 타겟 채널로 이동 vs 숫자 버튼을 통해 타겟 채널로 이동 고장난 버튼이 없을 때, 입력을 받지 않음 차이의 최솟값을 구하는 게 최선이 아닐 수 있음 알고리즘 1. 시작값(100)에서 타겟값까지의 차이 해당 문제의 예시에도 잘 나와있듯이, N = 100인 상황일 때는 당연히 리모컨을 조작하지 않아도 된다. 2. 고장난 버튼이 없을 때 입력을 받지 않음 m의 범위는 0 ~ 10이므로, ..
[프로그래머스] 131530. 가격대 별 상품 개수 구하기
·
PS/BOJ&Programmers
문제 PRODUCT 테이블에서 만원 단위의 가격대 별로 상품 개수를 출력하는 SQL 문을 작성해주세요. 이때 컬럼명은 각각 컬럼명은 PRICE_GROUP, PRODUCTS로 지정해주시고 가격대 정보는 각 구간의 최소금액(10,000원 이상 ~ 20,000 미만인 구간인 경우 10,000)으로 표시해주세요. 결과는 가격대를 기준으로 오름차순 정렬해주세요. group by기본 문제다. 문제를 잘 보면 만원 단위의 가격대 별로 상품 개수를 출력해야 한다. 상품 개수는 예시에 잘 나와있듯이 product_id를 집계 함수로 잘 세어주면 된다. 만원 단위의 가격대 별로 조작하기 위해서는, 현재 DB에 저장된 price 값을 조정하고, GROUP BY해야한다. SQL Integer 조작 14000, 23000 이런..
[백준/7576] 토마토
·
PS/BOJ&Programmers
토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 알고리즘 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다. 시작점을 미리 queue에 넣어서 방문할 수 있도록 한다. 1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다. 이 부분을 print로 찍어보면 다음과 같이 나온다. 일단 queue에 익은 토마토(1)의 위치를 모두 append 해..
[프로그래머스] 조건에 부합하는 중고거래 댓글 조회하기
·
PS/BOJ&Programmers
문제 USED_GOODS_BOARD와 USED_GOODS_REPLY 테이블에서 2022년 10월에 작성된 게시글 제목, 게시글 ID, 댓글 ID, 댓글 작성자 ID, 댓글 내용, 댓글 작성일을 조회하는 SQL문을 작성해주세요. 결과는 댓글 작성일을 기준으로 오름차순 정렬해주시고, 댓글 작성일이 같다면 게시글 제목을 기준으로 오름차순 정렬해주세요. sql 문제를 풀 때는 원하는 결과값이 어떤 것인지?에 대해 먼저 파악해야 한다. 그리고 이 결과를 도출하기 위한 세부적인 연산에 대해 고민한다. 먼저, BOARD 테이블은 게시글에 대한 정보를 담고 있고, REPLY 테이블은 그 게시물의 첨부파일 정보를 담고 있다.(쉽게 생각해서 댓글이다. REPLY 테이블의 필드값을 통해 유추할 수 있다.) 이러한 정보를 보..
[프로그래머스] 조건에 맞는 도서 리스트 출력하기 | DATE
·
PS/BOJ&Programmers
DATE SQL의 DATE 타입은 YYYY-MM-DD hh:mm:ss 형식이다. select 문에서 DATE(datetype_record) 이렇게 사용하면 YYYY-MM-DD 부분만 추출한다. DATE_FORMAT으로 기본값인 YYYY-MM-DD hh:mm:ss를 변경할 수 있다. DATE Format 2024-02-01 18:31:45 날짜 및 요일 포맷 형식 결과값 %Y 2000 %y 00 %M February %b Feb %m 02 %d 01 %e 1 %a Thu 시간 포맷 형식 결과값 %H 18(24시간) %h 6(12시간) %i 31(분) %s / %S 45(초) %m 02 해당 문제는 시간을 제외하고 날짜를 'yyyy-mm-dd' 데이터를 출력해야 하므로, SQL문은 다음과 같다. date_f..
[백준/7785] 회사에 있는 사람 | 딕셔너리 | 코드 비교
·
PS/BOJ&Programmers
회사에 있는 사람 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 회사에 출입하는 사람의 기록이 남는다. 이 기록을 통해 회사에 남아있는 사람의 목록을 출력한다. 알고리즘 회사에 남아있는 사람을 체킹해야 하므로 출입 카운트를 해주었다. 입장 + 퇴장은 무조건 짝수이므로 홀수 카운팅이된 사람은 회사에 남아있는 사람이다. 입력 받은 이름을 정답 출력에 사용해야 하고 각각의 사람마다 카운팅 기록을 남겨주어야 하기 때문에 딕셔너리를 활용했다. 전체 코드와 알게된 점 import sys; input = sys.stdin.readline n = int(input()) dic = dict() le..
sebinChu
'PS/BOJ&Programmers' 카테고리의 글 목록
상단으로

티스토리툴바