programmers lv1 완주하지 못한 선수(고득점 kit)
전화번호 목록
처음 시도했던 접근법은,
HashMap<Integer, ArrayList
programmers lv2 전화번호 목록(고득점 kit)
완주하지 못한 선수
완주하지 못한 선수는 딱 한명이다.
그래서 완주자를 먼저 hashmap에 넣고,
SWEA 1953 탈주범 검거
백준 3190 뱀
백준 3190 뱀
문제를 풀면서 든 생각, 느낀점을 모두 기록해보려고 한다.
백준 5430 AC
백준 5431 AC
처음 든 생각은 RR이 있을 때는 무효한 연산이 되고,
RRDRRDRD…라는 함수 문자열이 주어졌을 때 R은 head, tail 인덱스를 가리키고, D는 그 첫 위치가 바뀔 때마다의 자리를 앞에서 첫째자리, 둘째자리…와 ,같은 식으로 하면 되겠다싶었다.
백준 12871 무한문자열
수정중
백준 12871 무한문자열
백준 조합문제
백준 1010 다리놓기
백준 16395 파스칼의 삼각형
백준 15489 파스칼의 삼각형
백준 2407 조합
백준 11051 이항계수2
백준 1010 다리놓기
백준 1074 Z
SWEA 1247 최적경로
백준 1440 수리공 항승
백준 1440 수리공 항승
완탐 문제만 풀다가 그리디 문제 하나 접했다고 기분이 이상하다..
뭔가 찜찜한 그런 기분
백준 2822 점수계산
백준 2822 점수계산
아직 자바 Compare가 낯설다.
8979올림픽은 compareTo로 풀 수 있는 것 같은데..
아직 그 C++에서 만들었던 comp함수랑 어떻게 다른건지 잘 모르겠다.
다시 보기..
백준 1302 베스트셀러
백준 1302 베스트셀러
HashSet 사용법 익히기
백준 11931 수 정렬하기4
백준 10610 30
백준 11728 배열의 합
백준 3273 두 수의 합
백준 3273 두 수의 합
오늘은 투 포인터와 슬라이딩 윈도우 문제를 풀어보려한다.
그 시작으로 간단한 백준 문제인 3273번 두 수의 합을 풀었다.
덧붙여 같이 보면 좋을 포스팅도 공유하고 싶다.
투 포인터와 슬라이딩 윈도우에 대해 간결한 설명이 있고, 이와 관련된 백준문제를 추천해준다.
hongju bolg
백준 2210 숫자판점프
백준 6603 로또
SWEA 1974 스도쿠 검증
수정중 !
SWEA 1940 가랏!RC카
매초 속도가 변하므로 시간은 따로 처리할 필요가 없었다.
커맨드 0,1,2에 따라 처리하고
변하는 속도에 따른 거리를 합산해주면 된다.
백준 N과M (1)~(4)
N과 M (1) : 중복x, 사전순으로 증가.
N과 M (2) : 중복x, 사전순으로 증가, 오름차순.
N과 M (3) : 중복o, 사전순으로 증가.
N과 M (4) : 중복o, 고른 수열은 비내림차순이어야 한다.
SWEA 5432 쇠막대기 자르기(백준 10799)
SWEA 1225 암호생성기
백준 2493 탑
SWEA 1218 괄호짝짓기
스택의 대표문제유형인 괄호 문제를 풀었다.
(이외에도 수식계산, 브라우저 탐색 등이 있다. )
백준 15650 N과 M
백준 순열문제
SWEA 2805 농작물 수확하기
전략은 잘 세웠다.
빠른 시간 안에 나만의 풀이법을 잘 찾았는데,
포문에서 if, continue,dir++순서에서 한 번 막혔고
j로 돌아가는 포문을 하나 더 둬야 좌우로 뻗어나가면서 탐색하는 데 초반에 풀 때는 이걸 간과했다.
한 20분, 30분 안에는 풀 수 있을 것 같았는데 아쉽다.
SWEA 1954 달팽이 숫자
문제전략
두 가지의 소스코드를 써놨다. 처음에 써 놓은 건 아래와 같이 출력됐다.
SWEA 1210 Ladder1
문제전략
델타 방식으로 좌우 탐색을 먼저 진행한다.
만약 1로 칠해진 곳이 있으면 2로 체크하고 isTurned를 true로 바꿔준다.
만약 여기서 토글되지 않으면, 좌우로 갈 곳이 없다는 뜻이니까 아래의 if문으로 가서 좌표를 위쪽 방향으로 진행시킨다.
만약 if문에서 map[–i][j]와 같이 하면 i가 0일때 outOfBound가 나니까 while문 상단에서 체크를 해줬다.
SWEA 1208 Flatten
문제전략
크기가 100인 배열을 준비하고, 높이를 입력받은 후 그 높이를 인덱스로 갖는 원소를 1만큼 증가시킨다.
예를 들어 42층의 블록이 들어오면, arr[42]++;을 한다.
입력 받을 때 max,min을 갱신한다.
입력 받고 나서, 덤프횟수에 맞춰서 arr[max]–, arr[max-1]++을 하고
arr[min]–,arr[min+1]++;을 한다.
백준 1244 스위치 켜고 끄기
흠 백준에서 자바는 채점이 정말 느리다. 채점을 5분이상 기다려본 적이 없는데 신기하다.
처음에 제출할 때 public class Main 으로 안 해서 컴파일 에러가 났다.
문제전략
기지국 문제를 풀고 와서 영향을 받았는지 다른 쪽으로 생각나질 않았다.
학생이 여성일 경우 좌우탐색을 한칸,두칸, 세칸 순으로 진행하게 포문을 돌렸다.
static int[] dx = { -1, 1 };
for (int j = 1; j < N; j++) {
int left = dx[0]j + NUM;
int right = dx[1]j + NUM;
} 이런식으로 돌게 만들었다.
IM 기지국
문제를 간단히 설명하자면 기지국 A,B,C는 각각 사방으로 한칸, 두칸, 세칸의 영향력을 미침. 그 범위 안에 들어오지 못하는 집이 몇개나 있는 지 세는 문제였다.
교수님의 코드는 하단에 추가했다.
다른점은,
첫번째로 toCharArray()와, for문에서 charAt()으로 받는 것.
두번째로, 나는 델타를 12개의 배열로 하드코딩했는데 교수님은 ABC기지국에 카운트를 줘서 cnt = map[r][c] - 65 + 1; 와 같이 쓰셨다.
이렇게 하면 for문을 하나만 써도int nc = c + dc[k] * d;처럼 쓸 수 있다.
SWEA 1289 원재의 메모리 복구하기
BufferedReader를 써봤다.
String으로 받은 뒤에 Integer.parseInt를 해야하나 고민하다가
그냥 char 자체로 인식해서 풀었다.
가장 메인 아이디어는 이전 배열의 원소가 다르면 카운트가 증가한다.
이번 기회에 SWEA에 제출은 처음 해보았다.
첫 줄에 package명은 제거하고,
파일 입출력으로 테스트했던 문장도 지워야했다.
System.setIn(new FileInputStream(“Input.txt”));
한 가지 실수를 더 했는데, test case가 1부터 시작하는 걸 습관처럼 0부터 해서 살짝 헤맸었다.
교수님 코멘트 : 처음에 배열 두 개를 사용하는 것을 풀어보세요. 보다 직관적인 방법이니까.
백준 10868 최솟값
시도1 : 문제이해를 잘못해서, 벡터 v를 입력받고 sort로 전체를 정렬시켰다.
그리고 나서 v[a]와 v[b]를 출력함.
(틀림)
백준 1764 듣보잡
처음에 든 생각은 브루트포스, string에서 find 함수, 2차원배열로 AND 연산 등이 있었다.
백준 1620 나는야 포켓몬 마스터 이다솜
단일벡터에서 매번 find를 하는 것보다, vector<pair<int,string» v(n);과 같이 정의하고 sort를 진행한 후 binary_search를 이용하는 게 훨씬 빠르다.(lower_bound) find함수는 O(n), lower_bound는 O(logn)이다.
백준 11726 2xn 타일링
코딩테스트에서 dp가 잘 안 나온다는 말을 듣고 랭작 비슷하게 하고 있다.
백준 9095 1,2,3더하기
#include <iostream>
#include <algorithm>
using namespace std;
int v[11];
int main() {
v[1] = 1;
v[2] = 2;
v[3] = 4;
int t, n;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
for (int j = 4; j <= n; j++)
v[j] = v[j - 1] + v[j - 2] + v[j - 3];
cout << v[n] << '\n';
}
}
백준 1463 1로만들기
입력받은 수 n에 대해서, bottom부터 n까지 for문으로 memoization을 한다. 원하는 값은 최소값이므로, 2로 나누어지더라도 min을 택해서 memo를 해야함!
바킹독의 실전 알고리즘 구버전 0x09강 dp
스크랩한 글입니다. 바킹독의 알고리즘 DP 중요하다고 생각되는 부분, 필요한 부분을 저장하고자 함
스크랩한 글입니다
알고리즘 공부를 하면서..
살짝 자괴감이 들어서 잠깐 공부법에 대한 구글링을 했다.
baactree님 블로그
백준 7662 좌표압축
시도 1 : vector 삽입은 v.push_back(n); 으로 하고, v.erase(max_element(v.begin(), v.end())); v.erase(min_element(v.begin(), v.end())); => 시간초과
백준 1927 최소힙
최대힙과 유사한 문제다. 코드한줄만 변경하면 된다.
최대힙에서는 priority_queue
백준 18870 좌표압축
이 문제에서 좌표압축을 처음 접했다. 내 언어로 정리해보자면, -10부터 10까지 범위에서 -10,2,5,10으로 네 수가 있을 때 0,1,2,3으로 인덱싱을 해서 좌표공간을 압축한다. 만약 중복값이 있다면 제거하고 인덱싱을 하면 된다.
입력받은 배열을 먼저 sort함수로 정렬한 후 unique함수로 중복값을 제거한다. 이렇게 정리한 배열의 하한값- 배열의 첫 요소를 빼면 0이 나올 것이다. 배열의 나머지 요소들도 같은 방식으로 해결하면 된다.
백준 11279 최대힙
stl queue에서 priority_queue를 사용하면 쉽게 풀 수 있는 문제였다.
백준 11723 집합
보통 이런 문제는 큐나, 스택에서 많이 보던 유형인데 특별히 저장되는 순서는 상관없었고
stl vector를 사용하면 될 것 같았다. add, remove, check 등의 기능을 가진 함수를 각각 만들고 main함수에서 string을 입력받은 후 각 함수를 호출하는 식으로 풀었다.
백준 1931 회의실 배정
처음에 풀 때는 v[i].second에서 v[i].first를 뺀 값으로 정렬하는 과정도 추가했었는데, 딱히 그럴 필요는 없었다.
너무 복잡하게 생각했나보다.
백준 2606 바이러스
연결요소 문제와 비슷하게 풀었습니다. 정점개수와 간선개수를 입력받은 후
간선의 걍 끝점 u,v를 입력받습니다.
그대로 인접행렬을 만들어주고, dfs로 풀었습니다.
백준 11399 ATM
문제설명이 좀 복잡하다고 생각했습니다.
제가 더 간단하게 설명할 순 없을 것 같지만,
인출시간이 짧은 사람부터 줄세워야 각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 될 것임을 알 수 있습니다.
따라서 이 문제는 그리디문제로서 오름차순 정렬이 우선되어야함을 직관적으로 알 수 있습니다.
백준 11724 연결요소의 개수
정점개수와 간선개수를 입력받은 후
간선의 걍 끝점 u,v를 입력받습니다.
그대로 인접행렬을 만들어주고, dfs로 풀었습니다.
백준 7576 토마토
익은 토마토를 기준으로 하루가 지나면 상하좌우에 있는 토마토가 익게 됩니다.
총 며칠이 자나야 토마토들이 모두 익는지 일수를 구하는 문제였습니다.
백준 1697 숨바꼭질
온라인 알고리즘 마라톤 2주차 문제로 풀게 되었습니다.
이전에 바킹독님 강의에서도 한 번 본 적이 있어서 수월하게 풀었던 것 같습니다.
간단하게 문제를 요약하자면,
수빈이와 동생의 위치를 입력받고,
수빈이가 x-1, x+1, 2*x로 움직이면서 그 거리에 동생이 위치하였는지 알아보는 문제였습니다.
백준 1047 Z
백준 1047번 Z을 풀었습니다.
고해성사하자면 1시간동안 곱해보고 나눠보고 모드연산도 해보고 여러 시도를 했지만
분할정복과 사분면 정도 감을 잡고 코드로는 작성하지 못했습니다.
시간이 너무 오래걸리는 것 같아 타인의 코드를 보고 배웠습니다.
참고한 블로그링크입니다.
백준 1003 피보나치 함수
백준1003 피보나치함수를 풀었습니다.
처음에는 너무나 쉽게 생각한 나머지,
주어진 예시의 피보나치 함수에서 n이 0일때, n이 1일때의 조건문에서 각각의 카운트를 증가시키는 방법을 써봤습니다.
물론 틀렸습니다….(시간초과)
아무렴 이렇게 쉬울리 없지ㅎㅎ
백준 1012 유기농배추
온라인 알고리즘 마라톤에서 첫주차에 풀기로 정한 문제이다.
solved.ac에서 클래스3 에센셜을 차례로 푸는 듯 하다.
마침 바킹독님 강의에서 BFS,DFS를 막 들었는데
병행해서 풀어보기 좋은 것 같다.
백준 11723 집합
//이전에 제출한 코드에서 코드반복 줄임.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> v;
int check(int n) {
vector<int>::iterator iter;
iter = find(v.begin(), v.end(), n);
if (iter == v.end()) //없음
return 0;
else
return 1;
}
void remove(int n) { //원소가 있는지 사전에 체크한 후 실행
vector<int>::iterator iter;
iter = find(v.begin(), v.end(), n);
v.erase(iter);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m, n;
cin >> m;
string str;
while (m--) {
cin >> str;
if (str == "check") {
cin >> n;
cout << check(n) << '\n';
}
else if (str == "add")
{
cin >> n;
if (!check(n)) v.push_back(n);
}
else if (str == "remove")
{
cin >> n;
if (check(n)) remove(n);
}
else if (str == "toggle")
{
cin >> n;
if (check(n)) remove(n);
else v.push_back(n);
}
else if (str == "empty")
v.clear();
else if (str == "all") {
v.clear();
for (int i = 0; i < 20; i++)
v.push_back(i + 1);
}
}
}
programmers lv1 x만큼 간격이 있는 n개의 숫자
구글링해서 참고한 코드임 …
순환을 위한 코드 저 부분이 너무 낯설어서 시간이 좀 걸렸다.
programmers lv1 콜라츠 추측
#include <string>
#include <vector>
using namespace std;
int solution(int num) {
int answer = 0;
long long n= num; //범위 초과될 수 있어서!!!
while(n!=1){
if(answer==500){
return -1;
}
if(n&1){
n= n*3 +1;
}
else{
n/=2;
}
answer++;
}
return answer;
}
programmers lv1 하샤드 수
```cpp #include
programmers lv1 x만큼 간격이 있는 n개의 숫자
```cpp #include
programmers lv1 이상한 문자 제거하기
공백을 기준으로 입력받은 s를 토큰으로 나누어야하나 잠깐동안 고민했음.
그러나 생각을 바꿔서, i를 기준으로 작동하는 포문 1개에서 j변수를 같이 사용하기로 했다.
아스키코드 기준으로 [65,91]이 대문자, [97,123]이 소문자다.
알파벳 개수는 26개지만 대문자와 소문자 사이의 간격은 32라서, 소문자에서 32를 빼면 대문자가 되고 대문자일 때 32를 더하면 소문자가 되는 것을 이용했다. ```cpp #include
programmers lv1 제일 작은 수 제거하기
벡터를 사용해서 간단하게 풀 수 있는 문제였다.
굳이 반환하는 벡터 vector
종만북 27장 그래프
7부 그래프
- 27장 : 인접행렬, 인접리스트 구현법, 이에 대한 장단점
- 28장 : DFS(깊이우선탐색)
- 29장 : BFS(너비우선탐색). 가중치가 없는 그래프 상에서 최단경로를 찾기 위한 대표적인 알고리즘
추가적으로 양방향 탐색과 점점 깊어지는 탐색에 대해서 소개함 - 30장 : 가중치가 있는 그래프 상에서 정점 사이의 최단경로를 찾기 위한 알고리즘
경로의 출발점이 하나로 고정되어있는지에 따라 각각 다른 알고리즘을 사용해야한다. 대표적으로 다익스트라, 벨만-포드, 플로이드 알고리즘. - 31장 : 가중치가 있는 그래프 상에서 가중치의 합이 최소가 되도록 간선의 부분 집합을 선택해 정점들을 모두 연결하는 문제- 최소신장트리
- 32장 : 각 간선에 대해 길이뿐 아니라 용량을 정의했을 때 풀 수 있는 문제인 그래프의 최대 유량문제. 최적화 문제로, 그래프와는 상관없어 보이는 여러 문제를 풀 때 유용하다. 대표적으로 포드-풀커슨 알고리즘.
유튜브에서 BFS 영상보기
종만북 6장 브루트포스
6.1 도입
programmers 소수찾기
#include <iostream>
using namespace std;
int arr[100];
bool Prime(int x) {
if (x == 1)
return false;
else if (x == 2)
return true;
else {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (Prime(arr[i]))
cnt++;
}
cout << cnt;
}
백준 1018 체스판 다시 칠하기
처음 생각한 풀이 : 보드를 입력받은 배열에 첫번째가 B,W인지 확인하면서 새로운 배열에 B,W를 새로 작성하기.
막힌 부분 : 첫번째 요소가 B이면 그대로 두고 다음 요소를 W로 쓰려고 할 때, flag를 사용한다.
이런식으로 해서 (0,0)~(7,7)까지 한 번 배열을 작성하고, 총 재작성한 횟수를 어딘가에 또 저장해야하는가? 여기서 부딪힘.
뭔가 비효율적임을 깨달음;
